# Modular Arithmetic and Fermat’s Little Theorem

Modular arithmetic is a way of counting in which the numbers wrap around after reaching a certain value. The clock is often used as an analogy. While time always progresses forward, the 12-hour clock “resets” to 1 after passing 12 (13 o’clock is equivalent to 1 o’clock). If we replace 12 with 0, we have the set known as ℤ_{12} which is made up of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. If we consider midnight as *t _{0}=0*, then 5 hours later is

*t*. 17 hours later will also be

_{5}=5*t*. 84 hours later will be

_{17}=5*t*. 85 hours later will be

_{84}= 0*t*. There is a pattern here. The value

_{85}= 1*a*in the set ℤ

_{12}corresponding to any other integer

*b*is the remainder when

*b*is divided by 12. We can write this mathematically as

*b ≡ a (mod 12)*, and we say “

*b*is congruent to

*a*modulo 12”

More generally, we can write the set of integers for any modulus *n* as ℤ_{n} = {0, 1, 2, 3, … n-1} . Each element *a* in ℤ_{n} represents not only a itself, but all of the *b*’s for which *b ≡ a (mod n)*. These elements are called congruence classes, and the set ℤ_{n} is a set made up of these classes. Sometimes, it’s more convenient to write the relationship as *b-a ≡ 0 (mod n)*, i.e. each *b* is assigned to a congruence class depending on how much needs to be subtracted to be divisible by *n*. Addition and multiplication can be done using modular arithmetic if you are using the same modulus. If *b ≡ a (mod n)* and *d ≡ c (mod n)*, then

*(b+d) ≡ (a+c) (mod n)**(b*d) ≡ (a*c) (mod n)*

Example 1. What is *84,872 (mod 5)*? A simple way to approach this problem is to find the closest multiple of 5 to 84,872. That is 84,870. Therefore, we can write *84,872 (mod 5) ≡ 84,870 (mod 5) + 2 (mod 5) ≡ 0 (mod 5) + 2 (mod 5) ≡ 2 (mod 5)*. Example 2. In modulo 10, what is 19,374 · 3,172? One way to attempt this problem is to multiply out these numbers and then find the remainder when dividing by 10. However, since we want our answer in modulo 10, we can instead multiply just the representatives from their congruence classes. The remainder when 19,374 is divided by 10 is 4, so *19,374 ≡ 4 (mod 10)* and *3,172 ≡ 2 (mod 10)*, so *(19,374 · 3,172) ≡ (2·4) (mod 10) ≡ 8 (mod 10)*. Example 3. In modulo 4, what is 180,700,247 + 64,987,422? Again we first find the congruence class for each number modulo 4. We can simplify each by breaking it into the sum of smaller multiples of 4. One possible way is to write* 180,700,247 ≡ 180,700,200 (mod 4) + 44 (mod 4) + 3 (mod 4) ≡ 0 (mod 4) + 0 (mod 4) + 3 (mod 4) ≡ 3 (mod 4)* Similarly, *64,987,422 ≡ 2 (mod 4)*. Therefore, *(180,700,247+ 64,987,422) ≡ (3 + 2) (mod 4) ≡ 5 (mod 4)*. However, 5 is not in the set ℤ_{4} = {0, 1, 2, 3}, so we must reduce *5 (mod 4)* to something in the set. We can simplify by noticing that *5 (mod 4) ≡ 4 (mod 4) + 1 (mod 4) ≡ 0 (mod 4) + 1 (mod 4) ≡ 1 (mod 4).*

## Fermat’s Little Theorem

One important application for modular arithmetic is Fermat’s Little Theorem which states that if *p* is a prime number and *a* is not divisible by *p*, then *a ^{p-1} ≡ 1 (mod p)*. This theorem is useful because allows you to find a remainder when dividing a really big number by a prime number. Example 4. What is the remainder when 2

^{784}is divided by 11? 2

^{784}is too big to put in most calculators and too time-consuming to multiply by hand. We can apply Fermat’s Little Theorem to make it easier to solve. From the theorem we know that

*2*. And we also know that we can multiply congruence classes with the same modulus. Therefore, one strategy we can apply is to write 2

^{10}≡ 1 (mod 11)^{784}as the product of as many 2

^{10}’s as possible. We can simplify as follows:

*2*. The remainder is 5.

^{784}= (2^{10})^{78}·(2^{4}) ≡ 1^{78}· 2^{4}(mod 11) ≡ 2^{4}(mod 11) ≡16 (mod 11) ≡ 5 (mod 11)