[number theory] x²-a = 0 no solution => n not prime

[nonequilibrium]

Homework Statement

Define [itex]n = 3^{100}+2[/itex]. Suppose [itex]x^2-53 \equiv 0 \mod n[/itex] has no solution. Prove that n is not prime.

Homework Equations

/

The Attempt at a Solution

Well, I suppose that I'll have to prove that some identity which should be true for n prime is not satisfied in the above case. The only relevant thing that I can think of is that if n were prime, then [itex]\left( \frac{53}{n} \right) \equiv 53^{ \frac{n-1}{2} } \mod n[/itex] (the first symbol denoting the Jacobi symbol). From now on assume n is prime; I try to find a contradiction.

The fact that the stated equation has no solution, is translated into [itex]\left( \frac{53}{n} \right) = -1[/itex]. So assuming n is prime, we have that [itex]-1 \equiv 53^{ \frac{n-1}{2} } \mod n[/itex]. However, I don't see how to arrive at a contradiction, nor do I see another way to approach the problem...

 

[tt2348]

I don't know if it's a problem you're already done with, but try applying the lucas primality test?