# Euler phi

• July 6th 2010, 10:46 AM
RonyPony
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?
• July 6th 2010, 11:06 AM
chiph588@
Quote:

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}$
• July 6th 2010, 12:28 PM
RonyPony
Quote:

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?
• July 6th 2010, 12:51 PM
chiph588@
Quote:

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}$
• July 6th 2010, 12:59 PM
Also sprach Zarathustra
Is the last step is from Chinese remainder theorem?
• July 6th 2010, 01:02 PM
undefined
Quote:

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$.
• July 6th 2010, 01:05 PM
chiph588@
Quote:

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}$.
• July 6th 2010, 04:19 PM
melese
Quote:

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?
• July 6th 2010, 05:09 PM
chiph588@
Quote:

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.