Divisibility forces a power function — but why must the exponent divide n?

cursed_bonfire·Sep 5, 2025(edited)

After normalizing

f(0)=0

, I see that

f(p)

is a signed power of p for primes p. I can't see why that information on an infinite set of primes determines f at every integer. Problem: 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}

. Source: IMO 2011 Shortlist · MNET-06RM

Open MNET-06RM in the question bank →

7 replies

tarnished_ish·Sep 6, 2025(edited)

The condition forces injectivity: if

f(x)=f(y)

, divisibility by zero means

x^n=y^n

, and odd n gives x=y. There are finitely many possible signed exponents at primes, so one value

\varepsilon p^d

occurs for infinitely many primes. Change the sign of f if necessary.

cursed_bonfire·Sep 6, 2025(edited)

Could d be zero? Then we would only know

f(p)=1

tarnished_ish·Sep 6, 2025(edited)

Injectivity excludes that on an infinite set. Thus d≥1. Write

n=md+r

with

0\le r<d

. For fixed x and those primes p,

p^d-f(x)

divides

p^r f(x)^m-x^n

MissingNo404·Sep 6, 2025(edited)

The divisor grows like

p^d

, while that remainder grows at most like

p^r

. For sufficiently large p the remainder has smaller absolute value than the divisor, so it must be zero.

cursed_bonfire·Sep 6, 2025

For x=1, f(1) is nonzero. Then

p^r f(1)^m=1

for infinitely many p forces r=0. Is that the clean way to justify that step?

tarnished_ish·Sep 6, 2025

Yes. Now

f(x)^m=x^n

for every x. Since n is odd and d divides n, m is odd, so

f(x)=x^d

. Restoring the sign and constant gives

f(x)=c\pm x^d

, where d is a positive divisor of n.

cursed_bonfire·Sep 7, 2025

And the converse is the factorization

X^m-Y^m

with

X=x^d

Y=y^d

. I had proved only that these were examples, not that there were no others.