Solving x^2=1 (mod pq) with Odd Primes

[pupeye11]

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.

 

[spamiam]

(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.

 

[pupeye11]

Yup, I don't know why I didn't see that right away. Thanks!