IMO Shortlist 2011, Number Theory 3

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Jul 11, 2012, 10:27 PM • 8 Y

Y by Davi-8191, anantmudgal09, jhu08, Adventure10, Mango247, BorivojeGuzic123, cubres, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

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

MellowMelon

5850 posts

MellowMelon

#2 h Jul 12, 2012, 1:37 PM • 10 Y

Y by theproductof6by9, Anar24, jhu08, Adventure10, BorivojeGuzic123, Newmaths, and 4 other users

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.

Z K Y

The post below has been deleted. Click to close.

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

leshik

433 posts

leshik

#3 h Jul 12, 2012, 8:27 PM • 3 Y

Y by jhu08, Adventure10, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

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

hal9v4ik

368 posts

hal9v4ik

#4 h Jul 12, 2012, 9:46 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

Can someone post IMO Shortlist 2011 on contest page?

Z K Y

The post below has been deleted. Click to close.

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

KittyOK

349 posts

KittyOK

#5 h Jul 15, 2012, 3:12 AM • 3 Y

Y by jhu08, Adventure10, Mango247

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.$

Z K Y

The post below has been deleted. Click to close.

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

ACCCGS8

326 posts

ACCCGS8

#6 h Jul 15, 2012, 6:26 AM • 2 Y

Y by jhu08, Adventure10

$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.

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#7 h Jul 15, 2012, 9:03 AM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

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

harazi

5526 posts

harazi

#8 h Jul 15, 2012, 10:06 PM • 3 Y

Y by jhu08, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

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

eaglet

6 posts

eaglet

#9 h Jul 17, 2012, 7:19 AM • 3 Y

Y by jhu08, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#10 h Jul 17, 2012, 7:37 AM • 5 Y

Y by eaglet, jhu08, Adventure10, Mango247, and 1 other user

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?

Z K Y

The post below has been deleted. Click to close.

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

Isogonics

185 posts

Isogonics

#11 h Feb 5, 2014, 7:35 AM • 2 Y

Y by jhu08, Adventure10

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.)

Z K Y

The post below has been deleted. Click to close.

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

junioragd

314 posts

junioragd

#12 h Feb 8, 2015, 7:13 PM • 3 Y

Y by IgorM, jhu08, Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

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

JuanOrtiz

366 posts

JuanOrtiz

#13 h Apr 2, 2015, 9:55 PM • 2 Y

Y by jhu08, Adventure10

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$ .

This post has been edited 6 times. Last edited by JuanOrtiz, Apr 2, 2015, 10:03 PM

Z K Y

The post below has been deleted. Click to close.

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

anantmudgal09

1980 posts

anantmudgal09

#14 h Jan 25, 2017, 1:25 PM • 4 Y

Y by jhu08, SatisfiedMagma, Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

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

H.R.

172 posts

H.R.

#15 h Feb 9, 2017, 10:23 AM • 2 Y

Y by jhu08, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

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

vsamc

3789 posts

vsamc

#34 h Jun 9, 2023, 6:55 PM

Y by

Solution

This post has been edited 1 time. Last edited by vsamc, Jun 9, 2023, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

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

popop614

271 posts

popop614

#35 h Jun 19, 2023, 1:31 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

andyxpandy99

365 posts

andyxpandy99

#36 h Aug 24, 2023, 3:21 PM

Y by

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$ .

This post has been edited 1 time. Last edited by andyxpandy99, Aug 24, 2023, 3:26 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

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

huashiliao2020

1292 posts

huashiliao2020

#38 h Sep 4, 2023, 8:42 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

YaoAOPS

1526 posts

YaoAOPS

#39 h Sep 22, 2023, 3:49 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

thdnder

194 posts

thdnder

#40 h Oct 5, 2023, 8:42 AM

Y by

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$

This post has been edited 1 time. Last edited by thdnder, Oct 5, 2023, 8:43 AM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#41 h Dec 17, 2023, 12:54 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

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

kamatadu

478 posts

kamatadu

#42 h Jan 7, 2024, 6:20 PM

Y by

I was absolutely delighted by this problem. Really loved this!! :love:

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. :yoda:

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#43 h Mar 13, 2024, 4:03 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5593 posts

megarnie

#44 h Aug 18, 2024, 2:50 PM • 1 Y

Y by bjump

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.

Z K Y

The post below has been deleted. Click to close.

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

AshAuktober

993 posts

AshAuktober

#45 h Jan 2, 2025, 1:15 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

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

Zsnim

6 posts

Zsnim

#46 h Jan 7, 2025, 8:04 PM

Y by

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$

This post has been edited 1 time. Last edited by Zsnim, Jan 7, 2025, 8:09 PM
Reason: LaTeX fixing

Z K Y

The post below has been deleted. Click to close.

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

math004

23 posts

math004

#47 h Feb 3, 2025, 11:28 PM

Y by

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.$

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1729 posts

OronSH

#49 h Feb 21, 2025, 8:52 PM • 3 Y

Y by megarnie, megahertz13, gvh300

We claim $f(x)=(-1)^ix^d+c$ for $d\mid n$ are the solutions, which clearly work.

Shift so that $f(0)=0$ . Then $P(p,0)$ implies $f(p)=\pm p^d\mid p^n$ . Additionally $P(\pm 1,0)$ gives $P(\pm 1)=\pm 1$ so the product of $P(p,\pm 1)$ gives $p^{2d}-1\mid p^{2n}-1$ . By a euclidean algorithm argument, $2d\mid 2n$ so $d\mid n$ . Thus there exists some $i\in\{0,1\}$ and $d\mid n$ for which $f(p)=(-1)^ip^d$ for infinitely many primes $p$ .

Then $P(x,p)$ gives $f(x)-(-1)^ip^d\mid x^n-p^n$ , but $f(x)-(-1)^ip^d\mid f(x)^{\frac nd}-(-1)^ip^n$ so combining these we have $f(x)-(-1)^ip^d\mid f(x)^{\frac nd}-(-1)^ix^n$ for infinitely many $p$ , implying $f(x)^{\frac nd}-(-1)^ix^n=0$ , or $f(x)=(-1)^ix^d$ for all $x$ . Shifting back gives the desired.

This post has been edited 1 time. Last edited by OronSH, Feb 21, 2025, 8:59 PM

Z K Y

The post below has been deleted. Click to close.

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

InterLoop

274 posts

InterLoop

#50 h Apr 15, 2025, 12:26 AM

Y by

solution

Z K Y