1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Homework Help: [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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook