Given that $m,n > 2$ are relatively prime integers and that $a$ is an integer relatively prime to $mn$, prove that
$$ a^{{\rm lcm}(\phi(m), \phi(n))}\equiv 1 \pmod{mn} $$
I started by using the fact that
$$ {\rm lcm}(\phi(m), \phi(n)) = \alpha\phi(m)=\beta\phi(n) $$
for some positive integers $ \alpha , \beta $ to then applying Euler's $|phi$ theorem twice we have
$$ a^{\alpha\phi(m)}=(a^{\phi(m)})^\alpha\equiv(1)^\alpha\equiv1 \pmod{m} $$
and
$$ a^{\beta\phi(n)}=(a^{\phi(m)})^\alpha\equiv(1)^\beta\equiv1 \pmod{n} $$
I'm wondering if what I did was correct and how to apply the Chinese Remainder Theorem to show that this congruence is true mod mn.
Best Answer
Yes, it is correct. To finish, by CRT: $\,A\equiv 1\bmod m\ \&\ n\iff A\equiv 1\pmod{\!mn}.\,$ Or, w/o CRT, we have $\,m,n\mid A-1\iff {\rm lcm}(m,n)\mid A-1,\,$ and $\,{\rm lcm}(m,n) = mn\,$ by $\,\gcd(m,n)=1$
Remark $ $ This simple special case is known as CCRT = Constant-case Chinese Remainder Theorem
This is a special case of Carmichael's generalization of Euler's theorem - see here.