Question

Reduce the following modular arithmetic without the use of a calculator: PLEASE STATE THE THEOREMS/RULES YOU USE AND EXPLAIN HOW. Thanks!!

a) 104^5 mod 2669

b) 11^132 mod 133

c) 2208^5 mod 2669

d) 7^1000 mod 5

e) 2^247 mod 35

Answer 1

Please find the solutions in reversed order:

Part-E:

By Fermat's Theorem we have

Now

Hence

------------------(1)

Similarly

By Fermat's Theorem we have

Now

Hence

-----------------(2)

From (1) and (2)

Part-D:

By Fermat's Theorem we have

Part-C:

By Fermat's Theorem we have

Also

Hence

-----------(1)

In the same way as above

-----(2)

From 1 and 2

Part-B:

By Fermats theorem

Thus

Part-A:

By using the same method as Part -C we have