Problem 6

Let

p

be a prime number. Prove that there exists a prime number

q

such that for every integer

n

, the number

n^p-p

is not divisible by

q

Step 1 of 3: Choose a prime divisor

Previous step Next step

In plain words

Choose a prime divisor

\Phi_p(p)=1+p+\cdots+p^{p-1}\equiv1+p\pmod{p^2}

Detailed analysis

No prime divisor of $\Phi_p(p)$ equals $p$ . If all its prime divisors were $1\pmod{p^2}$ , the product would be $1\pmod{p^2}$ , contradicting the displayed congruence. Choose $q\mid\Phi_p(p)$ with $q\not\equiv1\pmod{p^2}$ .