# Prove that $a^{[\phi(m), \phi(n)]} \equiv 1 \pmod{mn}$

Given that $$m,n > 2$$ are relatively prime integers and that $$a$$ is an integer relatively prime to $$mn$$, prove that $$a^{[\phi(m), \phi(n)]}\equiv 1 \pmod{mn}$$

I started by using the fact that

$$[\phi(m), \phi(n)] = \alpha\phi(m)=\beta\phi(n)$$ for some positive integers $$\alpha , \beta$$ to then write

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

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
• @mjoseph $A := a^{\large [\phi(m),\phi(n)]}$. You proved $\,A\equiv 1\pmod m$ and $\,A\equiv 1\pmod n$ – Bill Dubuque Nov 19 '18 at 18:10
• @mjoseph The first $3$ proofs in the link work for arbitrary coprime moduli (I added a remark emphasizing that). – Bill Dubuque Nov 19 '18 at 18:14