11
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ooh... Bezout helper :-) $\endgroup$ – robjohn Jun 26 '12 at 6:34
6
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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