Find all functions $f : \mathbb{Z}\rightarrow \mathbb{Z}$ such that for all prime $p$ the following condition holds: $$p \mid ab + bc + ca \iff p \mid f(a)f(b) + f(b)f(c) + f(c)f(a)$$ Proposed by Anzo Teh Zhao Yang
Problem
Source: Malaysian IMO TST 2022 P5
Tags: number theory
CANBANKAN
14.05.2022 01:42
Prove $p\nmid f(n+1)-f(n) \rightarrow |f(n+1)-f(n)|=1$, and $f$ is injective, done.
TYT
14.05.2022 01:51
How do you prove that $p \nmid f(n + 1) - f(n)$?
gghx
14.05.2022 02:24
Really bashy solution because I couldn't find anything better: We claim that the only solutions are $f(n)\equiv n$ and $f(n)\equiv -n$. Indeed, both solutions work because $f(a)f(b)+f(b)f(c)+f(c)f(a)=ab+bc+ca$. We now show that they are the only solutions. Note that we have the condition $ab+bc+ca=0$ implies $f(a)f(b)+f(b)f(c)+f(c)f(a)=0$ $(\star)$. This is because any prime divides $0$, and the only number that is divisible by every prime is $0$. In particular, taking $a=b=c=0$ in $(\star)$ implies $3f(0)^2=0$ so $f(0)=0$. Now, taking $a=0$, $b=c$ in the original equation gives $p|b^2\iff p|f(b)^2$, so $p|b\iff p|f(b)$. (this implies injectivity at 0) In particular, $f(1)$ is $1$ or $-1$. Note that if $f$ is a solution, so is $-f$, so WLOG $f(1)=1$. If $f(-1)=1$, then taking $a=b=1,c=-1$ gives $p|-1\iff p|3$, which is false. Thus, $f(-1)=-1$. Taking $a=b=2n,c=-n$ in $(\star)$ gives $2f(-n)f(2n)+f(2n)^2=0$. For $n\ne 0$, we get $f(2n)=-2f(-n)$, which is obviously true for $n=0$ as well. Thus, this gives $f(4n)=-2f(-2n)=4f(n)$. Taking $a=4n, b=12n, c=-3n$ in $(\star)$ gives $f(4n)f(12n)+f(4n)f(-3n)+f(12n)f(-3n)=0$. Thus, $16f(n)f(3n)+4f(n)f(-3n)+4f(3n)f(-3n)=0$, or $4f(n)f(3n)+f(n)f(-3n)+f(3n)f(-3n)=0$. $(1)$ Taking $a=3n, b=6n, c=-2n$ in $(\star)$ gives $f(3n)f(6n)+f(3n)f(-2n)+f(-2n)f(6n)=0$. Thus, $-2f(3n)f(-3n)-2f(3n)f(n)+4f(n)f(-3n)=0$, or $2f(n)f(-3n)-f(-3n)f(3n)-f(3n)f(n)=0$. $(2)$. Adding $(1)$ and $(2)$ gives $3f(n)f(3n)+3f(n)f(-3n)=0$, so $f(3n)=f(-3n)$ for $n\ne 0$, obviously true for $n=0$ as well. From $(2)$, this gives $-3f(n)f(3n)+f(3n)^2$, so $f(3n)=3f(n)$ for $n\ne 0$, obviously true for $n=0$ as well. Thus, $6f(-n)=2f(-3n)=-f(6n)=f(-6n)=-2f(3n)=-6f(n)$. This means $f(-n)=-f(n)$. We now induct on $k$ to show that $f(kn)=kf(n)$ for all $n$, with base cases $k=1,2,3,4$ proven above. ($f(2n)=-2f(-n)=2f(n)$). Suppose it is true for $k-1$. Then, using $a=kn, b=k(k-1)n, c=-(k-1)n$ in $(\star)$, $f(kn)f(k(k-1)n)+f(kn)f(-(k-1)n)+f(k(k-1)n)f(-(k-1)n)=0$. From the induction hypothesis, $(k-1)f(kn)^2-(k-1)f(kn)f(n)-(k-1)^2f(kn)f(n)=0$. This simplifies to $f(kn)^2-kf(kn)f(n)=0$. Thus, $f(kn)=kf(n)$ for all $n\ne 0$, obviously true for $n=0$ as well. This completes the induction. Hence, $f(t)=tf(1)=t$ for all $t$. Removing the WLOG on $f(1)=1$, we get that the only solutions are $f(n)\equiv n$ and $f(n)\equiv -n$, as claimed.
CANBANKAN
14.05.2022 02:38
TYT wrote: How do you prove that $p \nmid f(n + 1) - f(n)$? Clearly f(even) is even and f(odd) is odd; for other (odd) primes, compare $P(a,b,n), P(a,b,n+1)$ where $p|ab+(a+b)n$ and $p\nmid a+b$ (or $p\nmid ab$) to see $p\nmid ab+(a+b)(n+1)$ but $p|f(a)f(b)+(f(a)+f(b))f(n)$ implies $p|f(a)f(b) + (f(a)+f(b))f(n+1)$ as $p\mid f(n+1)-f(n)$. Proving existence of such $a,b$ is not hard.
Anzoteh
14.05.2022 03:51
If you spot some relation with IMO 2012 Problem 4, you're exactly right: this proposal was motivated by the IMO problem, though it wasn't even shown to many people until it was used as the Malaysian TST (yes, after 10 years).
Kei0923
14.05.2022 04:15
Let $P(a,b,c)$ denote the given assertion. If $f$ satisfies the condition, then $-f$ also satisfies the condition thus it suffices to consider the case which is $f(1)\geq 0$. $$P(0,0,0)\Rightarrow (p\ |\ 0 \Leftrightarrow p\ |\ 3f(0)^2)\Rightarrow 3f(0)^2=0\Rightarrow f(0)=0.$$$$P(1,1,0)\Rightarrow (p\ |\ 1 \Leftrightarrow p\ |\ f(1)^2)\Rightarrow f(1)^2=1\Rightarrow f(1)=1.$$ lemma. $f(\dfrac{q-1}{2})=\dfrac{q-1}{2}$ for every primes $q$ proof. $P(\dfrac{q-1}{2},1,0)$ gives $$p\ |\ \dfrac{q-1}{2}\Leftrightarrow p\ |\ f(\dfrac{q-1}{2})\cdots (\#)$$$$P(\dfrac{q-1}{2},1,1)\Rightarrow (p=q\Leftrightarrow p\ |\ q\Leftrightarrow p\ |\ 2f(\dfrac{q-1}{2})+1),$$means that there exists positive integer $s$ such that $|2f(\dfrac{q-1}{2})+1|=q^s$. Case1. $2f(\dfrac{q-1}{2})+1=-q^s$. Then $f(\dfrac{q-1}{2})=-\dfrac{q^s+1}{2}$. Notice that $\dfrac{q-1}{2}$ divides $\dfrac{q^s-1}{2}$, we get $$\gcd(\dfrac{q-1}{2},-\dfrac{q^s+1}{2})=\gcd(\dfrac{q-1}{2},-\dfrac{q^s+1}{2}+\dfrac{q^s-1}{2})=\gcd(\dfrac{q-1}{2},-1)=1$$but it contradicts with $(\#)$. Case2. $2f(\dfrac{q-1}{2})+1=q^s$. Then $f(\dfrac{q-1}{2})=\dfrac{q^s-1}{2}$. Suppose now that $s=2$. We get $p\ |\ \dfrac{q-1}{2}\Leftrightarrow p\ |\ \dfrac{q+1}{2}(q-1)$ but $$\gcd(\dfrac{q-1}{2},\dfrac{q+1}{2})=\gcd(\dfrac{q-1}{2},\dfrac{q+1}{2}-\dfrac{q-1}{2})=\gcd(\dfrac{q-1}{2},1)=1$$so it's a contradiction. If $s\geq 3,$ by Zsigmondy's theorem there exists prime divisor $p_1\neq 2$ of $\dfrac{q^s-1}{2}$ such that does not divide $\dfrac{q-1}{2}$ but it contradicts with $(\#)$. Hence $s=1$ and $f(\dfrac{q-1}{2})=\dfrac{q-1}{2}$, as desired. Let $q\geq 5$ be a prime. $$P(\dfrac{q-1}{2},1,a)\Rightarrow\left(p\ |\ \dfrac{q+1}{2}a+\dfrac{q-1}{2}\Leftrightarrow p\ |\ \dfrac{q+1}{2}f(a)+\dfrac{q-1}{2}\right).$$Notice that $\dfrac{q-1}{2}\perp \dfrac{q+1}{2}\Rightarrow \dfrac{q+1}{2}a+\dfrac{q-1}{2}\perp \dfrac{q+1}{2}$, we have $$p\ |\ \dfrac{q+1}{2}a+\dfrac{q-1}{2}\Rightarrow p\ |\ \dfrac{q+1}{2}f(a)+\dfrac{q-1}{2}-\{\dfrac{q+1}{2} a+\dfrac{q-1}{2}\}\Rightarrow p\ |\ \dfrac{q+1}{2}(f(a)-a)\Rightarrow p\ |\ f(a)-a.$$If $a=-1$, by replacing $q\rightarrow 5$ it holds that $$(p\ |-1\Leftrightarrow p\ |\ 3f(-1)+2)\Rightarrow |3f(-1)+2|=1$$so $f(-1)=-1$. If $|a|\geq 2$, by Dirichlet prime number theorem there exist primes $p'>\max\{|a+1|,|f(a)-a|\}$ and $q'$ that satisfying $$q'\equiv \dfrac{2}{a+1}-1\ (\bmod\ p')$$then $$p'\ |\ \dfrac{q'+1}{2}a+\dfrac{q'-1}{2}\Rightarrow p'\ |\ f(a)-a\Rightarrow f(a)-a=0$$so $f(a)=a$. From the above, we conclude $\forall a\in\mathbb{Z}, f(a)=a$ or $\forall a\in\mathbb{Z}, f(a)=-a$. This easily gives the result.
SnowPanda
14.05.2022 15:05
The answer is $f(x) = \pm x$, which work.
Now we'll show that these are the only functions which work. The idea is to pin down $f$ for powers of $2$, and then show that this is enough to pin down $f$ for all inputs.
Claim: For all integers $x$, we have $f(-2x) = -2f(x)$.
Proof. First, fix any prime $p > 3$; we'll show that $f(-2x) \equiv -2f(x) \pmod{p}$.
By $(a, a, a)$ we have $p \mid f(a)$ iff $p \mid a$. This shows the desired congruence if $p \mid x$. Then by $(a, -2a, -2a)$ we have \[p \mid f(-2a)(2f(a) + f(-2a)).\]If $p \nmid x$ then $p \nmid f(-2x)$, so we must have $p \mid 2f(x) + f(-2x)$, as desired.
But then $f(-2x) + 2f(x)$ is divisible by infinitely many primes $p$, so must be $0$. $\blacksquare$
In particular, $f(0) = 0$, and if $f(1) = c$, then $f((-2)^k) = (-2)^kc$ for all nonnegative integers $k$.
Claim: If $x \equiv y \pmod{p}$, then $f(x) \equiv f(y) \pmod{p}$.
Proof. Assume $x \equiv y \not\equiv 0 \pmod{p}$ and $p > 2$ (the edge cases can be checked separately). Then we claim we can find nonzero $b$ and $c$ with $p \mid xb + xc + bc$ -- if $x \not\equiv -1 \pmod{p}$ then take $(b, c) = (1, -\tfrac{x}{x + 1})$, while if $x \equiv -1 \pmod{p}$ then take $(b, c) = (2, -\tfrac{x}{x + 2})$ (where the fractions are mod $p$).
Now we have \[f(x)(f(b) + f(c)) \equiv f(y)(f(b) + f(c)) \equiv -f(b)f(c) \pmod{p}.\]But $f(b) + f(c)$ is nonzero, since $f(b)f(c)$ is nonzero. So then $f(x) \equiv f(y) \pmod{p}$, as desired. $\blacksquare$
Claim: For any fixed integers $a$ and $x$ with $|a| > 1$ and $x \neq 0$, infinitely many primes divide the sequence $a^n + x$ (over all positive integers $n$).
Proof. Assume not, so there are finitely many primes which divide $a^n + x$. Fix some $m$ for which $a^m + x$ is nonzero, and for each prime $p_i$, take some $d_i > \nu_{p_i}(a^m + x)$. Now choose any \[n \equiv m \pmod{\varphi(p_i^{d_i})}\]for all $i$. Then $a^n \equiv a^m \pmod{p_i^{d_i}}$, which means \[\nu_{p_i}(a^m + x) = \nu_{p_i}(a^n + x)\]for all primes $p_i$. But these are the only primes which can divide an element of the sequence, so $a^m = a^n$, contradiction. (Alternatively, this follows from Kobayashi.) $\blacksquare$
Now this means for any nonzero integer $x$, there are infinitely many primes $p$ which divide $(-2)^k - x$. But for any such prime, we must have \[f(x) \equiv f((-2)^k) = (-2)^kc \equiv cx \pmod{p}.\]So $f(x) - cx$ has infinitely many prime factors, and must be $0$; this means $f(x) = cx$ for all $x$. Now $c$ cannot have a prime factor (or else $(0, 1, 1)$ would give a contradiction), so $c = \pm 1$ and we're done.