# Total Number of Solutions for a Pair of Congruences (Explanation Needed)

• Feb 12th 2013, 03:48 PM
Total Number of Solutions for a Pair of Congruences (Explanation Needed)
I have two questions, which are probably somewhat related:

1) Suppose we have congruences:
(a) x^r = 1 (mod p) and
(b) x^r = 1 (mod q),
where p and q are primes. Let's say the number of solutions of (a) is S_p and the number of solutions of (b) is S_q. I know that the number of solutions for x^r = 1 (mod pq) is now S_p * S_q, but the question is, why? Why are we multiplying? How is it possible to determine what are the solutions mod pq if we know the solutions mod p and mod q?

2) I know that to find out the number of invertible matrices in Z_pq (again, p and q are primes), we can calculate the number of invertible matrices in Z_p and Z_q. Suppose these are i_p and i_q (the amount of matrices whose determinant is not zero mod p / mod q). Then the amount of invertible matrices in Z_pq is i_p * i_q. Again, the question is, why is this?