1. ## Euler's totient function

If n=rs, r>2 and s>2, gcd(r,s)=1, show $\displaystyle a^{\phi(n)/2}$ ≡ 1 (mod n).

I really have no ideas -- something with Euler's Criterion maybe? -- any help would be appreciated. Thanks.

2. You should try using the Chinese Remainder Theorem.

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

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

It will suffice to show that $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{r}$ and $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{s}$ simultaneously. Keep in mind that $\displaystyle \varphi(n)=\varphi(rs)=\varphi(r)\varphi(s)$.
Thank you! In trying the Chinese Remainder Theorem on those two congruences, if I set x = $\displaystyle 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 $\displaystyle \equiv$ 1 (mod r) and rx $\displaystyle \equiv$ 1 (mod s). Did I do something wrong here?

4. Note that here $\displaystyle gcd(a,n)=1$, and therefore $\displaystyle gcd(a,r)=gcd(a,s)=1$.

Euler's Theorem implies that $\displaystyle a^{\phi(r)}\equiv1\bmod r$; also $\displaystyle \phi(r)$ is even since $\displaystyle r\geq3$. Hence $\displaystyle 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 $\displaystyle a^{(\phi(r)\cdot\phi(s))/2}\equiv1\bmod s$.

By hypothesis $\displaystyle gcd(r,s)=1$, so we can merge the main congruences to one that is equivalent, namely $\displaystyle a^{\phi(r)\cdot\phi(s))/2}\equiv1\bmod rs$. But $\displaystyle \phi(n)=\phi(r)\cdot\phi(s)$, so $\displaystyle a^{\phi(n)/2}\equiv1\bmod n$.

5. Thank you so much! I think I understand it now.