# $k^{\phi(l)} + l^{\phi(k)} \equiv1\pmod{lk}\,$ if $\,\gcd(l,k)=1$

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 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 also $$\,j\equiv 1\pmod l,\,$$ so $$\,j\equiv 1\pmod{\!kl}\,$$ by CCRT.
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)\,$$ hence 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).$$
Similarly $$\,k^{l}\!+l^{k}\equiv k\!+\!l\pmod{\!kl}\,$$ via $$\to (k,k)\!+\!(l,l) =(k\!+\!l,k\!+\!l)$$