godelproof is right. i will put it in a slightly different way.
It's been established that . Assume that . since is a prime we have .
LEMMA: If then iff .
PROOF: Its easy to see that .
Taking , from the above we have can leave at most distinct remainders when divided by . we put and using computation find that . from the blue colored statement above we immediately arrive at the required result.
from the above lemma we have iff or , . so the only prime value can take is and for it can be computationally verified that .
we have now proved that if is prime. so contrary to assumption. QED.