Show that if $\gcd(a,pq)=1$ and $g=\gcd (p-1, q-1)$ then $a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$.

Question

Suppose $p\neq q$ are two primes and $g=\gcd (p-1, q-1)$

Show that if $\gcd(a,pq)=1$, then $$a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$$

Hi, how to do?

I have no idea how to begin, Thanks.

Answer 1

Use the Chinese Remainder Theorem (or at least the idea behind the Chinese Remainder Theorem) and Fermat's Little Theorem.

For instance, since $g$ divides $q-1$, we see that $$ a^{\frac{(p-1)(q-1)}{g}} = \left( a^{\frac{q-1}{g}} \right)^{p-1} \equiv 1 \pmod p $$ by Fermat's Little Theorem. Doing the same for $q$ and combining gives a complete proof.

Answer 2

Well, by Fermat's little theorem you know that $a^{p-1}\equiv1\pmod p$; the same would hold for any exponent which is a multiple of $p-1$. Now look at that $\frac{(p-1)(q-1)}{g}$ thing: is it not a multiple of $p-1$ (and also $q-1$)? Now, if a number equals 1 modulo $p$ and also modulo $q$, what it might be like modulo $pq$? (Hint)