Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

share|cite|improve this answer

Your Answer


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.