Solve the congruence. Please Help

  • #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!
 

Answers and Replies

  • #2
35,052
6,788
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.
 

Related Threads on Solve the congruence. Please Help

  • Last Post
Replies
22
Views
246
  • Last Post
Replies
4
Views
8K
Replies
2
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
734
Top