Euler totient and functional equation

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Euler totient and functional equation

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: 2024 Turkey EGMO TST P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

82 posts

#1 h Feb 12, 2024, 7:22 AM • 1 Y

Y by Kimchiks926

Find all functions $f:\mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+}$ such that the conditions

$\quad a) \quad a-b \mid f(a)-f(b)$ for all $a\neq b$ and $a,b \in \mathbb{Z}^{+}$

$\quad b) \quad f(\varphi(a))=\varphi(f(a))$ for all $a \in \mathbb{Z}^{+}$ where $\varphi$ is the Euler's totient function.

holds

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

116 posts

Iveela

#2 h Feb 12, 2024, 9:40 AM

Y by

The answers are $f(x) \equiv 1$ and $f(x) \equiv x$ .

The condition implies that $f(1) = f(\varphi(1)) = \varphi (f(1))$ and hence $f(1)=1$ . Then $\varphi (f(2)) = f( \varphi (2)) = f(1)= 1$ . Hence, $f(2) \leq 2$ .
Case 1: $f(2)=1$ .
We prove by strong induction that $f(k)=1$ for all $k \in \mathbb{Z}^+$ . Note that $\varphi(k) < k$ and hence by induction $f(\varphi(k))=1=\varphi(f(k))$ which implies that $f(k) \leq 2$ . Suppose that $f(k)=2$ . Then the condition implies that $k-(k-2)= 2 \mid f(k)-f(k-2) = 1$ , a contradiction. $\square$
Case 2: $f(2)=2$ .
Again, we prove by strong induction that $f(k)=k$ for all $k \in \mathbb{Z}^+$ . Assume the contrary. We have $k - a \mid f(k) - a \implies k - a \mid f(k) - k$ for all $a < k$ .
Suppose that $k \in \mathbb{P}$ . Then it follows from $k-1 \mid f(k)-1$ that $2 \nmid f(k)$ . Hence, letting $f(k)=p_1^{\alpha_1}p_2^{\alpha_2} \dots p_n^{\alpha_n}$ , we have $\varphi(f(k)) = (p_1-1)p_1^{\alpha_1-1} \cdot \dots \cdot (p_n-1)p_n^{\alpha_n-1} \geq \sqrt{2f(k)}$ whenever $f(k)>3$ . Recall that $k-1 \mid f(k)-k$ and $k-2 \mid f(k)-k$ which implies that $(k-1)(k-2) \mid f(k)-k \implies \frac{k^2}{2} < k^2-2k+2 \leq f(k)$ . Hence, $\varphi(f(k)) \geq \sqrt{2f(k)} > k$ , a contradiction.
Now, suppose that $k \notin \mathbb{P}$ . Since every positive integer smaller than $k$ divides $f(k)-k$ , we must have $k \mid f(k)$ . It follows that $\varphi(f(k)) > \varphi(k)$ unless $f(k)=k$ so we're done. $\blacksquare$

This post has been edited 3 times. Last edited by Iveela, Feb 12, 2024, 9:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

666 posts

#3 h Feb 12, 2024, 5:04 PM

Y by

$a-b|f(a)-f(b)$
$f(\phi(a))=\phi(f(a))$
Let $P(a,b)$ be the assertion on $a-b|f(a)-f(b)$
Let $Q(a)$ be the assertion on $f(\phi(a))=\phi(f(a))$
$Q(1)\implies f(1)=f((\phi(1)))=\phi(f(1))\implies \boxed{f(1)=1}$
$P(a,1)\implies a-1|f(a)-1$
$Q(2)\implies 1=f(\phi(2))=\phi(f(2))\implies f(2)\in \{1,2\}$

$i)$ If $f(2)=1$
Let $f(2^k)=1$ for $k=1,2,...,n$ We'll prove that $f(2^{n+1})=1$ by induction.
$Q(2^{n+1})\implies 1=f(2^{n})=f(\phi(2^{n+1}))=\phi(f(2^{n+1}))$
So $f(2^{n+1})\in \{1,2\}$
$P(2^{n+1},2^n)\implies 2^n|f(2^{n+1})-1$
We know that $n\geq 1$ so $f(2^{n+1})\neq 2$ which means that $f(2^{n+1})=1$

$P(2^n,b)\implies 2^n-b|1-f(b)$
We can take $n$ to positive infinity so $f(b)=1$
In this case, we have the solution $\boxed{f\equiv 1}$

$ii)$ If $f(2)=2$
$Q(3)\implies 2=\phi(f(3))\implies f(3)\in \{3,4,6\}$
$P(3,1)\implies 2|f(3)-1\implies \boxed{f(3)=3}$
We'll prove that $f(n)=n$ by induction.
Let $f(k)=k$ for $k=1,2,...,n-1$
Let $k=p_1^{\alpha_1}...p_m^{\alpha_m}$

$\rule{430pt}{1pt}$
Claim: $k|f(k)$ if $k\neq p^{\alpha}$
Proof: By induction, we have $k-m|f(k)-m+m-k=f(k)-k$ so $k-m|f(k)-k$ for all $m\in[1,k-1].$
$p_1^{\alpha_1},...,p_m^{\alpha_m}<k$ so $p_i^{\alpha_i}|p_1^{\alpha_1}...p_m^{\alpha_m}-p_i^{\alpha_i}|f(k)-p_1^{\alpha_1}...p_m^{\alpha_m}\implies p_i^{\alpha_i}|f(k)\implies k|f(k)$
$\rule{430pt}{1pt}$
$Q(k)\implies \phi(k)=f(\phi(k))=\phi(f(k))$
$p_1^{\alpha_1-1}...p_m^{\alpha_m-1}(p_1-1)...(p_m-1)= \phi(k)=\phi(f(k))=\phi(p_1^{\alpha_1}...p_m^{\alpha_m}T)$
We can see that if $T\geq 2$ , then $RHS>LHS$ .
If $k$ has at least two distinct prime divisors, then $f(k)=k$ by induction.

If $k=p^{\alpha}$ , then $p^{\alpha-1}(p-1)=\phi(f(p^{\alpha}))$
$P(p^{\alpha},p^{\alpha-1})\implies p^{\alpha-1}|f(p^{\alpha})$
$P(p^{\alpha},p^{\alpha}-q)\implies q=p^{\alpha}-(p^{\alpha}-q)|f(p^{\alpha})-p^{\alpha}$ which gives that $f(p^{\alpha})$ has no prime divisor other than $p$ .
$f(p^{\alpha})$ is a power of $p$ so $f(p^{\alpha})=p^{\alpha}$
By induction, we get that $\boxed{f(n)=n}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10 posts

#4 h Feb 22, 2024, 10:18 AM

Y by

It is obvious that the functions $f(x) \equiv 1$ and $f(x) = x$ satisfy the given equation. Now, we will prove that these are the only solutions. Let $P(a, b)$ denote the assertion $a-b \mid f(a) - f(b)$ and $Q(a)$ denote the assertion $f(\varphi(a)) = \varphi(f(a))$ .
$\begin{align*} Q(1)&: f(1) = \varphi(f(1)) \implies f(1) = 1 \\ Q(2)&: \varphi(f(2)) = f(1) = 1 \implies f(2) = 1 \text{ or } 2. \end{align*}$ Consider the case when $f(2) = 1$ . Suppose $f(1) = f(2) = \cdots = f(k) = 1$ for some $k \geq 2$ . Then,
$\begin{align*} Q(k+1): \varphi(f(k+1)) = f(\varphi(k+1)) =1 \implies f(k+1) = 1 \text{ or } 2. \end{align*}$ But if $f(k+1) = 2$ , then $P(k+1, 1)$ gives $k\mid 1$ which contradicts $k \geq 2$ . Thus, $f(k+1) = 1$ . By mathematical induction, $f(n) = 1$ for all $n$ in this case.
Now, suppose $f(2) = 2$ . Assume $f(a) = a$ for all $1\leq a < k$ for some $k \geq 3$ . For such $a$ ,
$k - a \mid f(k) - a \implies k-a \mid f(k) - k.$ Thus, $a \mid f(k) - k$ for all $1\leq a < k$ . Observe that if $\gcd(a, k) = 1$ , then $\gcd(a, f(k)) = 1$ . Moreover, $\gcd(f(k), f(k) - 1) = 1$ . This shows that $\varphi(f(k)) \geq \varphi(k) + 1$ if $f(k) > k$ . On the other hand, $Q(k)$ yields $\varphi(f(k)) = f(\varphi(k)) = \varphi(k)$ . Thus, we must have $f(k) \leq k$ . If $f(k) = 1$ , then $k-2 \mid k-1$ . This is possible only when $k=3$ . However, this would imply that
$Q(3): 1 =\varphi(f(3)) = f(\varphi(3)) = 2$ which is absurd. Thus,
$P(k, 1): k-1 \mid f(k) - 1 \implies f(k) \geq k.$ Hence, we must have $f(k) = k$ , and the inductive proof is complete.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#5 h Mar 23, 2025, 12:26 PM • 1 Y

Y by Kaus_sgr

We will prove the only solutions are $\boxed{f(n)=1}$ and $\boxed{f(n)=n}$
Plug in $a=1$ in the second condition, we have: $\varphi{(f(1))}=f(\varphi{(1)})=f(1)$ , implying $f(1)=1$ . Now setting $a=2$ in the same condition, we get $\varphi(f(2))=f(\varphi(2))=f(1)=1$ so $f(2)\in \{1,2\}$ .

Case 1: $f(2)=1$ . We will now prove by induction that $f\equiv 1$ .
Suppose $f(y)=1, \forall y \leq x-1$ , and we aim to prove $f(x)=1$ . First of all, by the second condition, $f(x)\in \{1,2\}$ . But, if $f(x)=2$ , by the first condition $x-1\mid 1$ which is clearly a contradiction. So $f(x)=1, \forall x \in \mathbb{N}$ , as desired.

Case 2: $f(2)=2$ . We will prove by induction that $f(x)=x, \forall x \in \mathbb{N}$ .
Suppose $f(y)=y, \forall y \leq x-1$ , and we aim to prove $f(x)=x$
Let $x=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ . We will casework based on the value of $k$ .

Case 2.1: $k\geq 2$ . Then $p_i^{e_i} \leq x-1, \forall 1 \leq i \leq k$ . In the first condition setting $a=x$ , $b=p_i^{e_i}$ gives: $x-p_i^{e_i}\mid f(x)-p_i^{e_i}$ therefore $p_i^{e_i}\mid f(x), \forall 1\leq i \leq k$ . So $f(x)=\prod_{i=1}^{k}p_i^{a_i}\cdot Q$ where $(Q,p_i)=1, \forall 1\leq i \leq k$ and $a_i \geq e_i, \forall 1\leq i\leq k$ . So $\varphi(f(x))=\varphi(\prod_{i=1}^{k}p_i^{a_i})\cdot \varphi(Q) \geq \varphi(x)=f(\varphi(x))$ , equality being achieved when $a_i=e_i,\forall 1\leq i\leq k$ and $\varphi(Q)=1\iff Q\in \{1,2\}$ .
Now if $p_1=2$ then $Q$ has to be $1$ so we are done. Otherwise, if $x$ is odd, $f(x)$ is either $x$ or $2x$ . But if $f(x)=2x$ , then by setting $b=1$ in the first condition we have that $x-1\mid 2x-1$ which is clearly a contradiction. So $f(x)=x$ , as desired.

Case 2.2: $k=1$ . Therefore $x=p^e$ .
$\bullet$ If $e >1$ then setting $a=x$ and $b=p^{e-1}$ in the first condition gives $f(p^e)\equiv 0(\mod p^{e-1})$ so $f(p^e)=p^{\varepsilon}\cdot M$ , where $\varepsilon \geq e-1$ and $(M,p)=1$ By the second condition, we have: $p^{e-1}(p-1)=\varphi(M)\cdot p^{\varepsilon-1}(p-1)$ implying that $\varepsilon$ is either $e$ or $e-1$ .
Case 1: $\varepsilon=e-1$ then $\varphi(M)=p$ so $M\geq 3$ . But for $n\geq 3$ , $\varphi(n)$ is even so $p=2$ , implying $M=3$ because $(M,p)=1$ . By plugging $b=1$ in the first condition, we can check it gives a contradiction.
Case 2: $\varepsilon=e$ can be treated as case $1$ and it will give $f(x)=x$ , as desired.

$\bullet$ If $e=1$ then $x=p$ , a prime. Suppose $p$ is large enough(we can check first few cases by hand).
For $(a,b)=(p,1): p-1\mid f(p)-1$ , so $f(p)=k(p-1)+1$ .
For $(a,b)=(p,2): p-2 \mid k(p-1)-1$ so $k\equiv 1(\mod p-2)$ . Similarly, $2k\equiv 2(\mod p-3)$ . If $k\neq 1$ we can check $k=p-1$ or $k=2p-1$ don't work, so $f(p)>2(p-1)^2$ . But $\varphi(f(p))=p-1>\sqrt{\frac{f(p)}{2}}>p-1=\varphi(p)$ , contradiction.

We have exhausted all the cases, therefore the induction is complete. $\blacksquare$

This post has been edited 1 time. Last edited by ravengsd, Monday at 12:50 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a