Euler phi

**RonyPony** · July 6th 2010, 09:46 AM

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?

**chiph588@** · July 6th 2010, 10:06 AM

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}$

**RonyPony** · July 6th 2010, 11:28 AM

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?

**chiph588@** · July 6th 2010, 11:51 AM

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}$

**Also sprach Zarathustra** · July 6th 2010, 11:59 AM

Is the last step is from Chinese remainder theorem?

**undefined** · July 6th 2010, 12:02 PM

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$ .

**chiph588@** · July 6th 2010, 12:05 PM

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}$ .

**melese** · July 6th 2010, 03:19 PM

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?

**chiph588@** · July 6th 2010, 04:09 PM

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.

Thread: Euler phi

LinkBack

Thread Tools

Display

Euler phi

Similar Math Help Forum Discussions

Euler path and Euler circuit problem

Graph Theory - To Euler or not to Euler? With attempted working.

wats the relation between Fermat, Euler, Euler–Jacobi

euler phi-function

Euler Phi Help

Search Tags