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.

Printable View

- Nov 4th 2010, 10:28 PMkimberuEuler'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. - Nov 4th 2010, 11:09 PMroninpro
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)$. - Nov 4th 2010, 11:43 PMkimberu
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?

- Nov 5th 2010, 12:50 AMmelese
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$. - Nov 5th 2010, 01:04 AMkimberu
Thank you so much! I think I understand it now.