# Solve the congruence. Please Help

1. Mar 24, 2009

### zzzcreepyzzz

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. Mar 24, 2009

### Staff: Mentor

So x2 - 78 $\equiv$ 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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook