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

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.

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.
• But my question was is it obvious that $(q,n)=1$? – Jyotishraj Thoudam Jun 7 '17 at 16:16
• You don't understand what I said. If $q\nmid n$, then the official solution handles it. The official solution ignores the case $q\mid n$ because, as I stated in my answer, this is the trivial case. – Batominovski Jun 7 '17 at 16:18
• Ok. So, the first question was, are we choosing $n$ to be $\frac{p^p-1}{p-1}$ ? – Jyotishraj Thoudam Jun 7 '17 at 16:20