1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 20, 2012 #1
    1. The problem statement, all variables and given/known data
    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.

    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 [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...
  2. jcsd
  3. Jun 3, 2012 #2
    I dunno if it's a problem you're already done with, but try applying the lucas primality test?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook