uniolympiads Ελληνικά

IMC 2011, Day 1, Problem 3

Let pp be a prime number. Call a positive integer nn interesting if

xn−1=(xp−x+1)f(x)+pg(x)x^n - 1 = (x^p - x + 1)f(x) + pg(x)

for some polynomials ff and gg with integer coefficients.

a) Prove that the number pp−1p^p - 1 is interesting.

b) For which pp is pp−1p^p - 1 the minimal interesting number?

Eugene Goryachko and Fedor Petrov, St. Petersburg

Original from the official PDFLet p be a prime number. Call a positive integer n interesting if x n − 1 = (x p − x + 1)f (x) + pg(x) for some polynomials f and g with integer coefficients. a) Prove that the number p p − 1 is interesting. b) For which p is p p − 1 the minimal interesting number? (Eugene Goryachko and Fedor Petrov, St. Petersburg)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Eugene Goryachko and Fedor Petrov, St. Petersburg)

Solution. (a) Let's reformulate the property of being interesting: nn is interesting if xn−1x^n-1 is divisible by xp−x+1x^p-x+1 in the ring of polynomials over Fp\mathbb F_p (the field of residues modulo pp). All further congruences are modulo xp−x+1x^p-x+1 in this ring. We have xp≡x−1x^p\equiv x-1, then xp2=(xp)p≡(x−1)p≡xp−1≡x−2x^{p^2}=(x^p)^p\equiv(x-1)^p\equiv x^p-1\equiv x-2, xp3=(xp2)p≡(x−2)p≡xp−2p≡x−2p−1≡x−3x^{p^3}=(x^{p^2})^p\equiv(x-2)^p\equiv x^p-2^p\equiv x-2^p-1\equiv x-3 and so on by Fermat's little theorem, finally xpp≡x−p≡xx^{p^p}\equiv x-p\equiv x,

x(xpp−1−1)≡0.x(x^{p^p-1}-1)\equiv0.
Since the polynomials xp−x+1x^p-x+1 and xx are coprime, this implies xpp−1−1≡0x^{p^p-1}-1\equiv0.

(b) We write

x1+p+p2+⋯+pp−1=x⋅xp⋅xp2⋅…⋅xpp−1≡x(x−1)(x−2)…(x−(p−1))=xp−x≡−1,x^{1+p+p^2+\dots+p^{p-1}}=x\cdot x^p\cdot x^{p^2}\cdot\ldots\cdot x^{p^{p-1}}\equiv x(x-1)(x-2)\ldots(x-(p-1))=x^p-x\equiv-1,
hence x2(1+p+p2+⋯+pp−1)≡1x^{2(1+p+p^2+\dots+p^{p-1})}\equiv1 and a=2(1+p+p2+⋯+pp−1)a=2(1+p+p^2+\dots+p^{p-1}) is an interesting number.

If p>3p>3, then a=2p−1(pp−1)<pp−1a=\frac{2}{p-1}(p^p-1)<p^p-1, so we have an interesting number less than pp−1p^p-1. On the other hand, we show that p=2p=2 and p=3p=3 do satisfy the condition. First notice that by gcd(xm−1,xk−1)=xgcd(m,k)−1gcd(x^m-1,x^k-1)=x^{gcd(m,k)}-1, for every fixed pp the greatest common divisors of interesting numbers is also an interesting number. Therefore the minimal interesting number divides all interesting numbers. In particular, the minimal interesting number is a divisor of pp−1p^p-1.

For p=2p=2 we have pp−1=3p^p-1=3, so the minimal interesting number is 11 or 33. But x2−x+1x^2-x+1 does not divide x−1x-1, so 11 is not interesting. Then the minimal interesting number is 33.

For p=3p=3 we have pp−1=26p^p-1=26 whose divisors are 1,2,13,261,2,13,26. The numbers 11 and 22 are too small and x13≡−1≢+1x^{13}\equiv-1\not\equiv+1 as shown above, so none of 11,22 and 1313 is interesting. So 2626 is the minimal interesting number.

Hence, pp−1p^p-1 is the minimal interesting number if and only if p=2p=2 or p=3p=3.

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?