# Totient function and Euler's Theorem

Given $\big(m, n\big) = 1$, Prove that

$$m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \pmod{mn}$$

I have tried saying

$$\text{let }(a, mn) = 1$$

$$a^{\varphi(mn)} \equiv 1 \pmod{mn}$$

$$a^{\varphi(m)\varphi(n)} \equiv 1 \pmod{mn}$$

$$(a^{\varphi(m)})^{\varphi(n)} \equiv 1 \pmod{mn}$$

but I can't see where to go from here. I'm trying to somehow split the $a^{\varphi(mn)}$ into an addition so I can turn it into $m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \pmod{mn}$.

-

Hint What is $m^{\varphi(n)} + n^{\varphi(m)} \pmod{m}$? What about $\pmod n$?

-
$m^{\varphi(n)} + n^{\varphi(m)} \pmod{m} \equiv 1$ since $m^{\varphi(n)} \pmod{m} \equiv 0$ and $n^{\varphi(m)} \pmod{m} \equiv 1$. Same for $\pmod{n}$ except the other way around. –  mottese Mar 6 '13 at 15:51
@user1359900 And if some expression is $1 \pmod n$ and $1 \pmod m$ what can you say about the expression $\pmod{mn}$? –  N. S. Mar 6 '13 at 15:53
I see now. I was over-thinking this way too much. Thanks! –  mottese Mar 6 '13 at 15:56
@user1359900 yw :) –  N. S. Mar 6 '13 at 15:57

Hint $\$ If $\rm\,(m,n)=1\,$ then $\rm\ x \equiv a m^{\varphi(n)}\!\! + b n^{\varphi(m)}\,\ (mod\ mn)\iff \begin{eqnarray} x\equiv a&&\rm (mod\ n)\\ \rm x\equiv b&&\rm (mod\ m)\end{eqnarray}$

Yours is the special constant case of CRT: $\rm\:a = b\ (= 1),\:$ so $\rm\:mn\mid x\!-\!a\iff m,n\mid x\!-\!a$

-