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, 10: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 4th 2010, 11:09 PMroninpro
You should try using the Chinese Remainder Theorem.

It will suffice to show that and simultaneously. Keep in mind that . - November 4th 2010, 11:43 PMkimberu
- November 5th 2010, 12: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, 01:04 AMkimberu
Thank you so much! I think I understand it now.