Show that $a^{\phi(b)}+b^{\phi(a)} \equiv 1 (\text{mod }ab)$ , if a and b are relatively prime positive integers. Show that 
$a^{\phi(b)}+b^{\phi(a)} \equiv 1 (\text{mod} ab)$,
if a and b are relatively prime positive integers.
Note that $\phi(n)$ counts the number of positive integers not exceeding n which are relatively prime with n.
 A: Since $gcd(a,b)=1$, by Fermat's little theorem, $a^{\phi(b)}\equiv1 (\mod{b})$.
Now, $b^{\phi(a)}\equiv 0(\mod{b})(\because b\mid b^{\phi(a)}).$
So now we have, $a^{\phi(b)}+b^{\phi(a)}\equiv 1(\mod{b}).\tag{1}$
Again by Fermat little theorem,
$b^{\phi(a)}\equiv 1(\mod{a}).$
And $a^{\phi(b)}\equiv 0(\mod{a})(\because a\mid a^{\phi(b)})$
From this we have,
$a^{\phi(b)}+b^{\phi(a)}\equiv 1(\mod{a})\tag{2}$
From $(1)$ and $(2)$, we have,
$a^{\phi(b)}+b^{\phi(a)}\equiv 1(\mod{ab}), (\because (a,b)=1)$
A: Use Euler's Theorem,
$$a^{\phi (b)}+b^{\phi (a)} \equiv a^{\phi (b)}\equiv 1 (mod \space b) $$
$$a^{\phi (b)}+b^{\phi (a)} \equiv b^{\phi (a)}\equiv 1 (mod \space a) $$
So, $a^{\phi (b)}+b^{\phi (a)} \equiv 1 (mod \space ab) $
A: Hint $\rm\ x = a^{\phi(b)}\!+\!b^{\phi(a)}\! \equiv 1\:$ mod $\rm\:a\:$ and $\rm\:b\:$ by Euler. $\!$ So $\rm\:a,b\:|\:x\!-\!1\:\Rightarrow\:lcm(a,b)=ab\:|\:x\!-\!1.$
Remark $\ $ This yields a closed-form solution of CRT (Chinese Remainder Theorem)
$\quad$ If $\rm\,\ (a,b)=1\,\ $ then $\rm\quad \begin{eqnarray}\rm x\! &\equiv&\,\rm \alpha\ \ (mod\ a)\\ \rm x\! &\equiv&\,\rm \beta\ \ (mod\ b)\end{eqnarray} \iff\ x\,\equiv\, \alpha\,b^{\phi(a)}\!+\beta\:a^{\phi(b)}\ \ (mod\ ab)$
Your case is $\rm\:\alpha=1=\beta.\:$ More generally see the Peirce decomposition.
