Compute large exponents in modular arithmetic


Compute the remainder when 37^{100} is divided by 29.

Performing all arithmetic mod 29, we have 39^{100} = 8^{100}. Moreover, note that
8^{28} = (8^2)^2 \cdot ((8^2)^2)^2 \cdot (((8^2)^2)^2)^2
 = 6^2 \cdot (6^2)^2 \cdot ((6^2)^2)^2
 = 7 \cdot 7^2 \cdot (7^2)^2
 = 7 \cdot 20 \cdot 20^2
 = 140 \cdot 23
 = 24 \cdot 23
 = 552
 = 1.
So we have 8^{100} = 8^{28} \cdot 8^{28} \cdot 8^{28} \cdot 8^{16} = 8^{16} = 23, as computed above.





No comments:

Post a Comment