[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?