- #1
nonequilibrium
- 1,439
- 2
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...