Can some explain how modular arithmetic works

52 Views Asked by At

Say I have a problem like 2^191 divided by 5, how can I solve this using only modular arithmetic?

1

There are 1 best solutions below

4
On BEST ANSWER

Here note that $2^4\equiv 1 \pmod 5 \implies (2^4)^{47} \equiv 1^{47} \pmod 5 \implies (2^4)^{47} \times 2^3 \equiv 1^{47} \times 8 \pmod 5 \\ \implies 2^{191} \equiv 3\pmod 5. $

$2^4 = 16 = 15+1$.