Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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)$

share|improve this answer
1  
Just a nit-pick, the quotes theorem ($a^\phi(b) \equiv1 \mod(b)$) is actually called Euler's theorem. –  ramanujan_dirac 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) $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.