Answer to Question #260105 in Discrete Mathematics for King

Question

(a) Use Fermat’s little theorem to compute: 4101 mod 5, 4101 mod 7, 4101 mod 11.

(b) Use your results from part (a) and the Chinese Remainder Theorem to compute

4

101 mod 385. (note that 385 = 5 × 7 × 11).

Answer 1

a) $4^{101} mod 5$

$4^2mod5=1$

$4^{101}mod5=4^{100+1}mod5=(4*4^{2*50})mod5=(4*(4^{2})^{50})mod5=4*1^{50}=4$

b) $4^{101} mod 7$

$4^3mod7=1$

$4^{101}mod7=4^{100+1}mod7=(4^2*4^{3*33})mod7=(4^2*(4^{3})^{33})mod7=(4^2*1^{33})mod7=2$

c) $4^{101} mod 11$

$4^5 mod 11=1$

$4^{101}mod11=4^{100+1}mod11=(4*4^{5*20})mod11=(4*(4^{5})^{20})mod11= 4*1^{20}=4$

We have that $M{\scriptscriptstyle 1}={\frac {385} 5}=77$ , and the inverse of 77 modulo 5 is y1 = 3. As well, $M{\scriptscriptstyle 1}={\frac {385} 7}=55$ , and the inverse of 55 modulo 7 is y2 = 6. Finally, $M{\scriptscriptstyle 1}={\frac {385} {11}}=35$ , and the inverse of 35 modulo 11 is y3 = 6. Thus, by the Chinese Remainder Theorem, the solution has the form:

$4^{101}mod385= (4*77*3(mod385) +2*55*6(mod385) +4*35*6(mod385))$ mod385 =

= 114