13
$\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$

3 Answers 3

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$
1
  • $\begingroup$ ooh... Bezout helper :-) $\endgroup$
    – robjohn
    Jun 26, 2012 at 6:34
7
$\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$
2
  • 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, 2013 at 14:28
  • 1
    $\begingroup$ Can you elaborate the last line? $\endgroup$ Jun 20, 2020 at 6:08
2
$\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.