# Euler's totient function

• Nov 4th 2010, 10:28 PM
kimberu
Euler's totient function
If n=rs, r>2 and s>2, gcd(r,s)=1, show $a^{\phi(n)/2}$ ≡ 1 (mod n).

I really have no ideas -- something with Euler's Criterion maybe? -- any help would be appreciated. Thanks.
• Nov 4th 2010, 11:09 PM
roninpro
You should try using the Chinese Remainder Theorem.

It will suffice to show that $a^{\varphi(n)/2}\equiv 1\pmod{r}$ and $a^{\varphi(n)/2}\equiv 1\pmod{s}$ simultaneously. Keep in mind that $\varphi(n)=\varphi(rs)=\varphi(r)\varphi(s)$.
• Nov 4th 2010, 11:43 PM
kimberu
Quote:

Originally Posted by roninpro
You should try using the Chinese Remainder Theorem.

It will suffice to show that $a^{\varphi(n)/2}\equiv 1\pmod{r}$ and $a^{\varphi(n)/2}\equiv 1\pmod{s}$ simultaneously. Keep in mind that $\varphi(n)=\varphi(rs)=\varphi(r)\varphi(s)$.

Thank you! In trying the Chinese Remainder Theorem on those two congruences, if I set x = $a^{\varphi(n)/2}$, I get that N1 = rs/r = s and N2 = rs/s = r, and then I get stuck again at solving sx $\equiv$ 1 (mod r) and rx $\equiv$ 1 (mod s). Did I do something wrong here?
• Nov 5th 2010, 12:50 AM
melese
Note that here $gcd(a,n)=1$, and therefore $gcd(a,r)=gcd(a,s)=1$.

Euler's Theorem implies that $a^{\phi(r)}\equiv1\bmod r$; also $\phi(r)$ is even since $r\geq3$. Hence $a^{(\phi(r)\cdot\phi(s))/2}=(a^{\phi(r)})^{\phi(s)/2}\equiv1^{\phi(s)/2}=1\bmod r$. In a similar way, we have the congruence $a^{(\phi(r)\cdot\phi(s))/2}\equiv1\bmod s$.

By hypothesis $gcd(r,s)=1$, so we can merge the main congruences to one that is equivalent, namely $a^{\phi(r)\cdot\phi(s))/2}\equiv1\bmod rs$. But $\phi(n)=\phi(r)\cdot\phi(s)$, so $a^{\phi(n)/2}\equiv1\bmod n$.
• Nov 5th 2010, 01:04 AM
kimberu
Thank you so much! I think I understand it now.