We claim there exists a positive integer $d$ dividing $n$, an $a \in \mathbb{Z}$, and an $e \in \{-1,1\}$ such that $f(x) = e \cdot x^d + a$ for all $x$. It can be easily checked that all of these solutions work. First, notice that if $f(x)$ is a solution, then $f(x) + a$ is a solution for any $a$. So WLOG $f(0) = 0$. Now take $x = 1$, $y = 0$ in the given equation. We get $f(1) \mid 1$, so $f(1) = \pm 1$. If $f(x)$ is a solution, then $-f(x)$ is a solution, so WLOG $f(1) = 1$. We also get $f(-1) \mid 1$ by taking $x = -1$ and $y = 0$. Now take $x = -1$ and $y = 1$. We get $f(-1) - 1 \mid 2$, so $f(-1)$ must be $-1$. Consider any odd prime $p$. We have $f(p) - f(0) \mid p^n$, so therefore $f(p)$ is either $p^d$ or $-p^d$ for some $d$. First consider the case that $f(p) = -p^d$. We have $f(p) - f(-1) \mid p^n + 1$, so $p^d - 1 \mid p^n + 1$. If we write $n = qd + r$ using the division algorithm, we get $p^d - 1 \mid p^r + 1$. We know $0 \leq r < d$, so $0 < p^r + 1 < p^d - 1$ since $p > 2$, a contradiction. So this case is impossible Then we must have $f(p) = p^d$. Again write $n = qd + r$ using the division algorithm. We get $p^d - 1 \mid (-1)^q p^r - 1$. Since $0 \leq r < d$, this is only possible if $r = 0$. Therefore, $d$ divides $n$. Let $b$ be an arbitrary integer, and let $q$ be a prime number greater than $b^n + 2|f(b)|^n$. We know $f(q) = q^d$ for some $d$ dividing $n$. Consider $x = b$ and $y = q$. We get $f(b) - q^d \mid b^n - q^n$. Writing $q^n$ as $(q^d)^{n/d}$, we get $f(b) - q^d \mid b^n - (f(b))^{n/d}$. Suppose that $b^n - (f(b))^{n/d}$ is nonzero. Then we know that \[|b^n - (f(b))^{n/d}| \leq b^n + |f(b)|^n < q - |f(b)|^n \leq q^d - f(b).\] This is a contradiction, so therefore $b^n - (f(b))^{n/d} = 0$, and $f(b) = b^d$. If we apply this process to two arbitrary integers $b,c$, taking the same large $q$ for both of them, we obtain that $f(b) = b^d$ and $f(c) = c^d$ for the same $d$. Therefore there exists a single $d$ dividing $n$ such that $f(x) = x^d$ for all integers $x$. Reversing our transformations in the second paragraph, we get the set of solutions described in the first paragraph, so we are done.

This problem has been posted before: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=453800

Can someone post IMO Shortlist 2011 on contest page?

The formulation of the problem is not quite clear. If we plug $x=y$ in the condition we get the nonsense $0$ divides $0$. Evidently, the official solution tacitly uses that $f$ is injective and that the condition applies only with distinct $x$ and $y$. A more interesting interpretation is as follows: Quote: Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all integers $x$ and $y$ such that $f(x)$ is not equal to $f(y)$, the difference $f(x)-f(y)$ divides $x^n-y^n.$

$0$ divides $0$ is actually true, because there exists an integer $k$ such that $(0)(k)=0$. So I don't think there is any confusion in the problem.

And injectivity of $f$ results from the given relation(s), since assuming $f(x)=f(y)$ for some $x\neq y$ leads to $0 \mid x^n-y^n \neq 0$ (don't forget, $n$ is odd), so it does not need to be tacitly implied.

Maybe a more interesting question: find all functions $f$ defined on $\textbf{positive integers}$ with integer values and with the same property as in the problem.

mavropnevma wrote: And injectivity of $f$ results from the given relation(s), since assuming $f(x)=f(y)$ for some $x\neq y$ leads to $0 \mid x^n-y^n \neq 0$ (don't forget, $n$ is odd), so it does not need to be tacitly implied. I just wanted to express my mild surprise at this explanation. If my understanding is correct, the statement $ 0\mid x^{n}-y^{n}\neq 0 $ is nonsense rather than false, and the responsibility of eliminating such nonsense statements lies not with the problem solver, but with the problem proposer. In this particular case, the proposer could have defined $f$ to be injective, a definition that would have left no ambiguity in the problem. Now, I could be totally inaccurate on this explanation attempt, and if so, please kindly enlighten me. On another note, I would like to confirm that KittyOK's interpretation is solvable, and indeed a much more interesting problem than the one originally intended. And to KittyOK, my warmest congratulations once again for your gold medal at IMO 2012.

My pleasure. Of course, the statement should have contained the domain of the functional relation excluding its diagonal, so Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all distinct integers $x$ and $y$, the difference $f(x)-f(y)$ divides $x^n-y^n.$ Now, one will ask oneself: what if $f(x) = f(y)$ for some $x\neq y$. Then $v = x^n-y^n \neq 0$, since $n$ is given odd, so the given relation would be $0\mid v$. I never said this is false; if you prefer to call it nonsense it's ok with me. What matters is that it's not TRUE, so by contradicting the given relation forbids $f(x) = f(y)$ when $x\neq y$. Now, why should the proposer have ruled out this consequence of the relation, by redundantly stating "$f$ is injective" ? Another example. Say I write: Let $A$ be a set of positive integers and let $M$ be a number such that $a\leq M$ for all $a\in A$. Why should I "warn" the solver by stating "$A$ is finite", when it's a trivial consequence of the givens?

I have a question about MellowMelon's Solution, in the $f(p)$ part : MellowMelon wrote: If we write $n = qd + r$ using the division algorithm, we get $p^d - 1 \mid p^r + 1$. We know $0 \leq r < d$, so $0 < p^r + 1 < p^d - 1$ since $p > 2$, a contradiction. So this case is impossible. Well, I think this is not true when $p=3, r=0, d=1$ , so setting $p$ any odd prime is wrong. (But in this solution "infinitely many prime" works, so only "any odd prime" needs to be corrected.)

Here is another solution(More precise,a way to finish via Dirichlet's theoerem instead of bounding): All solutions are if the form $a*x^b$+$c$,where $a$ is $1$ or $-1$,$d$ divides $n$ and $c$ is an arbirtary integer.Note that,if $f(x)$ is a solution,then $f(x)+a$ is also a solution and if $f(x)$ is a solution,then $-f(x)$ is a solution.Now,WLOG $f(0)=0$ and P$(1,1)$ gives $f(1)=1$.P$(2,0)$ gives $f(2)$ divides $2^n$,so $f(2)=2^k$($k<n$) and P$(2,1)$ gives $2^k-1$ divides $2^n$-$1$,so we get $k$ divides $n$.Now,pluging any prime bigger than 2^(n^2) we get $f(p)=p^k$.Now,pick an arbirtary integer $m$ and suppose $f(m)=m^k$ doesn't hold.Now,let $n=ak$. Lemma: The equation $r^a$ congruent $l$ $modp$ always has a solution if $GCD(a,p-1)=1$($p$ is a prime). Proof:Pick two distinct integers $m,n$ such that $p$ doesn't divide $m-n$.Suppose $p$ divides $m^a-n^a$.Now,from Ferma's little theorem we have that $p$ divides m^(p-1)-n^(p-1),now by LTE we have GCD((m^a-n^a),(m^p-1-n^p-1))=$m-n$,which is a contradiction. Pick a prime $r$ such that $r$ doesn't divide $f(m)^a$-$m^n$ and such that $k$ doesn't divide $r-1$.By Dirichlet,such a prime exists Now,by Dirichlet there will exist a prime $q$ such that $r$ divides $q^k-f(m)$,now P$(q,m)$ gives that $r$ divides $f(m^a)$-$m^n$,which is a contradiction,so we get $f(m)=m^k$.

First notice that if $n<0$ then $f(x)-f(0)|x^n$ but the left side is an integer and $x^n$ isn't an integer for all $x$, and therefore there exists no such function $f$. If $n=0$, then if $x=0$, $0^0$ is undefined and so the problem's statement is undefined. Now assuming $n>0$, I claim that the functions that work are $f(x)=\Gamma+x^{\Omega}$ and $f(x)=\Gamma-x^{\Omega}$, for any positive divisor $\Omega | n$ and any integer $\Gamma$. Firstly notice that we can multiply $f$ by $-1$ and shift it by a constant and it still works, and therefore WLOG $f(1) \ge 0$ and $f(0)=0$. Notice $f(1)-0|1-0$ and so $f(1)=1$. Now take $p$ be any odd prime. Notice that $f(p)|p^n$ and therefore $f(p)=p^{\Omega}$ or $-p^{\Omega}$ for some $0\le {\Omega} \le n$. In the second case, we get that $p^{\Omega}+1 | p^n-1$ and so $p+1 | p^n-1$ (or $\Omega=0 \Rightarrow f(p)=-1$) but notice that since $n$ is odd, $p+1 | p^n+1$ and so $p+1 | 2$, impossible. Therefore, $f(p)=p^{\Omega}$ for some $1 \le \Omega \le n$, or $f(p)=-1$. So $p^{\Omega}-1 | p^n-1$. It is a well known fact that $\text{mcd}(a^b-1,a^c-1) = a^{\text{mcd}(b,c)}-1$ for $a,b,c$ positive integers and $a>1$, which can be proven by Euclid's Algorithm easily. Therefore $\Omega | n$. Now let $S$ be the set of positive integers that divide $n$. Notice that if $f(a)=f(b)=-1 \Rightarrow 0 | a-b \Rightarrow -1$ and so $f(p)=-1$ for at most one value of $p$. For all other odd primes $p$, $\Omega \in S$ and since $S$ is finite, there exists an infinite set $S_{\Omega}$ of prime numbers such that $f(p)=p^{\Omega}$ for all $p \in S_{\Omega}$. Now take any integer $x \neq -1,0-1$ and notice that for any such $p$, $p^{\Omega}-f(x) | p^n-x^n$, but also $p^{\Omega}-f(x) | p^n-f(x)^{\frac{n}{\Omega}}$ and therefore $p^{\Omega}-f(x) | x^n-f(x)^{\frac{n}{\Omega}}$. This implies that $x^n-f(x)^{\displaystyle\frac{n}{\Omega}}$ has an infinite number of divisors, which clearly implies that said number is $0$. Therefore $f(x)={\Omega}$ for all $x \neq 0,1,-1$. But this equality is also true for $x=0,1$ as we had previously established. Now all that is left is to prove $f(-1)=-1$. But notice $f(-1)|-1$ and so $f(-1)=-1,1$. We also have $1-f(-1)|2$ and so $f(-1)=-1$. Therefore $f(x)=x^{\Omega}$ for all $x$, where $\Omega$ is a fixed positive divisor of $n$. Taking into account that we shifted and multiplied $f$ by $-1$ at the beginning, this gives us the final answers $\boxed{f(x)=\Gamma+x^{\Omega}}$ and $\boxed{f(x)=\Gamma-x^{\Omega}}$, for any positive divisor $\Omega | n$ and any integer $\Gamma$.

Answer. The only solutions are $f(x)=cx^d+e$ where $c \in \{-1, 1\}$, $d \ge 0$ is an odd divisor of $n$ and $e \in \mathbb{Z}$ for all integers $x$. Solution. It is clear that these satisfy the conditions. We will show that no other function works. Indeed, suppose a function $f$ other than those specified works. Injectivity of $f$ follows since $f(a)=f(b) \Longrightarrow a^n=b^n$ and as $n$ is odd, $a=b$. Shifting by a constant; let $f(0)=0$, and for all integers $a$ we get $f(a) \mid a^n$. As $f(1) \mid 1$, scaling by a $\pm 1$ factor, we let $f(1)=1$. For all primes $p$, $f(p) \mid p^n \Longrightarrow f(p)=\pm \, p^k$ for some $k >0$. Firstly, let $f(p)=-p^k$ and observe that $p^k+1 \mid p^n-1$. Write $n=kl+r$ for $0 \le r<k$ and note that $$p^n \equiv p^r\cdot (-1)^l \pmod {p^k+1} \Longrightarrow p^k+1 \le \left|p^r\cdot (-1)^l-1\right| \le p^r+1,$$which is clearly false. It follows that $f(p)=p^{k_p}$ for all primes $p$ with $1 \le k_p \le n$. Evidently, there exists $1 \le d \le n$ such that $k_p=d$ holds for infinitely many primes $p$. Fix a prime $p_1$ with $k_{p_1}=d$ and vary $p$ with $k_p=d$. Write $n=md+r$ for $0 \le r<d$ and note that $$p^d-p_1^d \mid p^n-p_1^n \Longrightarrow p_1^{md}\cdot \left(p^r-p_1^r\right) \equiv 0 \pmod {p^d-p_1^d}.$$This is fails to occur unless $d \mid n$. Finally, fix an integer $x$ with $f(x) \ne x^d$ and vary prime $p$ with $k_p=d$. It follows that $$p^d-f(x) \mid p^n-x^n \Longrightarrow p^d-f(x) \mid f(x)^{\frac{n}{d}}-x^n,$$which fails to hold by taking $p$ sufficiently large. The initial claim holds. $\, \square$

Answer. All functions f of the form f(x) = εxd + c, where ε is in {1, −1}, the integer d is a positive divisor of n, and c is an integer. Solution. Obviously, all functions in the answer satisfy the condition of the problem. We will show that there are no other functions satisfying that condition. Let f be a function satisfying the given condition. For each integer n, the function g defined by g(x) = f(x) + n also satisfies the same condition. Therefore, by subtracting f(0) from f(x) we may assume that f(0) = 0. For any prime p, the condition on f with (x, y) = (p, 0) states that f(p) divides p n . Since the set of primes is infinite, there exist integers d and ε with 0 ≤ d ≤ n and ε ∈ {1, −1} such that for infinitely many primes p we have f(p) = εpd . Denote the set of these primes by P. Since a function g satisfies the given condition if and only if −g satisfies the same condition, we may suppose ε = 1. The case d = 0 is easily ruled out, because 0 does not divide any nonzero integer. Suppose d ≥ 1 and write n as md + r, where m and r are integers such that m ≥ 1 and 0 ≤ r ≤ d − 1. Let x be an arbitrary integer. For each prime p in P, the difference f(p)−f(x) divides p n −x n . Using the equality f(p) = p d , we get p n − x n = p r (p d ) m − x n ≡ p r f(x) m − x n ≡ 0 (mod p d − f(x)) Since we have r < d, for large enough primes p ∈ P we obtain |p r f(x) m − x n | < pd − f(x). Hence p rf(x) m − x n has to be zero. This implies r = 0 and x n = (x d ) m = f(x) m. Since m is odd, we obtain f(x) = x d

$f(x) = \epsilon x^d + c, \ \ \epsilon \in \{ 1,-1\} , c \in \mathbb{Z}$ and $d$ is a positive divisor of $n$. We will now prove this is the only solution. Lemma: If $x^m-1 \mid x^n-1$ then $m \mid n$ Proof: Let $n=am+r$. Then $$x^{am+r} -1 \equiv x^{am+r} - x^m \equiv x^m (x^{(a-1)m+r}-1) \equiv x^{(a-1)m+r} -1 \equiv \cdots \equiv x^r -1 \mod (x^m-1) $$But $r<m$ so $r=0$. Let $f(0)=c$. Throughout the solution we will assume $c=0$. Because if $f(x)$ is a solution so is $f(x)+c$. $f(1) \mid 1$. Hence $f(1)= \pm 1$. WLOG, $f(1)=1$ Let $p$ be a prime. Plugging in $(p,0) \longrightarrow f(p) \mid p^n \longrightarrow f(p) = \pm p^d$ If $f(p) = -p^d$ $(p,1) \longrightarrow p^d +1 \mid p^n-1$. Let $n=ad+r$ $$p^{ad+r} -1\equiv p^{ad+r} + p^d \equiv p^{(a-1)d+r}+1 \equiv \cdots \equiv p^r +1 \mod (p^d+1)$$But $p^r+1 >0$ so $f(p) -1$ does not divide $p^n-1$. If $f(p) =p^d$ $(p,1) \longrightarrow p^d -1 \mid p^n -1 \longrightarrow d \mid n$ from our Lemma. $(p,y) \longrightarrow p^d -f(y) \mid p^n -y^n$ $$p^{ad} -y^n \equiv f(y)^a -y^n \mod (p^d -f(y))$$Take $p$ very large. Then $p^d -f(y ) > f(y)^a -y^n \Longrightarrow f(y)^a - y^n=0$ Hence $f(y) = y^d\ \ \forall y \in \mathbb{Z}$. If $f(1)=-1$ then $f(y) = -y^d$. Moreover we can add an integer constant $c$ so we are done.

Note that if $f$ works, so does $f+C$ for any constant $C$, so we may assume WLOG $f(0)=0$. Furthermore, if $f$ works, so does $-f$, so we may assume WLOG that $f(1)\ge 0$. Note that $f$ is injective as $0\mid x^n-y^n\implies x=y$, so this in fact implies $f(1)\ge 1$. Let $p$ be any prime. We see that $f(p)\mid p^n$, so $f(p)=\pm p^k$ for some $k\le n$. Note that \[p^n= (p^k)^{\lfloor n/k\rfloor}p^{n\pmod{k}}\equiv \pm f(1)^k p^{n\pmod{k}}\pmod{p^k-1}.\]Thus, \[p^k\pm 1\mid f(1)^k p^{n\pmod{k}}\pm 1.\]Note that we can't have $k=0$ more than a couple of times because of injectivity, so we have $k\ge 1$ for sufficiently large $p$. But $p^{n\pmod{k}}\le p^{k-1}$, and since $k\le n$ is bounded above, we have \[p^k\pm 1 > f(1)^k p^{n\pmod{k}}\pm 1\]for sufficiently large $p$ (note that our argument isn't relying on the fact that $k$ is fixed, only that $k\ge 1$). The only fix is that \[f(1)^k p^{n\pmod{k}}\pm 1=0\]for sufficiently large $p$, which means that $k\mid n$ and $f(1)\in\{-1,1\}$, and we assumed that $f(1)\ge 1$, so $f(1)=1$. Repeating the same argument with $f(-1)$ shows that $f(-1)=-1$ (it can't be $1$ by injectivity). We have also shown that $f(p)=\pm p^k$ for $k\mid n$ for sufficiently large primes $p$, and a similar argument shows that $f(-p)=\pm p^k$ for some possibly different $k\mid n$. Let's quickly clear up the signs. We want $f(p)-1\mid p^n-1$. If $f(p)=-p^k$, then we have \[p^k+1\mid p^n-1.\]Note that $p^n=(p^k)^{n/k}\equiv (-1)^{n/k}=-1\pmod{p^k+1}$ (this uses the parity of $n$), so $p^k+1\mid 2$, which isn't true for large $p$, so $f(p)=p^k$, and similarly $f(-p)=-p^k$ for some possibly different $k$. Fix some $x\in\mathbb{Z}$. We have that $f(p)-f(x)\mid p^n-x^n$, for a sufficiently large prime $p$ with $f(p)=p^k$. We see that \[p^n-x^n=(p^k)^{n/k}-x^n\equiv f(x)^{n/k}-x^n\pmod{f(p)-f(x)},\]so \[p^k-f(x)\mid f(x)^{n/k}-x^n.\]As $p$ grows larger and larger (keep in mind that $k\ge 1$ always here), we see that the left side grows without bound while the right side remains fixed. As usual, the only fix is that \[f(x)^{n/k}=x^n.\]Since $n$ is odd, we may take the $n$th root of both sides to deduce that $f(x)^{1/k}=x$. Raising both sides to the power $k$, we learn that $f(x)=x^k$. Now, in theory $k$ could be different for the sufficiently large primes $p$, but this shows that this is not the case, and that in fact, $f(x)=x^k$ for all integers $x$. All the solutions are then given by $\boxed{\pm x^k+C}$ for any integer $C$. It is trivial to check that these work. $\blacksquare$

Cute problem! orl wrote: Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^n-y^n.$ Proposed by Mihai Baluna, Romania It's immediate to see that $f(x)= \pm x^k +C$ where $k\mid n$ and $C$ is any integer is indeed such a function. We will prove that it is the only such function. Firstly observe that $f(x)$ is a solution implies $f(x)+C$ is a solution too. So let us assume WLOG that $f(0)=0$. Also observe that $f(x)$ is a solution implies $-f(x)$ is a solution too. $\bullet$ Let $P(x,y)$ denote the assertion $f(x)-f(y)\mid x^n-y^n$. Readily observe that $f$ is injective. $$P(1,0)\implies f(1)-f(0)\mid 1\implies f(1)=\pm 1$$By $(\bullet)$ we can assume that $f(1)=1$. $P(p,0)$ where $p$ is a prime gives us $$f(p)\mid p^n\implies f(p)=\pm p^k, 0\le k\le n$$Note that $k=0$ is possible for at-most $2$ primes due to injectivity. Henceforth we will choose a prime such that $f(p)\ne \pm 1$. and $$P(p,1)\implies f(p)-f(1)\mid p^n-1\implies \pm p^k-1\mid p^n-1$$If $f(p)=p^k\implies k\mid n$ If $f(p)=-p^k\implies -p^k-1\mid p^n-1$ $$\implies p^k+1\mid p^n-1$$But we know that $p^k+1\mid p^{2k}-1\implies p^k+1\mid p^{\gcd(2k,n)}-1\implies p^k+1\implies p^k+1\mid p^{\gcd(k,n)}-1$ because $n$ is odd. But $p^{\gcd(k,n)}\le p^k+1$, a contradiction. $$P(x,p)\implies f(x)-f(p)\mid x^n-p^n$$$$\implies f(x)-p^k\mid x^n-p^n\qquad(1)$$But we also have $$f(x)-p^k\mid f(x)^{n/k}-p^n\qquad(2)$$Subtracting $(2)$ from $(1)$ we get $$f(x)-p^k\mid x^n-f(x)^{n/k}$$Now taking large enough $p$ for a fixed $x$ we obtain $$x^n-f(x)^{n/k}=0\implies f(x)=x^k$$So $\boxed{f(x)=\pm x^k+C}$ where $k\mid n$ and $C$ is any integer.

Let $P(x,y)$ denote $f(x)-f(y) \mid x^n-y^n$. Note that if $f$ works, so does $f+C$. Hence WLOG $f(0)=0$. $P(1,0)$ gives $f(1)\mid 1$, so $f(1)=\pm 1$. If $f$ works, so does $-f$, so WLOG $f(1)=1$. Now, $P(p,0)$ for a prime $p$ gives $f(p) \mid p^n$, so $f(p)= \pm p^k$ for some $k\le n$. And $P(p,1)$ gives $f(p)-1 \mid p^n-1$.

Therefore, we conclude $f(p)=p^k$. Now, we know $p^k-1\mid p^n-1$, so $k\mid n$. Define $k_p$ for each $p$ so that $f(p)=p^{k_p}$. We know $k_p\mid n$. But $n$ has finitely many factors, so there exists some $e\mid n$ such that infinitely many primes $q$ with $f(q)=q^e$. We need to involve a general $x$ somehow to get the value of $f$ for all $x$. So $P(x,q)$ gives $f(x)-q^e \mid x^n-q^n$. We want to get rid of the $q$ on the right side to utilize the infinitely many $q$ fact. We also know $f(x)-q^e \mid f(x)^{n/e} - q^n$. Hence $f(x)-q^e \mid (x^n-q^n) - (f(x)^{n/e} - q^n) = x^n - f(x)^{n/e}$. Since this holds for infinitely many $q$, we get a size contradiction by taking large enough $q$, unless $x^n-f(x)^{n/e}=0$, i.e. $f(x)=x^e$. Therefore, we conclude that $f(x)$ is of the form $x^e$, for some $e\mid n$. But clearly $f(x)=x^e$ for some $e\mid n$ works. Therefore, in fully generality, our solution set is $f(x)=\pm x^e + C$ for a constant $C$ and for some $e\mid n$.

The answer is $f(x)=\pm x^k+c$, where $k$ is a positive divisor of $n$ and $c$ is a fixed integer. It is easy to see that such function always work, we now show that they are the only ones. Firstly, note that is $f$ is a solution to the equation then so as $\pm f(x)+c$. Therefore by shifting we may assume $f(0)=0$. Therefore, sub. $x=1,y=0$ into the equation we have $$f(1)|1$$Hence $f(1)=\pm 1$. Again by shifting we may assume $f(1)=1$, similarly $f(-1)=-1$. Moreover if $x\neq y$ then $x^n\neq y^n$, hence $f$ is injective. Now the crucial step: CLAIM. Suppose $a$ and $b$ are two distinct factors of $n$, and $k$ is a fixed integer, then the divisibility in $m$ $$k^a-m^b|k^n-m^n$$has finitely many solutions in integers. Proof. Notice that $k^n-m^n=k^n-(m^{b})^\frac{n}{b}$ is a polynomial in $m^b$ since $b|n$. Therefore by remainder theorem, the remainder when $k^n-m^n$ is divided by $k^a-m^b$ is given by \begin{align} k^n-k^{\frac{na}{b}} \end{align}Notice that $\frac{a}{b}\neq 1$. Hence $(1)\neq 0$. Therefore we need $|k^a-m^b|\leq k^n-k^{\frac{na}{b}}$ which obviously has finitely many solutions since $R.H.S.$ is fixed. $\blacksquare$ Corollary 1. For every prime $p$, define $g(p)=\log_p(f(p))$, then $$g(p)=g(q)$$for all prime $p,q$. Proof. Let $p$ be a prime, and $g(p)=a$, then $f(p)=p^a$. We call another prime $q$ $p$-bad if $g(q)\neq g(p)$. Notice that from the condition we have $$p^a=f(p)-f(0)|p^n$$$$p^a-1=f(p)-f(1)|p^n-1$$Hence $a$ is a positive integer(since $f(p)\neq 1$ by injectivity) from the first equation. Moreover $a|n$ from the second equation. This holds for any prime as well. Now for any $p$-bad prime $r$ we have $$p^a-r^{g(r)}=f(p)-f(r)|p^n-r^n$$Since $g(r)|n$, $a|n$ and $g(r)\neq a$, applying the claim we found that there are only finitely many solutions for $r$ if $g(r)$ is fixed. Notice that $g(r)|n$, so there are finitely many possibilities for $g(r)$. This implies that there are only finitely many $p$-bad primes. Now suppose there exists a $p$-bad prime $r$, then by symmetry there exists only finitely many $r$-bad primes. But this is obviously a contradicition since for all primes, it must be either $p$-bad, $r$-bad or both $p$-bad and $r$-bad. $\blacksquare$ Corollary 2. from Corollary 1 $g(p)$ is a constant, denote it by $k$. Then $$f(a)=a^k$$for all integers $a$. Proof. from the condition we have $$f(a)-p^k=f(a)-f(p)|a^n-p^n$$for all prime $p$. Notice that $$a^n-p^n=a^n-(p^k)^{\frac{n}{k}}\equiv a^n-(f(a))^{\frac{n}{k}}\pmod{f(a)-p^k}$$Hence $$f(a)-p^k|a^n-(f(a))^{\frac{n}{k}}$$Since this holds for all prime $p$ the right hand side must be zero. Hence $$f(a)=a^k$$as desired.

We claim that $f(x)= \pm x^k+c$, where $k|n$. This clearly works. Then, observe that if $f$ is a solution, then $\pm f+c$ is also a solution $\implies$ WLOG $f(0)=0 \implies f(1)|1 \implies$ WLOG $f(1)=1 \implies f(-1)|1$ and $f(1)-f(-1)|2 \implies f(-1)=-1$. Now, since $f(0)=0 \implies f(p)|p^n$ for all prime numbers $p \implies |f(p)|=p^{x_p}$ for some $0 \leq x_p \leq n$. If $f(p)< 0$ for some prime number $p$ $$\implies f(1)-f(p)=1+p^{x_p}|1-p^n,1-p^{2x_p}$$$\implies p^{x_p}+1|p^{gcd(n,2x_p)}-1=p^{x_p}+1|p^{gcd(n,x_p)}-1 \leq p^{x_p}-1$, contradiction. Hence, $f(p)> 0$ for all prime $p$. Furthermore, $p^{x_p}-1|p^n-1 \implies x_p|n$, and by Pigeonhole, there exist infinitely prime numbers $p_1<p_2<...$ such that $$f(p_i)=p_i^k$$with $k$ fixed. $\implies$ if there exists a prime number $q$ such that $f(q)=q^l$ with $l \neq k$ $$\implies p_i^k-q^l|p_i^n-q^n \implies 0 \equiv p_i^n-q^n \equiv (q^l)^{\frac{n}{k}}-q^n \pmod{p_i^k-q^l}$$$\implies$ taking $i$ large enough, $q^{\frac{ln}{k}}=q^n \implies l=k$, contradiction. Thus, $f(p)=p^k$ for all prime numbers $p$ and fixed $k|n$ $$\implies p^k-f(y)|p^n-y^n \implies 0 \equiv p^n-y^n \equiv f(y)^{\frac{n}{k}}-y^n \pmod{p^k-f(y)}$$Then, taking $p$ large enough, we have that $f(y)=y^k$ for all $y \in \mathbb{Z}$ with $k|n$, and the result follows. $\blacksquare$

We claim the answer is $f(x)=cx^k+d$ where $k\mid n,$ and $c=\pm 1.$ It can easily be seen that this works. Now note that if $f$ is a solution so is $\pm f + d.$ So WLOG say $f(0)=0$ and $f(1)\geq 0.$ Note that $(1,0)$ gives $f(1)\mid 1$ or $f(1)=1.$ Then $(p,0)$ gives $f(p)\mid p^n$ or $f(p)=\pm p^k.$ Claim: For all $p,$ $f(p)=p^k$ for $k\mid n.$ If $f(p)<0$ then $(p,1)$ gives $\gcd(-p^k-1,p^n-1)=\gcd(p^k+1,(-1)^mp^r-1)$ where $n=mk+r$ for $0\leq r<n.$ Unless $r=0$ and $2\mid m,$ this value is less than $k,$ as $|(-1)^mp^r-1|<p^k+1.$ But note that $n$ is odd, so this can never happen. If $f(p)>0$ then $(p,1)$ gives $\gcd(p^k-1,p^n-1)=p^{\gcd(k,n)}-1$ by Euclidean Algorithm. So we must have $k\mid n.$ Now it remains to show that all said $k$ are the same. Say that $f(p)=p^k$ and $f(q)=q^j$ where $k\leq j.$ Then $(p,q)$ yields \[\gcd(p^k-q^j,p^n-q^n)=\gcd(p^k-q^j,p^{n-k}q^j-q^n)=\gcd(p^k-q^j,p^{n-k}-q^{n-j}).\]If $n=ak=bj,$ then this gives us \[p^k-q^j\mid p^{n-bk}-1.\]If $p\gg q$ or $q\gg p,$ then clearly $|p^k-q^j|>p^{n-bk}-1,$ so we must have $n-bk=0,$ implying $k=j$ as desired. So we induct; say $p_i$ is the $ith$ prime. Then to show $p_i=p_{i+1}$, take $q\gg p_{i+1},$ and note that $p_i\to q\to p_{i+1}.$ Now we're getting there! Claim: For all $x,$ $f(x)=x^k$ for the same $k$ as shown previously. Take large $p$ (so large that it completely overshadows $f(x)$ and $x^n$) and note \[f(x)-p^k\mid x^n-p^n\]\[f(x)-p^k\mid x^n-f(x)^{\frac{n}{k}}.\]By size we must have $x^n=f(x)^{\frac{n}{k}},$ implying that $f(x)=x^k.$

Write a divisibility FE without using size NT challenge (IMPOSSIBLE) The answer is $f(x)=a\cdot x^d+b$, where $a=\pm 1$ and $d \mid n$. This clearly works. Denote the assertion as $P(x,y)$, and note that $f$ must be injective as $f(x)=f(y) \implies 0 \mid x^n-y^n \implies x=y$. Now note that shifting $f$ by a constant preserves any solutions, and if $f$ works then $-f$ works too. Hence assume $f(0)=0$. From $P(1,0)$ we get $f(1) \mid 1$, so $f(1)=\pm 1$. WLOG let $f(1)=1$, so it suffices to show that $f(x)=x^d$. Further, $P(-1,0)$ implies that $f(-1)=-1$ by injectivity. Now note that $f(p) \mid p^n$, so by $P(p,0)$, $f(p)=\pm p^r$ where $n\geq r \geq 1$—note that $r \neq 0$ by injectivity. If $f(p)=p^r$, then by $P(p,1)$ we have $$p^r-1 \mid p^n-1 \implies r \mid n,$$as $\gcd(p^x-1,p^y-1)=p^{\gcd(x,y)}-1$. If $f(p)=-p^r$, then from $P(p,1)$ we have $p^r+1 \mid p^n-1$. Since $p^r+1 \mid p^{2r}-1$, it follows that $p^r+1 \mid p^{\gcd(2r,n)}-1=p^{\gcd(r,n)}-1$, as $n$ is odd. But $p^{\gcd(r,n)}-1$ is positive and less than $p^r+1$, which is a contradiction. Hence we require $f(p)=p^r$ for some $n\geq r \geq 1$. Then, by infinite pigeonhole there must exist some $d$ such that we have infinitely many primes $p$ with $f(p)=p^d$. Then for any $x$, we have $p^d-f(x) \mid p^n-x^n$. But we also have $p^d-f(x) \mid p^n-f(x)^{n/d}$, which implies $$p^d-f(x) \mid x^n-f(x)^{n/d}.$$By making $p$ sufficiently large, it follows that $x^n=f(x)^{n/d} \implies f(x)=x^d$ for all $x$. $\blacksquare$

Noticing that one may shift the function is, in my opinion, the most important part of the problem.

WLOG $f(0)=0$ and since $f(1)\mid 1,$ WLOG $f(1)=1$ by shifting. Let $P(x,y)$ denote the given assertion. Take a prime $p$ then $P(p,0)$ gives $f(p)\mid p^n.$ Note that this holds for infinitely many primes. Then $f(p)\in \{p^k,-p^k\}$ where $k$ is constant and $n\geq k\geq 1.$ WLOG $f(p)=p^k.$ $P(p,1)$ implies $k\mid n.$ Also $P(p,m)$ implies $p^k-f(m)\mid p^n-m^n.$ Since $p^k-f(m)\mid p^n-f(m)^{n/k}$ we get $p^k-f(m)\mid m^n-f(m)^{n/k}.$ Now just fix $m$ and vary $p$ so that $f(m)=m^k,$ this works.

Solved this one with quirtt. Solution: We will show that $f(x) = \pm x^k+d$ for all $x \in \mathbb{Z}$ where $k \mid n$. This indeed works and we now show this is the only solution. Denote $P(x,y)$ as the assertion. Start of by shifting $g(x) = f(x) - f(0)$. This would give $g(0) = 0$ and $g(x) - g(y) = f(x) - f(y)$, so the problem statement remains untouched and we will now talk in terms of $g$. Observe from $P(1,0)$ we get $g(1) = \pm 1$. Assume $g(1) = 1$ because if $g$ is a solution iff $-g$ is a solution. We now show $f$ is an injective function. Assume $f(a) = f(b)$ for $a \ne b$. $P(a,b)$ gives 0 dividing something which is a contradiction. Claim: $g(p) = p^k$ for all primes $p$ and some $k$ such that $k \mid n$. Proof: The substitution $P(p,0)$ gives us \[g(p) \mid p^n\]which now gives us $g(p) = p^k$ for some $k$ otherwise a contradiction on injectivity. We now turn to part of showing $k \mid n$. From $P(p,1)$ we get \[p^k - 1 \mid p^n - 1 \iff p^k -1 \mid p^{n-k} -1\]and upon iterating, and using size arguments one would eventually show $k \mid n$. To finally show that $k$ is constant throughout consider $P(x,y)$ where $x,y$ are primes. \[x^{k_1} -y^{k_2} \mid x^n - y^n \iff x^{k_1} -y^{k_2} \mid y^n - y^{qk_2}\]where $q = \frac{n}{k_1}$. Choose $x$ to be insanely big and $y$ be a prime say less than 1000. Due to insanely big nature of $x$ we force $y^n = y^{k_2q}$which gives $k_1 = k_2$ for primes between 1 to 1000. One can now vary $x$ and $y$ accordingly to prove $k$ is constant throughout. $\square$ The above claim is quite sufficient in itself. Consider $P(x,q)$ where $q$ is a prime. Re-write $n = \alpha k$ for simplicity. \begin{align*} g(x) - q^k &\mid x^{\alpha k} - q^{\alpha k} \\ g(x) - q^k &\mid x^{\alpha k} - q^{\alpha k} - (g(x)^{\alpha} -q^{\alpha k}) \\ g(x) - q^k &\mid x^{\alpha k} - g(x)^{\alpha} \end{align*}Picking $q$ to be large enough, we are done! $\blacksquare$ Remark 1. It suddenly popped that when we chose $q$ to be large enough we get $g(x)^\alpha = x^{\alpha k}$. For cancelling $\alpha$ as a power safely, we need to make sure it's odd otherwise we get more solutions! Since $n$ is odd, obviously $\alpha$ must be odd and thus we are done. Remark 2. $g(p) \mid p^{n}$ doesn't necessarily give $g(p) = p^k$. One could face sign issues like having $g$ to be positive at some points and negative at others. One can actually show that this won't. For the sake of contradiction, assume there are two primes $a,b$ such that $g(a) = a^{k_1}$ and $g(b) = -b^{k_2}$. One can show both $k_1$ and $k_2$ divide $n$. Imitate the part where we show $k$ is constant to get \[b^n + b^{k_2\frac{n}{k_1}} \equiv 0 \pmod{a^{k_1}+b^{k_2}}.\]This time picking large $a$ would lead to a size contradiction and we are done with resolving this part. People in the thread actually find it simple, but I will add this because I think solution demands this.

The answer is all functions $f$ such that $f(x)=\pm x^k+c$ where $k\mid n$ and $c$ is any integer. It is easy to check that all of these functions work. Now shift so that $f(0)=0$ and note that $f(1)\in \{-1, 1\}$. Therefore WLOG $f(1)=1$; we show that $f(x)=x^k$ for some fixed $k\mid n$ and all $x\ge 0$; the proof for negative numbers is similar. Notice that $f$ is clearly injective; we also have that \[f(p)\mid p^n\implies f(p)=\pm p^m,\, m\ge 1,\]\[f(p)-1\mid p^n-1\implies f(p)=p^m,\, m\mid n.\](Here, $m$ depends on $p$). Next take a sufficiently large prime $p$; we have that \[\frac{p^n-x^n}{p^m-f(x)}\in \mathbb{Z}\implies \frac{f(x)^{\tfrac{n}{m}}-x^n}{p^m-f(x)}\in \mathbb{Z}\]which is enough to imply that $f(x)=x^m$. However, this implies that for all primes $p\ge N$ for some large constant $N$, we have $f(p)=p^k$, this time for a constant $k$ not depending on $p$. This evidently extends to all positive integers by the previous argument; therefore $f(x)=x^k$ for some $k\mid n$ and we are done. $\blacksquare$

Used the 0% hint on ARCH. The answer is $\boxed{c\pm x^d}$ for an integer $x$, a choice of $+$ or $-$, and a positive integer $d$ dividing $n$. We will restrict our search to when $f(0)=0$(just shift the function) and $f(1)=1$(from $P(1,0)$, and the sign can be WLOG'd). Then we can get that $f(-1)=-1$. For any positive integer $x$, \[P(k,0)\rightarrow f(x)\mid x^n\rightarrow f(x)=x^{d_x}.\]\[P(k,1)\rightarrow x^{d_x}-1\mid x^n-1\rightarrow d_x\mid n.\] Now consider two integers $x_1$ and $x_2$ such that $2\le |x_1|\le |x_2|$. Now let $y=|x_2^{n^2}|+|x_2^n|+1434$. Then $P(y,x)$ for any $x$ such that $2\le |x|\le |x_2|$ gives \[y^{d_y}-x^{d_x}\mid y^n-x^n-(y^n-x^{d_x n/d_y})=x^{d_x n/d_y}-x^n.\]But the LHS is greater than the absolute value of the RHS, so $d_x n/d_y=n$, so $d_x=d_y$. But this means that $d_{x_1}=d_{x_2}$. So $d_i$ is constant between any two integers, QED.

Note that if $f$ is a solution then $\pm f+c$ is also a solution. Thus, we can assume $f(0)=0$ and $f(1)\ge 0$. Let $P(x,y)$ denote the assertion. Note that $P(1,0)$ gives $f(1)=1$ and $P(-1,1)$ gives $f(-1)=-1$. $P(p,0)$ gives $f(p)=\pm p^k$ for some $k$, for all primes $p$. If $f(p)=-p^k$ then $P(p,-1)$ gives $p-1\mid p^k-1\mid p^n+1$ so \[p^n+1\equiv 1^n+1\pmod 2\equiv 0\pmod p-1\]implies that $p=2$ or $3$. If $f(p)=p^k$ then $P(p,1)$ gives $k\mid n$. Let $p$ be a large prime and $n=ak$ then $P(x,p)$ gives \[f(x)-p^k\mid x^n-p^{ak}\implies f(x)-p^k\mid x^n-f(x)^a\]so picking a large enough $n$ makes $x^n=f(x)^a$. For all $x$, no matter how large of an $|x|$ we pick, we can always find a $p$ that is very big that will work for all the ones smaller than $|x|$. Thus, $f(x)=x^k$ for all $x$. Without the assumptions, $f(x)=\pm x^k+c$.

orl wrote: Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^n-y^n.$ Proposed by Mihai Baluna, Romania If $f(x)$ is a sollution then so it is $f(x)+c$ so we can WLOG $f(0)=0$. $P(p,0)$ gives $f(p)|p^n\Rightarrow f(p)=+-p^i$ with $i=0,1,2,..,n$ So there is a $i$ with is true for infinitive primes.Because $f(x)$ is a sollution then so it is $-f(x)$ let $f(p)=p^i$ Let $r$ be a prime with $r|i$ then consider by Direclert primes $p,q$ such that $p\equiv q(modr)$ then $P(p,q)$ gives: $p^i-q^i|p^n-q^n\Rightarrow U_r(p^i-q^i)\leqslant U_r(p^n-q^n)\Rightarrow U_r(p-q)+U_r(i)\leqslant U_r(p-q)+U_r(n)\Rightarrow U_r(i)\leqslant U_r(n)$ So $i|n$ let $n=i*m$ then: Fix $x$ and take a prime $p$ then $P(x,p)$ gives: $f(x)-p^i|x^{i*m}-p^{i*m}= x^{i*m}-(p^i)^m\equiv x^{i*m}-f(x)^m$ For $p\rightarrow +\infty $ we get $f(x)=x^i$ So $f(x)=ax^b+c$ with $a=+-1$and $b|n$

solved at 4 AM after dying on (read: unable to solve) other problems in DNY-euclid (how do i unbad...) All functions of the form $f(x) = \pm x^{D} + c$ where $c \in \mathbb{Z}$ and $D \in \mathbb{N}$ and $D \mid n$ work. It is clear that these do work by well known identities. Observe that if $g(x) = f(x) - f(0)$ satisfies the condition then $f(x)$ does as well; henceforth assume that $f(0) = 0.$ Note that \[ f(1) - f(0) \mid 1, \]so we obtain that $f(1) = \pm 1$. Assume from now on that $f(1) = 1$, as the other is handled in exactly the same manner. Now note that \[ f(1) - f(-1) \mid 1 - (-1) \implies f(-1) - 1 \mid 2, \]and also \[ f(-1) - f(0) \mid -1 \implies f(-1) \in \{-1, 1\}.\]In particular we must obtain that $f(-1) = -1$ as $0 \nmid 2$. Let $p$ be an arbitrarily large prime. Notice that \[ f(p) \mid p^n, \]so therefore for this value of $p$ we obtain that $f(p) = \pm p^d$ for some value $d$ and some choice of sign. Now assume that $f(p) = -p^d$ for some integer $d$, and let $k$ and $r$ be integers such that $dk+r=n$ and $0 \le r < d$. Then observe that \[ f(p) - f(-1) \mid p^n + 1 \]or \[ p^d - 1 \mid p^n + 1 \implies p^d - 1 \mid p^r + 1.\]Clearly for $p$ sufficiently large we can't have this. Therefore the negative sign is out. Now suppose that $f(p) = p^d$ for some integer $d \nmid n$, and let $k$ and $r$ be integers such that $dk+r=n$ and $0 < r < d$. Then observe that \[ f(p) - f(1) \mid p^n - 1 \]or \[ p^d - 1 \mid p^n - 1 \implies p^d - 1 \mid p^r - 1,\]again obviously impossible. Therefore for sufficiently large (realistically like $p>2$) we must have that $f(p) = p^d$ for some positive divisor $d$ of $n$. let $D$ be such that there are infinitely many primes $p$ such that $f(p) = p^D$. This exists as $n$ has a finite number of divisors. Now, \[ f(x) - p^D \mid x^n - p^n \implies f(x) - p^D \mid x^n - p^n - f(x)^{n/D} + p^n. \] However, taking $p$ incredibly large, we obtain that $f(x)^{n/D} = x^n$, or $f(x) = x^D$ for said divisor $D$. Undoing all the WLOG stuff we get our result.

The key idea is to realize that we can freely shift $f$ by a constant and that if $f$ works then $-f$ works. This implies that WLOG we can set $f(0) = 0$ and since $f(1) \mid 1$ take $f(1) = 1$. Now consider a particular prime $p$. Plug in $x = p$ and $y = 0$ to get $f(p) \mid p^n$. It follows that $f(p) = \pm p^m$ for some $m \leq n$. We will prove that $f(p) \neq -p^m$. Assume otherwise. Plugging in $m = p$ and $n = 1$ now yields $$-p^m-1 \mid p^n-1$$which is equivalent to $$p^m+1 \mid p^n-1$$Since $p^m+1 \mid p^{2m}-1$ we have $$p^m+1 \mid p^{\gcd(2m,n)}-1 = p^{\gcd(m,n)}-1$$because $n$ is odd. If $m > 0$ then $p^m +1$ is clearly greater than $p^{\gcd(m,n)}-1 \leq p^m-1$. It follows that $p^{\gcd(m,n)} -1 = 0$ or $m = 0$. This means that $f(p) = -1$. We will now prove that $f$ is injective. To see this, note that if $f(x) = f(y)$ then $x^n-y^n = 0$ so $x =y$ as desired. Plugging in $x = -1$ and $y = 0$ yields $f(-1) \mid -1$ but since $f$ is injective $f(-1) \neq f(1)$ so $f(-1) = -1$. It follows that $f(p) \neq f(-1) = -1$ so we arrive at a contradiction and $f(p) = p^m$ as desired. If $f(p) = p^m$ plugging in $x = p$ and $y = 1$ yields $$p^m-1 \mid p^n-1$$which means $m \mid n$. So, for a particular $p$ we have $f(p) = p^m$ where $m$ is a factor of $n$. Since there are infinitely many primes and only a finite number of factors of $n$, there has to exist a $k \mid n$ such that $f(p) = p^k$ for infinitely many primes $p$, not just a particular value of $p$. Now note that $$p^k - f(y) \mid p^n-y^n$$and $$p^k-f(y) \mid p^n-f(y)^{\frac{n}{k}}$$implies $$p^k-f(y) \mid f(y)^{\frac{n}{k}}-y^n$$The RHS is now not dependent on $p$ and we are free to take a big enough $p$ such that we force $f(y)^{\frac{n}{k}} = y^n$ which yields $f(y) = y^k$. Recalling that we can freely shift and negate, our answer is thus $f(y) = \pm y^k + c$ for some constant $c$.

It's obvious that if f is a sol then f+c is also a sol, so is -f, so WLOG f(0)=0, and henceforth ignore the +c and sign stuff; (1,0) gives f(1)=1, (p,0) for a prime p gives $f(p)=p^k$ (WLOG from f$\leftrightarrow$-f), (p,1) gives $p^k-1\mid p^n-1\implies k\mid n$. Now, since n has finite divisors but f is infinite, take $f(p)=p^k$ where there are infinite p that give the same k. Then, $f(x)-p^k\mid x^n-p^n-f(x)^{n/k}+p^n$; taking sufficiently large p (there are infinite of them), since the RHS doesn't depend on p, once the LHS>RHS we must have RHS=0, so $x^n=f(x)^{n/k}\iff f(x)=x^k$ for all x, as desired.

WLOG shift $f$ and invert such that $f(0) = 0$ and $f(1) = 1$. Claim: For primes $p$, $f(p) = p^k$ for some not fixed integer $k \mid n$. Proof. Note that $f(x) \mid x^n$ and $f(1) = 1$. Let $f(p) = p^k$. Then $p^k - 1 \mid p^n - 1$ so $p^{\gcd(n,k)} - 1 = p^k - 1$, and thus $k \mid n$. $\blacksquare$ Claim: For all $n$, $f(y) = y^k$ for $y \le n$ and some fixed $k$. Proof. Take a prime $q > n^{n^n}$. Then \[ q^k - f(y) \mid (q^n - y^n) - (q^n - f(y)^{\frac{n}{k}}) = f(y)^{\frac{n}{k}} - y^n \]so $f(y)^{\frac{n}{k}} = y^n$ and $f(y) = y^k$ for all $y \le n$. $\blacksquare$ Then $k$ is independent of $n$ by considering $f(2)$, so $f(x) = x^k$ for all $k$. As such, $f(x) = \pm x^k + c$ for $k \mid n$ is the solution set.

There exists a positive integer $d$ dividing $n$, $c \in \mathbb{Z}$ and an $\epsilon \in \{1, -1\}$ such that $f(x) = \epsilon x^d + c$ for all $x \in \mathbb{Z}$. If $f$ is a solution, then for all $c \in \mathbb{Z}$, $f - c$ is a solution. Thus we can assume that $f(0) = 0$. Then since $f(x) - f(0) \mid x^n - 0^n$, so $f(x) \mid x^n$. Thus for all prime $p$, we have $f(p) \mid p^n$. Since if $f$ is a solution, then $-f$ is also a solution, so we can assume $f(1) = 1$. Let $f(p) = \epsilon p^k$ for some $\epsilon \in \{-1, 1\}$, $k \le n$. Then $\epsilon p^k - 1 \mid p^n - 1$, thus $k \mid n$ and $\epsilon = 1$ for all prime $p$. Since there are infinitely many primes, so by pigeonhole principle, there are infinitely many primes $p$ such that $f(p) = p^d$ for some $d \mid n$. Now take large enough prime $p$ such that $f(p) = p^d$. Then $f(x) - f(p) \mid x^n - p^n$, so $x^n - p^n \equiv x^n - f(x)^{\frac{n}{d}} (f(x) - p^d)$. Since $p$ is large enough, this forces $f(x) = x^d$. Thus $f(x) = \epsilon x^d + c$ for some constant $c$, $\epsilon \in \{1, -1\}$, $d \mid n$. So we're done. $\blacksquare$

The answer is $f(x) = \varepsilon \cdot x^d + c$ for any $d \mid n$, $\varepsilon \in \{-1, 1\}$, and $c$ an integer. These obviously work. To show that these are the only functions, note that if $f$ works, then $f+c$ works for any $c \in \mathbb Z$; thus, we may assume $f(0) = 0$. Furthermore, $f(1) - f(0) \mid 1$, and we can also assume $f(1) = 1$. Now fix some prime $p$. As $f(p) \mid p^n$, set $f(p) = p^k$ for some $k$. Furthermore, because $f(p) - 1 \mid p^n - 1$, we have $k \mid n$. I claim that $k$ is consistent across all $p$. To show this, assume that $f(q) = q^\ell$. Then as $p^k - q^\ell \mid p^n - q^n$, we have $$p^k - q^{\ell} \mid p^{k+n-\ell} - q^n - p^n + q^n = p^n(p^{\ell - k} - 1).$$As the LHS is relatively prime to $p^n$, it follows for size reasons that $p^{\ell - k} = 1$, or $\ell = k$. So we have $f(p) = p^d$ for some fixed $d$ across all primes. Then for any $n$, by setting $p$ big we have $$f(x) - p^d \mid x^d - f(x)$$implying $f(x) = x^d$ too.

I was absolutely delighted by this problem. Really loved this!! The solutions are $f(x) \equiv x^d + c$ and $f(x) \equiv -x^d + c$, where $d>0$ and $d \mid n$, $c\in\mathbb Z$. Note that scaling the function by a constant does not effect the condition $f(x) - f(y) \mid x^n - y^n$. So WLOG assume that $f(0) = 0$. Also note that if $f$ works, then $-f$ works too. So multiplying the entire function by $-1$ does not change the condition either. We will use this fact later on. Firstly note that $f$ is injective. Otherwise let $f(a) = f(b)$ for $a\neq b$. But then substituting $P(a,b)$ gives a contradiction as the divisor becomes undefined. Now note that $P(1,0) \implies f(1) \mid 1$ and $P(-1,0) \implies f(-1) \mid -1$. So we get that $f(1),f(-1) \in \left\{+1,-1\right\}$. Now using the injectivity, we get that one of them must equal $1$. So let, $f(a) = 1$. Let $\left\{p_i\right\}$ be the sequence of primes. $P(p_i,0) \implies f(p_i) \mid p_i^n \implies f(p_i) = p_i^{k_i}$ for some $1 \le k_i \le n$. I claim that there are infinitely many $i$ such that $f(p_i) = p_i^{d_i}$ where $d_i$ is a positive divisor of $n$. Suppose on the contrary that there are finitely many such $i$. Thus there are infinitely many $j$ for which $f(p_j) = p_j^{k_j}$ where $k_j$ is not a divisor of $n$. By infinite PHP, we get a sequence of primes $\left\{q_i\right\}$ for which $f(q_i) = q_i^k$ where $k$ is fixed. $P(q_i,a) \implies f(q_i) - 1 \mid q_i^n - a^n \implies q_i^k - 1 \mid q_i^n - a^n$. Now let $n = ks + t$ where $0 < t < k$. Then we get that, \[ q_i^k - 1 \mid q_i^n -a^n \equiv (q_i^k)^s \cdot q_i^t - a^n \equiv (1)^s \cdot q_i^t - a^n = q_i^t - a^n. \] But then note that $a^n$ is just a constant. So after some sufficiently large $q_i$, we get that $q_i > a^n$. Thus we get that $q_i^k -1 \le q_i^t - a^n$ for all large enough $q_i$. We obviously have that $k > t$ and thus by taking a very large $q_i$, we get a contradiction. Thus we must have had that there are infinitely many $i$ such that $f(p_i) = p_i^{d_i}$ where $d_i$ is a positive divisor of $n$. Now again by infinite PHP, we get that $f(p_i) = p_i^d$ where $d$ is a fixed divisor of $n$. Now we fix some $u \in \mathbb Z$. Then note that $f(u) - f(p_i) \mid f(u)^{n/d} - f(p_i)^{n/d}= f(u)^{n/d} - p_i^n$. Then we have that, \[ P(u,p_i) \implies f(u) - f(p_i) \mid u^n - p_i^n \equiv (u^n - p_i^n) - (f(u)^{n/d} - p_i^n) = u^n - f(u)^{n/d} \implies f(u) - p_i^d \mid u^n - f(u)^{n/d}. \] Now taking a sufficiently large $p_i$, we get that $u^n - f(u)^{n/d} \equiv 0$ that is $f(u) = u^d$. Now since $u$ was arbitrary, and we are done.

We claim our only answers are $\boxed{f(x)=-x^a+b, ~ f(x)=-x^a+b}$, where $a \mid n$. Denote the assertion as $A(x,y)$. Shifting tells us $b$ can be any integer, so we can assume WLOG $f(0)=0$. $A(1,0)$ gives us the $\pm$, so we can assume WLOG $f(1)=1$, from which $A(-1,0)$ forces $f(-1)=-1$. Consider an arbitrarily large prime $p$. Then $A(p,0)$ and $A(p,1)$ implies $f(p)=p^a$, where $a \mid n$. Consider a prime $q<p$. Then $A(p,q)$ says \[p^a-q^b = f(p)-f(q) \mid p^n-q^n, \quad p^a-q^b \mid p^n-q^{nb/a}.\] Hence the LHS must also divide $q^{nb/a}-q^n$. Since $p$ is arbitrarily large, we must have $\frac{nb}{a}=n$, or $a=b$, so $f(x)=x^a$ for all primes. Fix an integer $x$, and let $n=ka+r$, where $0 \leq r \leq k-1$. Now $A(p,x)$ says \[p^a-f(x) = f(p)-f(x) \mid p^n-x^n = p^r \cdot f(p)^k-x^n,\]\[p^a-f(x) \mid p^r \left(f(p)^k-f(x)^k\right).\] Hence the LHS must also divide $p^r \cdot f(x)^k - x^n$, from which the size and infinite possibilities of $p$ forces this quantity to be 0 and $r=0$. Hence $f(x)=x^a$ for all $x$. $\blacksquare$

The answer is $x^d + C$ and $-x^d + C$ for any positive integer $d\mid n$ and integer constant $C$. These clearly work. Now we show they are the only solutions. Let $P(x,y)$ denote the assertion that\[ f(x) - f(y) \mid x^n - y^n\]Since $f$ works iff $x + c$ works, we may WLOG that $f(0) = 0$. Now, since $f$ works iff $-f$ works, we may WLOG $f(1) \ge 0$. It suffices to show that $f(x) = x^d$ for some positive integer $d$ dividing $n$. Claim: $f$ is injective Proof: If $f(a) = f(b)$, then $P(a,b)$ gives $0\mid a^n - b^n$, so $a^n = b^n \implies a = b$. $\square$ $P(x,0): f(x) \mid x^n$ Now setting $x = 1$ here gives that $f(1) \mid 1$. Since $f(1) \ge 0$, $f(1) = 1$. Similarly, setting $x = -1$ gives $f(-1) \mid 1$. Since $f(1) \ne f(-1)$, we have $f(-1) = -1$. For any prime $p$, $P(p,0)$ gives that $f(p) \mid p^n$, so $|f(p)|$ must be a power of $p$. Claim: For any prime $p$, we have $f(p) > 0$. Proof: Suppose otherwise. By injectivity, $f(p) \ne 0$. Let $f(p) = -p^k$ for some positive integer $k \le n$. $P(p,1)$ gives that $p^k + 1 \mid p^n - 1$, so $p^k + 1 \mid p^{nk} - 1$. Since $n$ is odd, we also have $p^k + 1\mid p^{nk} + 1$, so $p^k + 1 \mid 2$, which is absurd. $\square$ Hence $f(p)$ is a power of $p$ for any prime $p$. Then by infinite pigeonhole there exists a positive integer $d \le n$ such that infinitely many primes $p$ satisfy $f(p) = p^d$. For any such prime $p$, $P(p,1)$ gives $p^d - 1 \mid p^n - 1$. Now $p^n \equiv 1\pmod{p^d - 1}$, so $\frac{p^n}{p^{dk}}$ is also $1\pmod{p^d - 1}$, meaning that $p^d - 1 \mid p^{n - kd} - 1$ for any positive integer $k$. If $d \nmid n$, we could choose $k$ such that $1 \le a = n - kd \le d - 1$. We have $p^d - 1 \mid p^a - 1$, which is a contradiction by size as $1 \le a < d$. Therefore, $d \mid n$. Now, if $p$ is a prime with $f(p) = p^d$, then $P(x,p)$ gives $f(x) - p^d \mid x^n - p^n$. Hence $f(x) - p^d \mid x^{nd} - p^{nd}$. Since $f(x) - p^d \mid f(x)^n - p^{nd}$, we have\[f(x) - p^d \mid x^{nd} - p^{nd} - (f(x)^n - p^{nd}) = x^{nd} - f(x)^n \]Taking $p$ sufficiently large gives that $x^{nd} = f(x)^n$, so $f(x) = x^d$, as desired.

Shift and invert $f$ so that $f(0) = 0, f(1) = 1$. Then some case-checking and bounding shows that for all primes $p$, $f(p) = p^a$ with $a \mid n$. Choose the $a$ that appears infinitely many times (which exists by infinite PHP). Now for $y = p$ satisfying the condition, $f(x) - y^a \mid x^n - y^n \implies f(x) - y^a \mid x^n - f(x)^{\frac{n}{a}}$. As this means the quantity on the RHS has infinitely many divisors, we do indeed have $f(x) = x^a$ for fixed $a \mid n$. Un-transforming, the general function is $f(x) = cx^a + d,$ where $c \in \{-1, 1\}, d \in \mathbb{Z}, a \mid n$.

Note for the start of the solution, for simplicity, we only play around for the answer $f(x)=x^k+c$ for $k\mid n$, but the solution $f(x)=-x^k+c$ for $k\mid n$ can be gotten by completely analog means. Claim: $f(p)=p^k+f(0)$ for some $k\mid n$ Proof: Consider the assertion $P(p,0)$ where $p$ is a prime, we get: \[ f(p)-f(0) \mid p^n \implies f(p)=p^k+f(0) \quad \text{for some $k\leq n$} \]Now consider the assertions $P(p,q)$ where $p$ and $q$ are prime: \[ f(p)-f(q) \mid p^n-q^n \iff p^k-q^l \mid p^n - q^n \]Notice that this is an expression on which we can use the Euclidean algorithm and get something beneficial: \[ p^k-q^l \mid p^n - q^n-(p^n-q^{l}\cdot p^{n-k}) \implies p^k-q^l \mid p^{n-k} - q^{n-l} \]WLOG assume that $k>l$, which means that the power of $p$ is going to be the first one to dip under its respective power (basically, what I mean is that after appyling Euclidean algorithm we will get that the power of $p$ is smaller then $k$). So after applying the Euclidean algorithm a couple of times, we will get \[ p^k-q^l \mid p^x - q^y \quad \text{where} \quad x<k \]But now we can just say that we pick $p$ which is large enough so and $q$ small enough, in that way we can make it so that $p^k-q^l > p^x - q^y $ Thus we conclude that $k=l$, now we are looking at (also assuming $p\neq q$) \[ p^k-q^k \mid p^n-q^n \]We can now proceed by the Euclidean algorithm or we can simply just scream out cyclotomic polynomials and conclude $k\mid n$ Claim: $f(p^a)=p^{ak}+f(0)$ for any integer $a$ and for $k\mid n$ Proof: This is basically as above, only exception is a little uglier exponents Claim: $f(pq)=(pq)^k+f(0)$ for some $k\mid n$ Proof: Okay so we have some structure for primes, but let's extend this to integers which are made up of $2$ primes. By simillar methods as above, we have that $f(pq)=p^k\cdot q^l+f(0)$, and once again, consider the assertion $P(pq,q)$ we get \[ p^kq^l-q^r\mid p^nq^n-q^n \iff q^r(p^kq^{l-r}-1)\mid q^n(p^n-1) \]Now we have $p^kq^{l-r}-1\mid (p^n-1)$, since we can take $q$ to be sufficiently large, we either have $p=1$ (which is a no) or $l=r$ Remark: We immediately saw that we must have $l\geq r$, in the other case we get \[ p^k-q^{r-l} \mid p^n-1 \]But this is absurd since we can make $p^n-1$ have infinitely many divisors by moving $q$ around Now assume we consider the assertion $P(pq,p)$, we get something which looks like \[ p^kq^l-p^r\mid p^nq^n-p^n \]By the same reasoning as above we can conclude that $r=l$, hence proving that the degree of $p$ and $q$ is the same. Claim: $f(p^aq^b)=(p^aq^b)^k+f(0)$ for $k\mid n$ Proof: By considering $P(p^aq^b,0)$ we get that $f(p^aq^b)=p^xq ^y$ such that $x\leq an$ and $y \leq bn$. Now we consider the assertion $P(p^aq^b, p^a)$: \[ p^x(p^{ak-x}-q^y)\mid p^{an}(q^{an}-1) \]Since $p^{ak-x}-q^y \nmid p^{an}$ we have \[ p^{ak-x}-q^y \mid q^{an}-1 \]But since we can select a huge $p$ we have that either $q=1$ (a no), or $ak=x$ (which is a yes) Claim: $f(n)=(n)^k+f(0)$ for $k\mid n$ Proof: Let $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \cdots p_m^{\alpha_m}$ This is a generalization of the above. We consider the following assertions \[ P(n, p_1^{\alpha_1}) \quad P(n,p_2^{\alpha_2}) \quad \dots \quad P(p_m^{\alpha_m}) \]We basically prove the claim for every prime $p$, as seen when we have only $2$ primes, this simply works because we can always selects a huge prime that is not present in the denominator. Hence finally we can conclude: $f(x)=\pm x^k+c$ for $k\mid n$ and any integer $c$

Note that if $f$ is a solution then so is $-f+a$ for some constant $a.$ Thus, we can suppose WLOG that $f(0)=0$ and $f(1)=1.$ \[P(p,0) : f(p) \mid p^n\]which implies that $f(p)=\pm p^k$ for some non negative integer $k.$ Now, $P(1,p)$ gives that $1\pm p^k \mid p^n -1.$ If $f(p)=-p^k,\quad O_{1-p^k}(p)\mid (2k,n)$ but does not divide $k$ which is impossible. Hence $f(p)$ is a power of $p$ for all primes $p.$ Moreover, \[p^k-1\mid p^n-1 \implies O_{p^k-1}(p)\mid n \iff k \mid n.\]By piegonhole principle, there is a infinity of prime numbers and a fixed divisor of $n$ named $c,$ such that $f(p)=p^c.$ Now, fix $x$ and take a large enough such a prime and observe that \[0\equiv x^n-p^n =x^n -{p^{c}}^{\frac{n}{c}} \equiv x^n-f(x)^{\frac{n}{c}}\pmod{f(x)-p^c}\]For large enough $p^c,$ we have $x^n=f(x)^{n/c} \iff f(x)=x^c.$ Whence the answer is $f\equiv \pm x^c+a $ for some constant $a$ and $c$ divisor of $n.$