Find all functions $f : Z \to Z$ satisfying $\bullet$ $ f(p) > 0$ for all prime numbers $p$, $\bullet$ $p| (f(x) + f(p))^{f(p)}- x$ for all $x \in Z$ and all prime numbers $p$.
Problem
Source: Dutch IMO TST2 2019 p4
Tags: number theory, function, Find all functions, prime numbers, functional equation
11.01.2020 16:29
The only solution is $f(x)=x$. Take $x=p$, where $p$ is an odd prime. to get that $p\mid 2^{f(p)}f(p)^{f(p)} \implies p\mid f(p)$ for all odd primes. Assume that $2\nmid f(2)$, if $f(2)\neq 1$ then let $q$ be an odd prime divisor of $f(2)$, we have from the second condition that $q\mid (f(2)+f(q))^{f(q)}-2 \implies q\mid 2$ which is a contradiction, hence in this case we must have that $f(2)=1$, but taking $x=2$ in the second conditon we get that $p \mid -1$ for all odd primes which again is not true, hence we're left with $2\mid f(2)$. Now, it is not hard to show by contradiction that for any two primes $p,q$ we have $p\nmid f(q)$ and $q\nmid f(p)$, hence $f(p)=p^{\alpha_p}$ where $\alpha_p$ is a natural number depenent on $p$. Fix $x$ any non-zero integer, then using Fermat's Little Theorem and the fact that $\gcd(x,p)=1 \implies \gcd(f(x),f(p))=1$ we have $p\mid f(x)-x$ for all primes such that $\gcd(p,x)=1$ which is possible iff $f(x)=x$, and if we fix $x=0$ a similar reasoning will give $f(0)=0$, which finishes the proof.
29.03.2021 02:37
Not sure if this is correct but posting it anyway. The only answer if $f(x)=x$. Let $p$ be a prime number greater than $2$.Then we must have that $p \mid \left( 2f(p) \right)^{f(p)}$, which must imply that $p \mid f(p)$, this all stems from setting $x=p$. This implies that $f(p)=pg(p)$., where $g: \mathbb{P} \rightarrow \mathbb{Z}^{+}$. Then we surely must have that: $$p \mid f(x)^{f(p)}-x$$which clearly implies that $f(x)^{f(p)} \equiv x \pmod{p}$. Thus we must clearly have, by FLT, that $f(x)^{g(p)} \equiv x \pmod{p}$. Now notice that $f(1)^{g(p)},f(2)^{g(2)}\dots,f(p)^{g(p)}$ forms a complete residue system for any prime $p$, $\pmod{p}$. Also they must be in an increasing order. So since this needs to hold for all primes $p$, then we must have that $g(p) \equiv 1 \pmod{\varphi (p)}$ Thus we have that $f(x)^{g(p)} \equiv f(x) \equiv x \pmod{p}$. Now we just choose a prime number $p$ such that $p > f(x)$. Thus we must have that $f(x)=x$, since we have $\infty$ many primes for which the relation $p > f(x)$ holds.
28.04.2021 19:03
parmenides51 wrote: Find all functions $f : Z \to Z$ satisfying $\bullet$ $ f(p) > 0$ for all prime numbers $p$, $\bullet$ $p| (f(x) + f(p))^{f(p)}- x$ for all $x \in Z$ and all prime numbers $p$. Let $x=p$ then $p|(2f(p))^{f(p)}$ so $p|f(p)$ or $p=2$. For $x=0$ and every odd prime $p$ we have $p|f(0)$ so $f(0)=0$ For $x=0$ and $p=2$ we get $2|f(2)$ so $p|f(p)$ for all primes. So $p|f(x)^{f(p)}-x$ Take $x=prime$ different from $p$ it is obviously that we get $f(p)$ is a power of $p$. Otherwise suppose that this is not true take $p$ such that $p|f(x)$ then we have $p|x$ contradiction. Now by Fermat little theory we have that $n^{p^{m}}=n(mod p)$. This means that $p|f(x)-x$.For all primes $p$ so $f(x)=x$.
08.07.2021 12:21
We claim that the only function satisfying these conditions is $f(n) = n$ for all integers $n$. Let $P(n,p)$ denote the assertion $p \mid (f(x)+f(p))^{f(p)} - x$. Firstly, $P(p,p)$ for arbitrary odd prime $p$ gives us $ p \mid (2f(p))^{f(p)} - p \iff p \mid f(p)$. Next, $P(0,p)$ gives us that $p \mid f(0)$ for all odd primes $p$, thus $f(0)=0$. Now, $P(0,2)$ gives us $2 \mid f(2)$. Hence we have $p \mid f(p)$ for all primes $p$. Claim 1: For any prime $p$, $f(p)$ cannot have any prime factor which is not $p$. Proof: Assume contrariwise. Suppose $q \mid f(p)$, where $q \neq p$. Now, $P(p,q)$ gives us that $q \mid (f(p)+f(q))^{f(q)} - p \iff q \mid -p$, as $q\mid f(p)$ and $q \mid f(q)$. This is clearly a contradiction. Now, this implies that for all primes $p$, $f(p) = p^k$ with $k \geq 1$. Fix any prime $p$. $P(n,p)$ gives us $p \mid (f(n)+f(p))^{f(p)} - n \iff p \mid f(n)^{p^k} - n \iff p \mid f(n) - n$ by Fermat's Little Theorem. Hence the main condition has relaxed to $p \mid f(n)-n$ for all primes $p$, which immediately yields $f(n) = n$ for all $n \in \mathbb{Z}$.
19.03.2022 03:26
$f(x)=x$ only which works. Let $A(x,p)$ denote the second assertion. Unless otherwise specified, $p$ denotes a prime throughout this solution. I claim that $p \mid f(p)$. From $A(p,p)$ we get $p \mid 2f(p)$; for odd $p$ this implies $p \mid f(p)$. Now suppose $f(2)$ is odd, from which we find that $f(x)$ is always the opposite parity of $x$. In particular $f(3)$ is even, so $(f(2)+f(3))^{f(3)}$ is a square mod $3$, but it is also $2 \pmod{3}$, contradiction. Therefore $f(2)$ is even, so $p \mid f(p)$ for all primes $p$. Now, if some prime $q \neq p$ divides $f(p)$ for some $p$, from $A(p,q)$ we get $$q \mid (f(p)+f(q))^{f(q)}-p \implies q \mid -p,$$which is absurd. Thus $f(p)$ must equal a power of $p$. We can easily get $p^k \equiv 1 \pmod{p-1}$ for all $k$, so $A(x,p)$ gives $$x \equiv (f(x)+f(p))^{f(p)} \equiv f(x)^{f(p)} \equiv f(x) \pmod{p}$$by Fermat's Little Theorem, so every prime divides $f(x)-x$, implying that it equals $0$. This gives $f(x)=x$ for all $x$ as desired. $\blacksquare$
01.04.2022 16:01
We claim the answer is $f(x) = x$, which works by Fermat's little theorem. Let $P(x,p)$ be the proposition \[p| (f(x) + f(p))^{f(p)}- x.\]Then, \[P(p,p): f(p) \equiv -f(p) \pmod p,\]so $p\mid f(p)$ for all odd primes $p$. \[P(0,p): 0\equiv f(p) \equiv -f(0) \pmod p,\]so $f(0) = 0$. In particular, we get by $P(0,p)$ that $2\mid f(2)$. Claim 1: for all $x\not \equiv y \pmod p$ ; $x,y \in \{1,2,...,p\}$, \[f(x) \not \equiv f(y) \pmod p.\]Proof: Note that $(f(x) + f(p))^{f(p)}$ is surjective $\pmod p$ for $x\in \{1,2,...,p\}$. This implies that $f(x)$ (restrained to $\{1,2,...,p\}$) is surjective on $\mathbb Z /p \mathbb Z$, and since the domain and the image have the same size, $f$ must be a bijection. Claim 2: If $a^k \equiv b^k \pmod p$ and $\gcd (k,p-1) = 1$, $a\equiv b \pmod p$. Proof: Let $g$ be a primitive root $\pmod p$, and $x,y$ be such that $a\equiv g^x, b\equiv g^y \pmod p$. Then, $kx \equiv ky \pmod {p-1}$, so $x\equiv y \pmod {p-1}$, therefore $a\equiv b \pmod p$. Claim 3: $d = \gcd(f(p),p-1) = 1$. Proof: If not, $(f(x)+f(p))^{f(p)} \equiv g^{d.y} \pmod p$, which is not surjective $\pmod p$ Claim 4: If $a \equiv b \pmod p$, $f(a)\equiv f(b) \pmod p$. Proof: \[ (f(a)+f(p))^{f(p)} \equiv a \equiv b \equiv (f(b)+f(p))^{f(p)} \pmod p, \]and we conclude by using claims 3 and 2. \[P(x^{f(p)},p)\implies f(x^{f(p)}) \equiv x \equiv f(x)^{f(p)} \pmod p\]\[P(x^{f(p)^{\varphi(p-1)-1}},p)\implies f(x) \equiv x^{f(p)^{\varphi(p-1)-1}} \pmod p \]\[\implies f(ab)\equiv f(a)f(b) \pmod p \forall a,b \]\[\implies f(ab) = f(a)f(b).\]Note that, since $p\mid f(p)$, this implies that $n\mid f(n)$ for all nonzero $n$, and $f(p)>0$ implies that $f(n)>0$ for all $n>0$. Claim 5: $f(n) = n$ for all $n \le 1$. Proof: We proceed by induction. Base case: $f(1) = 1$. Suppose $n\ge 2$ is minimal such that $f(n)\ne n$. Then, $f(n) \ge 2n$. Let $p$ be a prime dividing $f(n) - n +1$. Then $f(n) \equiv f(n-1) \pmod p$, a contradiction by claims 4 and 1. Note that $f(-1) \equiv f((-1)^{f(p)})\equiv -1 \pmod p$, so $f(-1) = -1$, so $f(-x) = f(-1)f(x) = -f(x)$. This concludes the proof that $f(x) = x$ for all $x$.