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$ enter image description here

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.

  • $\begingroup$ But my question was is it obvious that $(q,n)=1$? $\endgroup$ – Jyotishraj Thoudam Jun 7 '17 at 16:16
  • $\begingroup$ 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. $\endgroup$ – Batominovski Jun 7 '17 at 16:18
  • $\begingroup$ Ok. So, the first question was, are we choosing $n$ to be $\frac{p^p-1}{p-1}$ ? $\endgroup$ – Jyotishraj Thoudam Jun 7 '17 at 16:20
  • 1
    $\begingroup$ Well, read Comment 1 in the official solution. It gives an explanation of this "pulling a rabbit out of a hat" trick. $\endgroup$ – Batominovski Jun 7 '17 at 18:53
  • 1
    $\begingroup$ When I first read your name, I read Batmanovski hahah. $\endgroup$ – Mr Pie Mar 2 '18 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.