I need help with problems 3941 and 42 Solution39 Note that 5

I need help with problems 39,41 and 42

Solution

39. Note that 561 = 3 * 11 * 17.

(i) Working mod 3, we know that 2^2 = 1 (mod 3) (by Fermat or direct computation).
So, 2^560 = (2^2)^280 = 1^280 = 1 (mod 3).

(ii) Working mod 11, we know that 2^10 = 1 (mod 11) (by Fermat).
So, 2^560 = (2^10)^28 = 1^28 = 1 (mod 11).

(iii) Working mod 17, we know that 2^16 = 1 (mod 17) (by Fermat).
So, 2^560 = (2^16)^35 = 1^35 = 1 (mod 17).

Since 3, 11, and 17 are pairwise relatively prime, we conclude by the Chines Remainder Theorem that 2^560 = 1 (mod 561).