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

1. May 20, 2012

### nonequilibrium

1. The problem statement, all variables and given/known data
Define $n = 3^{100}+2$. Suppose $x^2-53 \equiv 0 \mod n$ has no solution. Prove that n is not prime.

2. Relevant equations
/

3. 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...

2. Jun 3, 2012

### tt2348

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