If n=rs, r>2 and s>2, gcd(r,s)=1, show ≡ 1 (mod n).

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

Printable View

- November 4th 2010, 11:28 PMkimberuEuler's totient function
If n=rs, r>2 and s>2, gcd(r,s)=1, show ≡ 1 (mod n).

I really have no ideas -- something with Euler's Criterion maybe? -- any help would be appreciated. Thanks. - November 5th 2010, 12:09 AMroninpro
You should try using the Chinese Remainder Theorem.

It will suffice to show that and simultaneously. Keep in mind that . - November 5th 2010, 12:43 AMkimberu
- November 5th 2010, 01:50 AMmelese
Note that here , and therefore .

Euler's Theorem implies that ; also is even since . Hence . In a similar way, we have the congruence .

By hypothesis , so we can merge the main congruences to one that is equivalent, namely . But , so . - November 5th 2010, 02:04 AMkimberu
Thank you so much! I think I understand it now.