1 Use congruence to verify that 53103 10353 is divisivle by

1. Use congruence to verify that 53^103 + 103^53 is divisivle by 39.

2. Use congruence to verify that 2^44 - 1 is divisible by 89

Solution

1.

53=14 mod 39

103=-14 mod 39

53^103+103^53

=14^103-14^53 mod 39

Let us look at congruences of powers of 14 modulo 39

14=14 mod 39

14^2=196=195+1=1 mod 39

Hence, 14^2=1 mod 39

14^103=14 mod 39

14^53=14 mod 39

Hence proved

2.

We look at powers of 2 mod 89

2^2=4

2^4=4^2=16

2^8=16^2=256=-11

2^16=11^2=121=32=2^5

2^32=2^10=2^{8+2}=-11*4=-44

2^44=2^{32+8+4}=-44*-11*16=484*16=39*16=78*8=-11*8=-88=1

HEnce,

2^44=1 mod 89

2^44-1 =0 mod 89