Maths Olympiad Prep

Library / /9 of 63

Number theory Difficulty 6.1 National olympiad Prove it Japan

Let pp be a prime. Determine all positive integers nn for which the following condition is satisfied for all the integers xx:
Condition: If xn1x^n - 1 is divisible by pp, then it is also divisible by p2p^2.

Solution

If, for a pair of integers a,ba, b and a positive integer mm, aba - b is divisible by mm, we write ab0(modm)a - b \equiv 0 \pmod{m}.
We will show that the numbers nn we seek are those of the form kpkp, where kk is a positive integer.
Let us first show that if nn satisfies the condition of the problem, then nn must be a multiple of pp. To see this let x=p+1x = p + 1. Then from xn11n10(modp)x^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{p}, we get the fact that xn1x^n - 1 is divisible by pp, and hence by the condition of the problem, is divisible by p2p^2 as well. By using the binomial expansion we get (p+1)nnp+1(modp2)(p+1)^n \equiv np + 1 \pmod{p^2}, and therefore, xn1np(modp2)x^n - 1 \equiv np \pmod{p^2}. This implies that npnp is a multiple of p2p^2, and therefore, nn must be a multiple of pp.

Conversely, we will show that if n=kpn = kp for a positive integer kk, then it satisfies the condition of the problem. First we note that xn=(xk)pxk(modp)x^n = (x^k)^p \equiv x^k \pmod{p} holds by Fermat's Little Theorem. This shows that if xn1x^n - 1 is a multiple of pp, then so is xk1x^k - 1. Now we have
xn1xk1=1+xk+x2k++x(p1)k1+1++1p0(modp), \frac{x^n - 1}{x^k - 1} = 1 + x^k + x^{2k} + \dots + x^{(p-1)k} \equiv \underbrace{1+1+\dots+1}_{p} \equiv 0 \pmod{p},
from which we conclude that xn1=(xk1)×xn1xk1x^n - 1 = (x^k - 1) \times \frac{x^n - 1}{x^k - 1} is a multiple of p2p^2. Thus, we see that n=kpn = kp satisfies the condition of the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.