2
$\begingroup$

Can anyone show some hints to this? If $\gcd(a,b)=1$, then $a^{\phi(b)}+b^{\phi(a)}=1 \pmod{ab}$. I know that $a^{\phi(b)}=1 \pmod{b}$, and similarly, $b^{\phi(a)}=1 \pmod{a}$, but then how do I combine the work so that I get the result I need? Thanks!

  • 0
    @Arturo Magidin: Thank you$a$lot for guiding me within this wonderful math forum.2011-02-18

2 Answers 2

5

It's just $\rm\ (0,1) + (1,0)\: =\: (1,1)\ $ in $\rm\ \mathbb Z/a \times \mathbb Z/b\:,\ $ i.e. $\rm\ a^{\phi(b)}\to (0,1)\ $ being $\ 0\:$ mod $\rm\:a\:,\ 1\: $ mod $\rm\: b$

This is the special case $\rm\ \alpha = \beta = 1\ $ in the following form of the Chinese Remainder Theorem:

THEOREM (CRT) $\rm\ \ $ If $\rm\ a,\:b\:$ are coprime integers then

$\rm\displaystyle\quad\quad\quad\quad\quad x\equiv \alpha\ (mod\ a),\ \ x\equiv \beta\ (mod\ b)\ \ \iff\ \ x\ \equiv\ \alpha\ b^{\phi(a)}+ \beta\ a^{\phi(b)} \ \ (mod\ a\:b)$

Proof $\rm\ (\Leftarrow)\ \ $ Immediate from $\rm\ b^{\phi(a)}\equiv 1\ (mod\ a),\ \ a^{\phi(b)}\equiv 1\ (mod\ b)\:$.

$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ ab)\ $ since if \rm\ x',\:x\ are solutions then \rm\ x'\equiv x\ mod $\rm\:a,b\:$ therefore \rm\ a,\:b\ |\ x'-x\ \Rightarrow\ a\:b\ |\ x'-x\ \ since $\rm\ \:a,\:b\:$ coprime $\rm\:\Rightarrow\ lcm(a,b) = a\:b\:.\quad\quad$ QED

11

Verify the congruence holds modulo $a$ and modulo $b$. Then use the fact that if $a|k$, $b|k$, and $\gcd(a,b)=1$, then $ab|k$.