1. ## Euler phi

Show that $a^{\phi(b)}+b^{\phi(a)} \equiv 1 \pmod{ab}$ if a and b are relatively prime.

Starting with a and b are relatively prime I get

$a^{\phi(b)} \equiv 1 \pmod{b}
$

$
b^{\phi(a)} \equiv 1 \pmod{a}
$

But I am not sure how to combine the moduli to get $\pmod{ab}$. Would Chinese Remainder Theorem be the right approach?

2. Originally Posted by RonyPony
Show that $a^{\phi(b)}+b^{\phi(a)} \equiv 1 \pmod{ab}$ if a and b are relatively prime.

Starting with a and b are relatively prime I get

$a^{\phi(b)} \equiv 1 \pmod{b}
$

$
b^{\phi(a)} \equiv 1 \pmod{a}
$

But I am not sure how to combine the moduli to get $\pmod{ab}$. Would Chinese Remainder Theorem be the right approach?
$\begin{cases} a^{\varphi(b)}-1 \equiv 0 \bmod{b}\\b^{\varphi(a)}-1 \equiv 0 \bmod{a}\end{cases}\implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}$ as $(a,b)=1$

But $0\equiv(a^{\varphi(b)}-1)(b^{\varphi(a)}-1)=a^{\varphi(b)}b^{\varphi(a)}-a^{\varphi(b)}-b^{\varphi(a)}+1=ab\left\{a^{\varphi(b)-1}b^{\varphi(a)-1}\right\}-a^{\varphi(b)}-b^{\varphi(a)}+1$

$\equiv-a^{\varphi(b)}-b^{\varphi(a)}+1\bmod{ab}$

3. Originally Posted by chiph588@
$\implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}$ as $(a,b)=1$
Why are we allowed to do this step?

4. Originally Posted by RonyPony
Why are we allowed to do this step?
Actually that step is wrong... Try this:

$a^{\varphi(b)}\equiv1\bmod{b}\implies a^{\varphi(b)}+b^{\varphi(a)}\equiv1\bmod{b}$

$b^{\varphi(a)}\equiv1\bmod{a}\implies b^{\varphi(a)}+a^{\varphi(b)}\equiv1\bmod{a}$

Since $(a,b)=1$, $a^{\varphi(b)}+b^{\varphi(a)}\equiv1\bmod{ab}$

5. Is the last step is from Chinese remainder theorem?

6. Originally Posted by Also sprach Zarathustra
Is the last step is from Chinese remainder theorem?
See this page on MathWorld, property #11. Note that $\gcd(a,b) = 1 \implies \text{lcm}(a,b)=ab$.

7. Originally Posted by Also sprach Zarathustra
Is the last step is from Chinese remainder theorem?
$x\equiv y\bmod{n}$ and $x\equiv y\bmod{m}$ where $(n,m)=1\implies x\equiv y\bmod{nm}$

This is because $x=y+nk$ and $x=y+mj \implies nk=mj\implies m\mid nk\implies m\mid k$ since $(n,m)=1$.

This means $k=mr$. Thus $x=y+nmr\implies x\equiv y\bmod{nm}$.

8. Originally Posted by chiph588@
$\implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}$
You said this step is wrong, why?
If $a|c$ and $b|d$, then $ab|cd$ regardless, even, of $a$ and $b$ being relatively prime. Here, $a$ and $b$ divide $b^{\varphi(a)}-1$ and $a^{\varphi(b)}-1$, respectively. Then $ab|(b^{\varphi(a)}-1)(a^{\varphi(b)}-1)$.
Is it correct?

9. Originally Posted by melese
You said this step is wrong, why?
If $a|c$ and $b|d$, then $ab|cd$ regardless, even, of $a$ and $b$ being relatively prime. Here, $a$ and $b$ divide $b^{\varphi(a)}-1$ and $a^{\varphi(b)}-1$, respectively. Then $ab|(b^{\varphi(a)}-1)(a^{\varphi(b)}-1)$.
Is it correct?
Yes you are correct. I had a lapse in clear thought for a bit. Thanks for pointing that out.