Find all functions $f: \mathbb{Z}^+\rightarrow \mathbb{Z}^+$ such that for all positive integers $m,n$ with $m\ge n$, $$f(m\varphi(n^3)) = f(m)\cdot \varphi(n^3).$$Here $\varphi(n)$ denotes the number of positive integers coprime to $n$ and not exceeding $n$.
Problem
Source: China TST 2021, Test 2, Day 2 P4
Tags: number theory, totient function, function
22.03.2021 08:56
22.03.2021 09:07
23.03.2021 19:11
I think there's lots of good problems in this year's test. my solution is smilar to @above .. Let $P(m,n):=f(m\phi n^3)=f(m) \phi n^3$. claim1) $f(pm)=pf(m)$ for all prime $p$ and interger $m$ that satisfies $m \ge p^2$. <pf> we use strong induction on $p$. (1) $P(m,2): f(4m)=4f(m)$ $P(m,4): f(2^5m)=2^5f(m)$ So, $2^4f(2m)=2^2f(2^3m)=f(2^5m)=2^5f(m) \rightarrow f(2m)=2f(m) (m \ge 4)$ (2) say that $f(qm)=qf(m) (m \ge q^2)$ satisfies for all $q \leq p$. for all prime dividers of $p-1$ (let $r$), $r$ satisfies $r^2<p^2<mp^2$. So, we can use induction in the assertions below. $P(m,p) : f(m p^2(p-1)) = f(m) p^2(p-1) \rightarrow (p-1)f(mp^2)=f(m)p^2(p-1) \rightarrow f(mp^2)=f(m)p^2$. $P(m,p^2): f(mp^5(p-1)) = f(m)p^5(p-1) \rightarrow (p-1)f(mp^5)=f(m)p^5(p-1) \rightarrow f(mp^5)=f(m)p^5$. So, $p^4f(pm)=p^2f(p^3m)=f(p^5m)=p^5f(m) \rightarrow f(pm)=pf(m) (m \ge p^2)$. claim2) $f(pm)=pf(m)$ for all prime $p$ and interger $m.(p,m \ge 2)$ lets take a very big interger $M$. Then, $p2^Mf(m)=p2^{M-1}f(2m)=...=pf(2^Mm)=f(p2^Mm)=2f(2^{M-1}pm)=...=2^Mf(pm)$ since $pm \ge 2*2=2^2, 2^Mm \ge p^2$. So, $f(pm)=pf(m)$ for all prime $p$ and interger $m.(p,m \ge 2)$. claim3) the only solution is \[f(n)=\begin{cases}a\quad&n=1\\bn\quad&n>1\end{cases}\] <pf> because of claim 2, $2f(p)=f(2p)=pf(2) \rightarrow f(p)=bp (b=\frac{f(2)}{2})$. So, when $n=p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t}$ (primes $p_1,\dots,p_t$ and exponents $e_1,\dots,e_t>0$ ), $f(n)=p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t-1}f(p_t)=n*\frac{f(p_t)}{p_t}=bn$ if $n \ge 2$, and $f(1)$ can be any constant.
24.03.2021 03:28
Let \(P(m,n)\) denote the assertion. The answer is \[f(n)\equiv\begin{cases}c&n=1\\dn&n>1\end{cases}\]for constants \(c\) and \(d\). These obviously work, so we show they are the only solutions. Claim: \(f(mn)=nf(m)\) whenever \(m\ge n\). Proof. We proceed by strong induction on \(n\). In what follows, ``I-H'' refers to the inductive hypothesis, that the hypothesis holds for all positive integers less than \(n\). Observe that if \(n\) is composite, take a prime \(p\mid n\), and observe that \[f(mn)=f(mn/p\cdot p)\stackrel{\text{I-H}}=pf(mn/p)\stackrel{\text{I-H}}=p\cdot n/p\cdot f(m)=nf(m).\]Otherwise assume \(n=p\) is prime. By \(P(m,p)\), for all \(m\ge p\) we have \[f(mp^2)\stackrel{\text{I-H}}=\frac{f(mp^2(p-1))}{p-1}=\frac{f(m)\cdot p^2(p-1)}{p-1}=f(m)\cdot p^2.\tag{\(\star\)}\]Moreover, by \(P(m,p^2)\), for all \(m\ge p^2\) we have \[f(mp)\stackrel{(\star)}=\frac{f(mp^5)}{p^4}\stackrel{\text{I-H}}=\frac{f(mp^5(p-1))}{p^4(p-1)}=\frac{f(m)\cdot p^5(p-1)}{p^4(p-1)}=f(m)\cdot p.\tag{\(\dag\)}\]Finally, whenever \(m\ge p\), we have \[f(mp)\stackrel{(\dag)}=\frac{f(mp^2)}{p}\stackrel{(\star)}=\frac{f(m)\cdot p^2}p=f(m)\cdot p,\]as claimed. \(\blacksquare\) Let \(f(2)=2d\) (we will show later that \(d\) is an integer). Then repeatedly substituting \(m=2^k\) and \(n=2\) into the claim for \(k=1,2,3,\ldots\) gives \(f(2^k)=2^kd\) for all \(k\). For each \(n\ge2\), select \(k\) such that \(2^{k-1}\le n<2^k\); observe \[f(n)=\frac{f(2^{k-1}n)}{2^{k-1}}=\frac{f(2^kn)}{2^k}=\frac{f(2^k)\cdot n}{2^k}=\frac{2^kd\cdot n}{2^k}=dn.\]Evidently \(d\) must be an integer. Finally, there are no restrictions on \(f(1)\), so we are done.
19.11.2021 15:38
China TST D2 P4 wrote: Find all functions $f: \mathbb{Z}^+\rightarrow \mathbb{Z}^+$ such that for all positive integers $m,n$ with $m\ge n$, $$f(m\varphi(n^3)) = f(m)\cdot \varphi(n^3).$$Here $\varphi(n)$ denotes the number of positive integers coprime to $n$ and not exceeding $n$. If $m\geq n^2$, then $$f(m\varphi(n^6))=f(m.n^3\varphi(n^3))\implies f(m.n^3)=f(m).n^3$$ We can now get rid of the $m\geq n$(for $m,n>1$) condition. Let $m<a , m\geq b, \gcd(a,b)=1$.Take $k$ large enough such that $m.k^3 \geq ab$.Then $$k^3.f(m. \varphi(a^3))\varphi(b^3)=k^3f(m.\varphi(a^3)\varphi(b^3))= f(k^3.m \varphi(ab^3))=f(k^3m).\varphi(a^3)\varphi(b^3)=k^3f(m)\varphi(a^3)\varphi(b^3) \implies f(m. \varphi(a^3))=f(m) \varphi(a^3)$$ Also , $n=2$ gives $f(4m)=4f(m)$.Also $f(8m)=8f(m)$.Combining , we have that $f(2m)=2f(m)$ Now , $f(n\varphi(n^3))=f(n^3\varphi(n))=n^3f(\varphi(n)) \implies f(n)=n\frac{f(\varphi(n))}{\varphi(n)}$ Also , we can get that $2|f(2)$.Let $f(2)=2k$.Then using $\boxed{f(n)=n\frac{f(\varphi(n))}{\varphi(n)}}$ we can get that $f(n)=nk $ by strong induction.
13.03.2022 01:39
Solved with Ritwin and megarnie. The solutions are $\boxed{f(1) = a, f(n) = bn}$ for any positive integer constants $a,b$ and it is obvious that these work. Note that $f(32m) = 32f(m)$ for $m\ge 4$ and $f(4m) = 4f(m)$ for $m \ge 2.$ So for any $m\ge 4,$ $$32f(m) = f(32m) = 4f(8m) = 16f(2m) \implies 2f(m) = f(2m).$$But also $2f(4) = f(8) = 4f(2)$ and $2f(6) = f(12) = 4f(3)$ so in summary for any $m\ge 2$ we have $2f(m) = f(2m).$ Claim: For any prime $p,$ we have $f(pm) = pf(m)$ for all $m \ge 2.$ We prove by strong induction with base case proven above. For all $m \ge p^2,$ we have $(p-1)p^{5} f(m) = f((p-1)p^{5} m) \implies p^{5} f(m) = f(p^{5} m) $ (by inductive hypothesis) and for all $m \ge p,$ we have $(p-1)p^{2} f(m) = f((p-1)p^{2} m) \implies p^2 f(m) = f(p^2m)$ (by inductive hypothesis). So $$p^{5} f(m) = f(p^{5} m) = p^2f(p^3m) = p^4f(pm) \implies pf(m) = f(pm).$$For all $m < p^2,$ take a large power of $2,$ call this $2^c,$ then $2^c f(pm) = f(2^cpm) = pf(2^cm) = 2^cpf(m),$ finishing the inductive step. $\square$ So for any integer $n \ge 2,$ note $f(2) \cdot n = f(2n) = 2f(n)$ so we're done. $\blacksquare$
13.03.2022 05:24
Step 1. For $m\geqslant 2, f(2m)=2f(m).$ (trivial) Step 2. For a prime number $p$ and $m\geqslant p^2, f(pm)=pf(m).$ (induction) Step 3. For a prime number $p$ and any $m\geqslant 2, f(pm)=pf(m).$ (simple) Step 4. Arrive at our destination. $\square$
01.05.2022 21:51
The answer is $f(x) \equiv cx$, which clearly works. Let $P(m,n)$ be the given assertion ; $f(1) = c$ and $$ T = \{x \in \mathbb Z^+: f(x) = cx \} $$We want to show $T = \mathbb Z^+$. Call a number $y \in \mathbb Z^+$ good if $$ y = \frac{\varphi(n_1^3)\varphi(n_2^3) \cdots \varphi(n_k^3)}{\varphi(m_1^3)\varphi(m_2^3) \cdots \varphi(m_l)^3} $$for some $n_1,n_2,\ldots,n_k,m_1,m_2,\ldots,m_l \in \mathbb Z^+$. Key Claim: All good numbers are in $T$. Proof: In $P(m,n)$, it is easy to see if any of $m \varphi(n^3),m$ lies in $T$, then the other also lies in $T$. Also, $1 \in T$ by definition. Taking $m=1$ gives $$ \varphi(n^3) \in T ~~ \forall ~ n \in \mathbb Z^+ $$Then taking $m = \varphi(n_2^3)$ gives $$ \varphi(n_2^3) \varphi(n^3) \in T ~~ \forall ~ n_2,n \in \mathbb Z^+ $$Then we take $m= \varphi(n_2^3) \varphi(n_3^3)$ and so on... We obtain (by induction on $k \ge 1$) that $$ \varphi(n_1^3)\varphi(n_2^3) \cdots \varphi(n_k^3) \in T ~~ \forall ~ n_1,n_2,\ldots,n_k \in \mathbb Z^+ $$Now this time if we force $m\varphi(n^3) \in T$, then we get $$ \frac{\varphi(n_1^3)\varphi(n_2^3) \cdots \varphi(n_k^3)}{\varphi(m_1^3)} \in T ~~ n_1,n_2,\ldots,n_k,m_1 \in \mathbb Z^+$$provided the value on LHS is integral. If we keep forcing $m\varphi(n^3) \in T$, then we obtain (by induction on $l \ge 1$) that $$ \frac{\varphi(n_1^3)\varphi(n_2^3) \cdots \varphi(n_k^3)}{\varphi(m_1^3)\varphi(m_2^3) \cdots \varphi(m_l)^3} \in T ~~ \forall ~ n_1,n_2,\ldots,n_k,m_1,m_2,\ldots,m_l \in \mathbb Z^+ $$provided the value on LHS is integral. This proves our Claim. $\square$ Now it remains to show that all numbers of $\mathbb Z^+$ are good. From definition, it is easy to see product and quotient (provided its integral) of two good numbers is good. So it suffices to show all primes $p$ are good. We do this by induction on $p$. As base case, we assume $1$ to be a prime. For induction step, note $$ \varphi(p^3) = p^2(p-1) , \varphi(p^6) = p^5(p-1) ~ \text{ are good} $$Now $p-1$ is good by induction hypothesis (as all its prime factors are $<p$). Hence $$ p^2 = \frac{\varphi(p^3)}{p-1} , p^5 = \frac{\varphi(p^6)}{p-1} ~ \text{ are good}$$Finally, $$ p = \frac{p^5}{(p^2)^2} ~ \text{ is good} $$This completes the proof. $\blacksquare$
18.06.2022 15:45
EDIT: My previous post didn't finish the problem correctly. The solution set is $f(x)=cx ~\forall x\neq 1$ and $f(1)=k.$ It is easy to verify this works. Denote the assertion by $P(m,n).$ We prove two claims. Claim 1: For all $a\geq 2$ we have $2f(a)=f(2a).$ Proof. $P(a,2)$ and $P(a,4)$ respectively give $f(4a)=4f(a)$ for all $a\geq 2$ and $f(32a)=32f(a)$ for all $a\geq 4.$ It is not hard to conclude $2f(a)=f(2a)$ for all $a\geq 4.$ But since $4f(2)=f(8)=2f(4)$ and $4f(3)=f(12)=2f(6)$ our claim follows. $\blacksquare$ Claim 2: For all $a\leq b$ we have $af(b)=f(ab).$ Proof. We induct with base case $a=2$ true. Assume it is true for all smaller than $a.$ We take $a$ to be prime. \begin{align*} P(b,a) \implies & f(a^2b)=\tfrac{f(a^2b(a-1))}{a-1}=\tfrac{a^2(a-1)f(b)}{a-1}=a^2f(b) \\ P(b,a^2)\implies & f(ab)=\tfrac{f(a^5b)}{a^4}=\tfrac{ f(a^5b(a-1)}{a^4(a-1)}=\tfrac{a^5(a-1)f(b)}{a^4(a-1)}=af(b) \\ \therefore & f(ab)=\tfrac{f(a^2b)}{a}=\tfrac{a^2f(b)}{a}=af(b)\end{align*}Now if $a$ is not prime then take any prime divisor $p$ of $a$ so that $$f(ab)=f(\tfrac{ab}{p^2})=pf(\tfrac{ab}{p})= af(b).$$$\blacksquare$ It is not hard to conclude the solutions found in the beginning.
18.06.2022 15:58
squareman wrote: So for any integer $n \ge 2,$ note $f(2) \cdot n = f(2n) = 2f(n)$ so we're done. $\blacksquare$ How did you prove this for any integer while I could prove it only for primes?