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

[nonequilibrium]

Homework Statement

Define $n = 3^{100}+2$. Suppose $x^2-53 \equiv 0 \mod n$ 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 $\left( \frac{53}{n} \right) \equiv 53^{ \frac{n-1}{2} } \mod n$ (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 $\left( \frac{53}{n} \right) = -1$. So assuming n is prime, we have that $-1 \equiv 53^{ \frac{n-1}{2} } \mod n$. 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?