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: Solve the congruence. Please Help

  1. Mar 24, 2009 #1
    Determine whether or not the following congruence has a solution:
    x^2 = 78 (mod 41503). If a solution exist then find a positive integer that satisfies the solution. Here, = means "congruent to".

    I understand the fact that if 78 is the quadratic residue of 41503 then we have a solution but I don't know how I should do that? Should I break down 78 into factors of prime and then try to verify using quadratic reciprocity? Assuming that there IS a solution, how do I find an integer that satisfies the congruent? Please help! thanks!
  2. jcsd
  3. Mar 24, 2009 #2


    Staff: Mentor

    So x2 - 78 [itex]\equiv[/itex] 0 mod 41503, or
    x2 - 78 = 41503k, for some integer k.

    A brute force approach would be to substitute five of ten values for k (such as 1 through 5 or 10), and see if you can get a solution. The problem asks for only one solution, and you might get lucky and find one this way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook