- #1
pupeye11
- 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.