# Euler phi

• Jul 6th 2010, 09:46 AM
RonyPony
Euler phi
Show that $\displaystyle 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

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

But I am not sure how to combine the moduli to get $\displaystyle \pmod{ab}$. Would Chinese Remainder Theorem be the right approach?
• Jul 6th 2010, 10:06 AM
chiph588@
Quote:

Originally Posted by RonyPony
Show that $\displaystyle 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

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

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

$\displaystyle \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 $\displaystyle (a,b)=1$

But $\displaystyle 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$

$\displaystyle \equiv-a^{\varphi(b)}-b^{\varphi(a)}+1\bmod{ab}$
• Jul 6th 2010, 11:28 AM
RonyPony
Quote:

Originally Posted by chiph588@
$\displaystyle \implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}$ as $\displaystyle (a,b)=1$

Why are we allowed to do this step?
• Jul 6th 2010, 11:51 AM
chiph588@
Quote:

Originally Posted by RonyPony
Why are we allowed to do this step?

Actually that step is wrong... Try this:

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

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

Since $\displaystyle (a,b)=1$, $\displaystyle a^{\varphi(b)}+b^{\varphi(a)}\equiv1\bmod{ab}$
• Jul 6th 2010, 11:59 AM
Also sprach Zarathustra
Is the last step is from Chinese remainder theorem?
• Jul 6th 2010, 12: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 $\displaystyle \gcd(a,b) = 1 \implies \text{lcm}(a,b)=ab$.
• Jul 6th 2010, 12:05 PM
chiph588@
Quote:

Originally Posted by Also sprach Zarathustra
Is the last step is from Chinese remainder theorem?

$\displaystyle x\equiv y\bmod{n}$ and $\displaystyle x\equiv y\bmod{m}$ where $\displaystyle (n,m)=1\implies x\equiv y\bmod{nm}$

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

This means $\displaystyle k=mr$. Thus $\displaystyle x=y+nmr\implies x\equiv y\bmod{nm}$.
• Jul 6th 2010, 03:19 PM
melese
Quote:

Originally Posted by chiph588@
$\displaystyle \implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}$

You said this step is wrong, why?
If $\displaystyle a|c$ and $\displaystyle b|d$, then $\displaystyle ab|cd$ regardless, even, of $\displaystyle a$ and $\displaystyle b$ being relatively prime. Here, $\displaystyle a$ and $\displaystyle b$ divide $\displaystyle b^{\varphi(a)}-1$ and $\displaystyle a^{\varphi(b)}-1$, respectively. Then $\displaystyle ab|(b^{\varphi(a)}-1)(a^{\varphi(b)}-1)$.
Is it correct?
• Jul 6th 2010, 04:09 PM
chiph588@
Quote:

Originally Posted by melese
You said this step is wrong, why?
If $\displaystyle a|c$ and $\displaystyle b|d$, then $\displaystyle ab|cd$ regardless, even, of $\displaystyle a$ and $\displaystyle b$ being relatively prime. Here, $\displaystyle a$ and $\displaystyle b$ divide $\displaystyle b^{\varphi(a)}-1$ and $\displaystyle a^{\varphi(b)}-1$, respectively. Then $\displaystyle 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.