Introduction to Modular Arithmetic

Hello mathletes! In this post, we will be exploring the basics of modular arithmetic. Modular arithmetic is a system of arithmetic for integers, in which numbers "wrap around" upon reaching the modulus (plural moduli). The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

“Modulo n” includes numbers between 0 and n-1. The easiest way to convert numbers in modular arithmetic is by doing Euclidean Division and taking the remainder.

In r = n mod m, we can remove as many multiples of m as possible until we are left with an answer between 0 and m-1. In this case, r would be the remainder and m would be the modulus. So for example, 34 mod 4 = 2 and 19 mod 7 = 5. If n is a negative number, then we add as many multiples of m as needed to have an answer between 0 and -(m-1). Thus, -23 mod 5 = 2 and -78 mod 9 = 3.

Here are some basic properties of Modular Arithmetic:

1> [ (a mod n) + (b mod n) ] mod n = ( a + b) mod n

ex) [(37 mod 6) + (99mod 6)] = 4 mod 6 = 4 and (37 + 99) mod 6 = 136 mod 6 = 4

2> [ (a mod n) - (b mod n) ] mod n = (a - b) mod n

ex) [ (37 mod 6) - (99mod 6)] mod 6 = -2mod 6 = 4 and (37 - 99)mod 6 = -62 mod 6 = 4

3> [ (a mod n)* (b mod n)] mod n = ab mod n

ex) [ (37mod6) * (99mod6)] mod 6 = 3 mod 6 = 3 and (37* 99) mod6 = 3663 mod 6 = 3

Lastly, the set of integers {0, 1, 2, …, n − 1} is called the least residue system modulo n. Any set of n integers, no two of which are congruent modulo n, is called a complete residue system modulo n. It is clear that the least residue system is a complete residue system, and that a complete residue system is simply a set containing precisely one representative of each residue class modulo n. The least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 include {1, 2, 3, 4}, {13, 14, 15, 16}, {−2, −1, 0, 1}, {−13, 4, 17, 18}, {−5, 0, 6, 21} and {27, 32, 37, 42}.

In the next post, we will explore the concept of congruence! Please contact me or comment below if you have any questions and have a great day!

If we replaced our 12 with a 0 in our clock,

the numbers on the clock would show us the way in which we would count in modulo 12.