Proving there exists a prime $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$.

Question

The problem I found was from the 2003 IMO Problem 6.

Let p be a prime number. Prove that there exists a prime q such that for every integer n, the number $n^p-p$ is not divisible by q.

I studied one version of the solution which started with the expanded form of the equation, $${\frac{p^p-1}{p-1}}$$ Then, it is quite obvious that we would find atleast one prime divisor of ${\frac{p^p-1}{p-1}}$ which is not congruent to $1$ $mod$ $p^2$. Denoting this prime divisor as $q$. And in the solution it stated that this $q$ is what we wanted.

I don't understand why this is the q we sought for in the first place. I also don't understand how this $q$ is related to the $q$ we wanted in forming the proof.

Also, from the method of reasoning in the solution, it deduced by stating Fermat's Little Theorem that $n^{q-1}=1$mod$q$. I don't understand how $n$ is coprime to $q$, because this version of FLT is true only for $(q,n)=1$

So, please help me clear my doubts and also if it wouldn't be too much of a trouble, please tell​ your versions of the solution. FYI, I have also tried reading the discussions on Art of problem solving site, that didn't help.

Answer 1

If $q \mid n$, then $q\mid n^p-p$ implies that $q\mid p$, but it is obvious that $\gcd(p,q)=1$. For the other question, it's better that you point out what you don't understand.

---

Claim: If $q$ is a prime natural number such that $n^p-p$ is not divisible by $q$ for every integer $n$, then $q\equiv 1\pmod{p}$.

Proof: First, it is obvious that $q\neq p$. If $q\not\equiv1\pmod{p}$, then $p\nmid q-1$, and therefore any residue modulo $q$ has a $p$-th root modulo $q$. To show this, we note that $px+(q-1)y=1$ for some $x,y\in\mathbb{Z}$. Thus, for any $a\not\equiv0\pmod{p}$, we have $$\left(a^x\right)^p=a^{px}\equiv a^{px}(1)^{y}\equiv a^{px}\left(a^{q-1}\right)^y=a^{px+(q-1)y}=a^1=a\pmod{q}\,.$$ In particular, the congruence $n^p\equiv p\pmod{q}$ has a solution modulo $q$. This is a contradiction, so $q\equiv 1\pmod{p}$ has to be satisfied.