# 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.

-

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.

-
ooh... Bezout helper :-) – robjohn Jun 26 '12 at 6:34

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)$

-
Just a nit-pick, the quotes theorem ($a^\phi(b) \equiv1 \mod(b)$) is actually called Euler's theorem. – user23238 Apr 27 '13 at 14:28

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)$

-