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
EpicNumberTheory
22.03.2021 08:56
Let the assertion be denoted by $P(m,n)$.
$P(m,2) \implies f(4m) = 4f(m)$
$P(m,2^2) \implies f(32m) = 32f(m)$
But $f(32m) = 4f(8m) = 16f(2m) = 32f(m) \implies f(2m) = 2f(m)$
$P(m,3) \implies f(18m) = 18f(m) \implies f(9m) = 9f(m)$
$P(m,3^2) \implies f(m \cdot 2 \cdot 3^5) = 2 \cdot 3^5 \cdot f(m) \implies f(m \cdot 3^5) = 3^5 \cdot f(m)$
But $f(9m) = 9f(m) \implies f(3^5m) = 3^4f(3m) = 3^5f(3m) \implies f(3m) = 3f(m)$
By a similar (strong) induction hypothesis we can prove that $f(m) = km$ for any constant $k \in \mathbb{Z}^+$ which works. Strong Induction:
First of all:
$P(m,p) \implies f(m p^2(p-1)) = f(m) p^2(p-1)$
$P(m,p^2) \implies f(mp^5(p-1) = f(m)p^5(p-1) = f(m p^3) p^2(p-1) = f(m) p^5(p-1) \implies f(m p^3) = f(m)p^3$
$P(mp,p) \implies f(mp^3(p-1)) = f(mp) p^2(p-1) = f(m(p-1))p = f(mp)(p-1) \implies f(m)p = f(mp)$ (For any prime $p$). Here $f(m(p-1)) = f(m)(p-1)$ due to strong induction since $p-1$ is made of primes less than $p$. Lets begin the strong induction:
Let $a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \dots$
$P(m,a) \implies f(m \phi(a^3)) = \phi(a^3)f(m)$
Now $\phi(a^3) = p_1^{3\alpha_1-1} \cdot p_2^{3\alpha_2-1} \cdot p_3^{3\alpha_3-1} \dots\cdot A$. Now here $A$ is a product of numbers less than $a$ and so can be 'flushed off' (Like in $f(km) = kf(m)$). Let $\mathcal{M} = p_1^{3\alpha_1-1} \cdot p_2^{3\alpha_2-1} \cdot p_3^{3\alpha_3-1}$
So we would have $f(m)\phi(a^3) = f(m)\mathcal{M}A = f(\phi(a^3)m) = f(A\mathcal{M}f(m)) = Af(\mathcal{M}m) \implies f(m)\mathcal{M} = f(\mathcal{M}m)$
$P(m,a^2) \implies f(m \phi(a^6)) = \phi(a^6) f(m)$
$\phi(a^6) \implies p_1^{6\alpha_1-1} \cdot p_2^{6\alpha_2-1} \cdot p_3^{6\alpha_3-1} \dots \cdot A_1$ (Here again $A_1$ is a product of numbers smaller than $a$). Let $\mathcal{P} = p_1^{6\alpha_1-1} \cdot p_2^{6\alpha_2-1} \cdot p_3^{6\alpha_3-1} \dots$
(Here too the $\phi(a^3) = \mathcal{P} \cdot A_1$ and $A_1$ is a product of numbers less than $a$ and can be similarly 'flushed off'.)
So $f(m \phi(a^6))= f(m \mathcal{P} A_1) = A_1 f(\mathcal{P} m) = A_1 f(\mathcal{M}^2 \cdot p_1p_2p_3 \dots m) \implies \mathcal{P} f(m) = \mathcal{M}^2 f(p_1p_2p_3 \dots m) \implies p_1p_2p_3 \dots f(m) = f(m p_1p_2p_3 \dots)$.
So taking $m$ to be a new prime $p$ we get $p_1p_2p_3 \dots f(p) = pp_1p_2p_3 \dots f(1)= f(pp_1p_2p_3 \dots)$
Hence our strong induction hypothesis is complete. $\blacksquare$. So we have $f(t) = kt$ for any squarefree $t$. But this is enough because every number is the product of some positive integer $s$ and a squarefree number $t$. So $f(n) = f(ts) = f(s)t = f(t_1s_1)t = f(s_1)tt_1 = \dots = nf(1)$
But since $f(1)$ occurs only in $f(m) = mf(1)$ and $P(1,1)$. By $f(m) = mf(1)$, f(1) could be any constant. But by $P(1,1)$ could be anything ($f(1) = f(1)$). So the solutions can be:
$f(m) = km$ for all positive integers $m$ except $1$ for any positive integer constant $k$ and $f(1)$ any (possibly distinct) constant.
nukelauncher
22.03.2021 09:07
Claim: $f(2m)=2f(m)$ for all $m\geq 2$.
Proof. Note that $n=2,4$ give that for $m\geq 2$, $f(4m)=4f(m)$ and for $m\geq 4$, $f(32m)=32f(m)$. Then for $m\geq 4$, we have \[32f(m)=f(32m)=4f(8m)=16f(2m)\implies f(2m)=2f(m).\]We also have $2f(4)=f(8)=4f(2)\implies f(4)=2f(2)$ and $2f(6)=f(12)=4f(3)\implies f(6)=2f(3)$. This proves the claim. $\blacksquare$
Claim: $f(pm)=pf(m)$ for all primes $p$ and all $m\geq p^2$.
Proof. Strong induct on $p$. Suppose the claim is true for all primes $p'<p$. The base case $p=2$ has been proven earlier. Then note that $n=p,p^2$ give that for $m\geq p$, $f(p^2(p-1)m)=p^2(p-1)f(m)$ and for $m\geq p^2$, $f(p^5(p-1)m)=p^5(p-1)f(m)$. Then for $m\geq p^2$, we have \[p^5(p-1)f(m)=f(p^5(p-1)m)=p^2(p-1)f(p^3m)\implies f(p^3m)=p^3f(m).\]We also have for $m\geq p^2$ that (I.H. stands for inductive hypothesis, since all prime factors of $p-1$ are less than $p$) \[p^2(p-1)f(m)=f(p^2(p-1)m)\stackrel{\text{I.H.}}=(p-1)f(p^2m)\implies f(p^2m)=p^2f(m).\]Finally, combine the 2 equations to get that for all $m\geq p^2$, we have \[p^2f(pm)=f(p^3m)=p^3f(m)\implies f(pm)=pf(m),\]as desired. $\blacksquare$
Claim: $f(pm)=pf(m)$ for all $m\geq 2$.
Proof. Note that for any $m\geq 2$, we have \[2^pf(pm)=f(p\cdot(2^pm))=pf(2^pm)=p\cdot 2^pf(m)\implies f(pm)=pf(m).\quad\blacksquare\]
Now this gives for any primes $p,q$ that \[f(pq)=pf(q)=qf(p)\implies \frac{f(p)}p=c_2\]for some constant $c_2\in\mathbb N$. Finally, we have $f(1)$ can be anything (since the only way for 1 to appear in the FE gives a tautology) and for $n>1$, write $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ for primes $p_1,\dots,p_k$ and exponents $e_1,\dots,e_k>0$ to get \[f(n)=p_1^{e_1-1}p_2^{e_2}\cdots p_k^{e_k}f(p_1)=c_2n.\]Thus, our solution set is \[f(n)=\begin{cases}c_1\quad&n=1\\c_2n\quad&n>1\end{cases}\]for some constants $c_1,c_2\in\mathbb N$. These can be easily checked to work.
KPBY0507
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.
TheUltimate123
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.
SPHS1234
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.
squareman
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$
JG666
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$
guptaamitu1
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$
ZETA_in_olympiad
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.
ZETA_in_olympiad
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?