Let M be the product of two distinct prime numbers p1 and p2, and let a be an integer chosen so that the greatest common factor of a and M is 1.
By considering the value of a^(p1-1)(p2-1) modulo p1 and modulo p2, or otherwise, prove that a^(p1-1)(p2-1) ≡ 1 mod M.
Angelos
Favorite Answer
By Fermat's little theorem, a^(p1-1) ≡ 1 mod p1.
So a^(p1-1)(p2-1) = [a^(p1-1)]^(p2-1) ≡ 1 mod p1.
Likewise, a^(p2-1) ≡ 1 mod p2, and
so a^(p1-1)(p2-1) = [a^(p2-1)]^(p1-1) ≡ 1 mod p2 as well.
But then a^(p1-1)(p2-1) - 1 is divisible by both p1 and p2;
so it must be divisible by their product M, QED