# Proof of an equality involving $\phi(n)$

I would like to prove the following equality: $$k^{\phi(l)} + l^{\phi(k)} \equiv1\pmod{lk}$$if $\gcd(l,k)=1$. What methods can I use? Thank you for your help.

• Euler's theorem – Dane Bouchie Aug 11 '14 at 20:53

Hint: use the Chinese Remainder Theorem (i.e. consider the experession $\pmod l$ and $\pmod k$)
Hint $\ {\rm mod}\ k\!:\ j := k^{\phi(l)}\!+l^{\phi(k)}\!\equiv 0+l^{\phi(k)}\!\equiv 1\,$ by Euler's Theorem. By symmetry $\,j\equiv 1\pmod l.\,$ Therefore $\ k,l\mid j-1\,\Rightarrow\,kl\mid j-1,\$ by $\,{\rm lcm}(k,l) = kl,\,$ by $\,\gcd(k,l)=1.$
Remark $\$ If you know about rings and the CRT isomorphism $\,\Bbb Z/kl \,\cong\, \Bbb Z/k\times\Bbb Z/l\,$ we have $\,k^{\phi(l)}\!\to (0,1)\,$ and $\,l^{\phi(k)}\!\to (1,0)\,$ therefore their sum $\to (0,1)+(1,0)= (1,1),\,$ the image of $\,1.$ Notice $\,e_1 = (0,1),\, e_2 = (1,0)\,$ are the idempotents of the the direct sum decomposition, which are employed by CRT to compute $\,x \equiv (a,b)\ {\rm mod}\ (k,l)\,$ via $\,(a,b) = a(1,0) + b(0,1).$