Find all functions f:N→N such that |xf(y)−yf(x)|is a perfect square for every x,y∈N
Problem
Source: 2024IMOC
Tags: number theory, functional equation
04.08.2024 04:20
One of my favorite problem in 2024 imoc : D Let ◻ denotes the set of perfect squares Let P(x,y) denotes the assertion of |xf(y)−yf(x)|∈◻ Choose a prime p with form 4k+1 P(p,x) ⟹ |pf(x)−xf(p)|∈◻, ∴ (\frac{xf(p)}{p})=0 \vee 1(Note that (\frac{-1}{p})=1 since 4|p-1, so the plus–minus sign doesn't matter at all) if p \nmid f(p) then we can choose x such that (\frac{x}{p})=-(\frac{f(p)}{p}), then 1=(\frac{xf(p)}{p})=(\frac{x}{p})(\frac{f(p)}{p})=-1, contradiction!! So we must have p|f(p) \forall p \in \mathbb{P}_{4k+1} Define another function g:\mathbb{N} \to \mathbb{Q}^+ (from the previous section we know f(x) \in \mathbb{N} \forall p \in \mathbb{P}_{4k+1}) Let Q(x,y) denote the assertion of xy|g(x)-g(y)| \in \square. Choose three distinct primes with form 4k+1: p, x, y Q(p,x) \implies px|g(p)-g(x)| \in \square \overset{p, x \in \mathbb{P}}{\implies} px|g(p)-g(x) \implies p|g(p)-g(x) \quad (1) Q(p,y) \implies py|g(p)-g(y)| \in \square \overset{p, y \in \mathbb{P}}{\implies} py|g(p)-g(y) \implies p|g(p)-g(y) \quad (2) (1)-(2) \implies p|g(y)-g(x) since there exist infinity primes with form 4k+1, g(y)-g(x) has infinity prime divisors, which implies g(y)-g(x)=0 \therefore f(x) is a constant c \forall x \in \mathbb{P}_{4k+1} Finally, choose p \in \mathbb{P}_{4k+1} and x \in \mathbb{N} (p \nmid x). Q(x,p) \implies px|g(x)-c| \in square \implies p|g(x)-c Again, since there exist infinity primes with form 4k+1, g(x)-c has infinity prime divisors, which implies g(x)-c=0 so g(x)=c \forall x \in \mathbb{N}. Namely, \boxed{f(x)=cx\quad \forall x} is a solution, where c is an arbtitary positive integer (which indeed fit since |xf(y)-yf(x)|=|cxy-cxy|=0 \in \square \forall x,y)
04.08.2024 16:08
Another weird solution: (x,y)=(1,3),(1,5),(3,5) can find out that \frac{f(1)}{1}=\frac{f(3)}{3}=\frac{f(5)}{5}so (x,y)=(x,1),(x,3) shows that f(x)=cx for all x
05.08.2024 10:33
I claim f(n)=cn for all n, where c\in\mathbb{N} is arbitrary. Let P(x,y) denotes the assertion that |xf(y)-yf(x)| is a perfect square for every x,y\in\mathbb{N}. Consider P(p,y) where p\equiv 1\pmod{4} is an arbitrary prime, we find yf(p) is a quadratic residue modulo p---as -1 is a quadratic residue modulo any such prime. So, unless p\mid f(p), we arrive at a contradiction by taking y to be a quadratic non-residue. Thus, p\mid f(p) for every p\equiv 1\pmod{4}, a prime. Next, let f(n)=n\phi(n), where \phi(p)\in\mathbb{N} for every prime p\equiv 1\pmod{4} and f(1)=\phi(1)\in\mathbb{N}. Considering P(p,1), we obtain |pf(1)-f(p)| = |p\phi(1) - p\phi(p)|=p|\phi(p)-\phi(1)| is a perfect square. Thus, \phi(p)\equiv \phi(1)\pmod{p}, for every prime p\equiv 1\pmod{4}. Next, consider P(p,q) where p\equiv q\equiv 1\pmod{4} are distinct primes. We have |pf(q)-qf(p)| = pq|\phi(p)-\phi(q)| a perfect square. Using modulo p and the fact q\ne p, we must have p\mid \phi(p)-\phi(q). As \phi(p)\equiv \phi(1)\pmod{p}, we find p\mid \bigl|\phi(1)-\phi(q)\bigr|. Unless \phi(q)=\phi(1), we arrive at a contradiction by taking p>|\phi(p)-\phi(1)|>0. So, for c:=\phi(1), we find f(p) = cp for every prime p\equiv 1\pmod{4}. We now prove f(n)=n for all n. Consider P(p,n) where p\equiv 1\pmod{4} is a prime to get |pf(n) -nf(p)| = p|f(n)-cn| is a square. If f(n)\ne cn for some n, then taking p large we find p\nmid |f(n)-cn|, a contradiction.
05.08.2024 15:55
grupyorum wrote: Now if p\nmid f(p) then by taking y to be a quadratic residue and quadratic non-residue, we arrive at a contradiction. So, p\mid f(p) for all primes p. I think there is a little mistake since |pf(y)-yf(p)| is equal to pf(y)-y(p) or yf(p)-pf(y), so both |pf(a)-af(p)| and |pf(b)-af(b)| may be a quadratic residue (suppose that p\nmid f(p) and (\frac{a}{p})=1 and (\frac{b}{p})=1)