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

  • $\begingroup$ what is A? and how did you get it using the CRT? $\endgroup$ – joseph Nov 19 '18 at 18:06
  • $\begingroup$ the CCRT case link attached above is for primes p and q.. does it matter that m and n are just relatively prime in this case? $\endgroup$ – joseph Nov 19 '18 at 18:07
  • $\begingroup$ @mjoseph $A := a^{\large [\phi(m),\phi(n)]}$. You proved $\,A\equiv 1\pmod m$ and $\,A\equiv 1\pmod n$ $\endgroup$ – Bill Dubuque Nov 19 '18 at 18:10
  • $\begingroup$ @mjoseph The first $3$ proofs in the link work for arbitrary coprime moduli (I added a remark emphasizing that). $\endgroup$ – Bill Dubuque Nov 19 '18 at 18:14
  • $\begingroup$ Just looked at the link a little more and understand it now. Thank you! $\endgroup$ – joseph Nov 19 '18 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.