Number Theory

  • Thread starter pupeye11
  • Start date
  • #1
100
0

Homework Statement



The idea of this problem is to investigate the solutions to x^2=1 (mod pq), where p,q are distinct odd primes.

(a) Show that if p is an odd prime, then there are exactly two solutions (mod p) to x^2=1 (mod p). (Hint: difference of two squares)

(b) Find all pairs (a,b) such that a^2=1 (mod p) and b^2=1 (mod q)

(c) Let p=17 and q=23. For each pair (a,b) from part (b), compute an integer x modulo 17*23 such that x=a(mod 17) and x=b(mod 23)

(d) Verify that each integer found in part (c) is a solution to x^2=1 (mod 17*23)

The Attempt at a Solution



For part (a), rewrite it as x^2-1= 0 (mod p). Then that splits into (x+1)(x-1)= 0 (mod p). which can be further split into (x+1)= 0 (mod p) and (x-1)= 0 (mod p). Then since p is an odd prime x= -1+p (mod p) cannot equal x=1 (mod p) so there are exactly two solutions.

I have no idea where to start on (b) though.
 

Answers and Replies

  • #2
360
0
(b) looks like it follows immediately from (a) to me. You know the 2 solutions for a and the 2 solutions for b, which should give you 4 pairs, I think.
 
  • #3
100
0
Yup, I don't know why I didn't see that right away. Thanks!
 

Related Threads on Number Theory

  • Last Post
Replies
2
Views
826
  • Last Post
Replies
2
Views
984
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
954
  • Last Post
Replies
2
Views
783
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
733
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
4
Views
2K
Top