Modular Arithmetic

Introduction

Throughout this lesson, all variables are integers. Modular arithmetic is a number system based on integers with an additional component called a modulus. Usually when we do arithmetic, integers can get infinitely big. However in modular arithmetic, every integer is reduced to its remainder upon division by the modulus.

In general, any integer $a$ can be written as $n(q)+r$ for some quotient $q$ and remainder $r$ . Then $a \equiv r$ mod $n$ . Then we say $a$ is congruent or equivalent to $r$ modulo $n$ . Often "modulo" is shortened to "mod".

Example: $15$ is the same as $3$ mod $12$ because $15$ leaves a remainder of $3$ when divided by $12$ . So $15=12(1)+3$ , which means $15 \equiv 3$ mod $12$ .

Consider the general case where we are working mod $n$ , then we can simplify any integer $a$ mod $n$ to its remainder upon dividing by $n$ , which we call its least positive residue.

As with the previous example, $3$ is the least positive residue for $3,15,27,$ and so on.

Visualizing Modular Arithmetic

Because of the circular nature of residues, modular arithmetic operations can be thought of as mappings performed on points around a circle, where each least positive residue corresponds with a point. Notice that if the modulus is $12$ , this looks just like the face of a clock.

Modulus:

Properties

Modular arithmetic is an integer system, so it inherits properties from the integers like addition and multiplication. Modular arithmetic also inherits 0 as the additive identity and 1 as the multiplicative identity. In other words, $a+0 \equiv a$ mod $n$ and $a\cdot 1 \equiv a$ mod $n$ for any $a,n \in \Z$ . We will see that additive inverses are always defined, but multiplicative inverses are not defined in general.

Addition

Similar to a clock, we can perform operations like addition and multiplication. We will consider each operation as a map that transforms the remainders to their result when the operation is applied. First, we look at an example of addition.

Example: $3$ hours after $10$ o'clock is the same as $10$ hours after $3$ o'clock, which is $1$ o'clock. In other words, $10+3 \equiv 3+10 \equiv 1$ mod $12$ .

Adjust the numbers for modulus and additive mapping to see more examples of addition in modular arithmetic.

	Modulus:
	Additive mapping:

Notice that each number maps to exactly one other number and every number is mapped to by exactly one other number. This shows that the inverse of addition is defined for every residue, so the additive inverse, subtraction, always exists. This means that for any integer $a$ and modulus $n$ , we can always write the additive inverse of $a$ as $-a$ , with $a-a \equiv 0$ mod $n$ .

Multiplication

Another operation of modular arithmetic is multiplication.

Example: $4$ repeated $3$ -hour time periods, the clock will read the same. This is because $3 \cdot 4 \equiv 0$ mod $12$ , which is represented on the circle below.

In this visual, arrows of the same color belong to a cycle that starts with some number $a$ that is consecutively by another number $b$ until the pattern eventually repeats with $a$ again. Just like before, adjust the numbers for modulus and multiplicative mapping to see more examples of multiplication in modular arithmetic.

	Modulus:
	Multiplicative mapping:

In normal arithmetic, the multiplicative inverse of a number is its reciprocal. To avoid using division, we instead write the multiplicative inverse of $a$ as $a^{-1}$ . The inverse of $a$ mod $n$ is denoted $a^{-1}$ . However, some numbers get mapped to another number more than once, so you can't "undo" that multiplicative mapping.

Example: $4 \cdot 2 \equiv 4 \cdot 5 \equiv 4 \cdot 1 \equiv 8$ mod $12$ . In this sense, we can't "undo" multiplication by $4$ mod $12$ , so the multiplicative inverse of $4$ isn't always defined.

In fact, the multiplicative inverse of some integer $a$ modulo $n$ is only defined when $gcd(a,n)=1$ .