Modular arithmetic is a system of arithmetic for integers, which considers the remainder. In modular arithmetic, numbers “wrap around” upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder. 

When we divide two integers we will have an equation that looks like the following:
\(
\frac{A}{B}=Q \text { remainder } R
\)
\(A\) is the dividend
\(B\) is the divisor
\(Q\) is the quotient
\(R\) is the remainder
Sometimes, we are only interested in what the remainder is when we divide \(A\) by \(B\).

For these cases, there is an operator called the modulo operator (abbreviated as mod).
Using the same \(A, B, Q\), and \(R\) as above, we would have: \(A \bmod B=R\)
We would say this as \(A\) modulo \(B\) is equal to \(R\). Where \(B\) is referred to as the modulus.

For example:
\(
\begin{aligned}
\frac{13}{5} & =2 \text { remainder } \mathbf{3} \\
13 \bmod 5 & =\mathbf{3}
\end{aligned}
\)

The Clock

Every time you think about “time,” you use modular arithmetic because it deals with cycles of integers and remainders just like a clock.  For example, suppose your clock reads 9:00 (am/pm is not important). What will the clock show in 10 hours? Well, 9 + 10 = 19, but “19 o’clock” is not something that can be displayed on a clock with the numbers 1 to 12.

So, what do we do?
We subtract 12 from 19 and proudly say that the clock will show 7:00.
This is the idea behind modular arithmetic, which is sometimes referred to as “clock arithmetic” because 19 mod 12 = 7 mod 12, where 7 represents the remainder when 19 is divided by 12.

How To Do Modular Arithmetic

This means that modular arithmetic finds the remainder of a number upon division!

Example 1: What is 16 mod 12?

Solution: Well 16 divided by 12 equals 1 remainder of 4. So the answer is 4.

Example 2: What about 15 mod 2?

Solution: Here, 15 divided by 2 equals 7 remainder of 1, so the solution is 1.

Example 3: And if you have 18 mod 9?

Solution: So we know that 18 divided by 9 equals 2 remainder 0, so that means 18 mod 9 is equivalent to 0.

So, what have we learned?

Note: The trick for modular arithmetic isfocus on the remainder.

But just like we say with divisibility, the remainder must be positive.

Example 4: Evaluate \(-97 \bmod 11\).

Solution:
Well, \(-97\) divided by 11 equals \(-8\) remainder \(-9\).
But since this remainder is negative, we have to increase our quotient by 1 to say \(-97\) divided by 11 equals \(-9\) remainder 2, as \(11(-9)+2=-97\).
Therefore, \(-97\) mod 11 equals 2.

Congruence

For a positive integer \(n\), the integers \(a\) and \(b\) are congruent \(\bmod n\) if their remainders when divided by \(n\) are the same.

For example,
\(
52 \equiv 24 \quad(\bmod 7)
\)
As we can see above, 52 and 24 are congruent \((\bmod 7)\) because \(52(\bmod 7)=3\) and \(24(\bmod 7)=3\).
Note that \(=\) is different from \(\equiv\).

Another way of defining this is that integers \(a\) and \(b\) are congruent \(\bmod n\) if their difference \((a-b)\) is an integer multiple of \(n\), that is, if \(\frac{a-b}{n}\) has a remainder of 0.

\(
36=10 \quad(\bmod 13)
\)
36 and 10 are said to be congruent (mod 13 ) because their difference \(36-10=26\) is an integer multiple of \(n=13\), that is, \(26=2 \times 13\).

More Examples

• \(31 \equiv 1(\bmod 10)\) because \(31-1=30\) is a multiple of 10 .
• \(43 \equiv 22(\bmod 7)\) because \(\frac{43-22}{7}=\frac{21}{7}=3\), which is an integer.
• \(8 \not \equiv-8(\bmod 3)\) because \(8-(-8)=16\), which is not a multiple of 3 .
• \(91 \not \equiv 18(\bmod 6)\) because \(\frac{91-18}{6}=\frac{73}{6}\), which is not an integer.

Making Computation Easier

We don’t always need to perform tedious computations to discover solutions to interesting problems. If all we need to know about are remainders when integers are divided by \(n\), then we can work directly with those remainders in modulo \(n\). This can be more easily understood with a few examples.

Addition Rule

In general, when \(a, b, c\), and \(d\) are integers and \(m\) is a positive integer such that
\(
\begin{aligned}
& a \equiv c(\bmod m) \\
& b \equiv d(\bmod m)
\end{aligned}
\)
the following is always true:
\(
a+b \equiv c+d(\bmod m)
\)

Example 5: Find the units digit of the following sum: 

Solution:

Now let’s look back at this solution, using modular arithmetic from the start. Note that
\(
\begin{aligned}
& 2403 \equiv 3(\bmod 10) \\
& 791 \equiv 1(\bmod 10) \\
& 688 \equiv 8(\bmod 10) \\
& 4339 \equiv 9(\bmod 10)
\end{aligned}
\)
Because we only need the modulo 10 residue of the sum, we add just the residues of the summands:
\(
2403+791+688+4339 \equiv 3+1+8+9 \equiv 21 \equiv 1(\bmod 10),
\)
so the units digit of the sum is just 1 .

Subtraction rule

When \(a, b, c\), and \(d\) are integers and \(m\) is a positive integer such that
\(
\begin{aligned}
& a \equiv c(\bmod m) \\
& b \equiv d(\bmod m)
\end{aligned}
\)
the following is always true:
\(
a-b \equiv c-d(\bmod m)
\)

Example 6: \(\text { Find the remainder when the difference between } 60002 \text { and } 601 \text { is divided by } 6 \text {. }\)

Solution:

Note that \(60002=10000 \cdot 6+2\) and \(601=100 \cdot 6+1\). So, \(60002 \equiv 2(\bmod 6)\)
\(
601 \equiv 1(\bmod 6)
\)
Thus,
\(
60002-601 \equiv 2-1 \equiv 1(\bmod 6),
\)
so 1 is the remainder when the difference is divided by 6.

Multiplication rule

When \(a, b, c\), and \(d\) are integers and \(m\) is a positive integer such that
\(
\begin{aligned}
& a \equiv c(\bmod m) \\
& b \equiv d(\bmod m)
\end{aligned}
\)
The following is always true:
\(
a \cdot b \equiv c \cdot d(\bmod m) .
\)

Example 7: Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After making as many complete cases as possible, how many sodas will Jerry have leftover?

Solution:

First, we note that
\(44 \equiv 8(\bmod 12)\)
\(113 \equiv 5(\bmod 12)\)
Thus,
\(
44 \cdot 113 \equiv 8 \cdot 5 \equiv 40 \equiv 4(\bmod 12),
\)
meaning there are 4 sodas leftover. Yeah, that was much easier.

Exponentiation Rule

\(
\text { If } a \equiv b(\bmod N), \text { then } a^k \equiv b^k(\bmod N) \text { for any positive integer } k \text {. }
\)

Example 8: What is \(3^{16}(\bmod 4)?\)

Solution:

We observe that
\(
3^2 \equiv 9 \equiv 1 \quad(\bmod 4) .
\)
Then by the property of exponentiation, we have
\(
\begin{aligned}
3^{16} \quad(\bmod 4) & \equiv\left(3^2\right)^8 \quad(\bmod 4) \\
& \equiv(1)^8 \quad(\bmod 4) \\
& \equiv 1 \quad(\bmod 4) \cdot
\end{aligned}
\)

Example 9: \(\text { What is the last digit of } \left.\left(\ldots\left((7)^7\right)^7\right) \ldots\right)^7 \text { if there are } 1000  7 \mathrm{~s} \text { as exponents and only one } 7 \text { in the middle? }\)

Solution:

We can solve this problem using mods. This can also be stated as \(7^{7^{1000}}\). After that, we see that 7 is congruent to \(-1\) in mod 4, so we can use this fact to replace the \(7 \mathrm{~s}\) with \(-1 \mathrm{~s}\), because 7 has a pattern of repetitive period 4 for the units digit. \((-1)^{1000}\) is simply 1 , so therefore \(7^1=7\), which really is the last digit.

Example 10: \(\text { Can you find a number that is both a multiple of } 2 \text { but not a multiple of } 4 \text { and a perfect square? }
\)

Solution:

No, you cannot. Rewriting the question, we see that it asks us to find an integer \(n\) that satisfies \(4 n+2=x^2\).
Taking mod 4 on both sides, we find that \(x^2 \equiv 2\) ( \(\left.\bmod 4\right)\). Now, all we are missing is proof that no matter what \(x\) is, \(x^2\) will never be a multiple of 4 plus 2 , so we work with cases:
\(
\begin{aligned}
& x \equiv 0(\bmod 4) \Longrightarrow x^2 \equiv 0(\bmod 4) \\
& x \equiv 1(\bmod 4) \Longrightarrow x^2 \equiv 1(\bmod 4) \\
& x \equiv 2(\bmod 4) \Longrightarrow x^2 \equiv 4 \equiv 0(\bmod 4) \\
& x \equiv 3(\bmod 4) \Longrightarrow x^2 \equiv 9 \equiv 1(\bmod 4)
\end{aligned}
\)
This assures us that it is impossible to find such a number.

Example 11: Find the last three digits of \(2^{40}\).

Solution: 
We have
\(
\begin{array}{rlr}
2^{40} & =  \left(2^{10}\right)^4 \\
 &=  1024^4 \\
 &\equiv  24^4 \\
 &\equiv 576^2 & (\bmod 1000)
\end{array}
\)
We can write \(576^2\) as
\(
\begin{aligned}
& (500+76)(500+76)=250000+2 \times 500 \times 76+76 \times 76 \\
& =250000+76000+5776 \\
& \equiv \quad 0+5776 \\
& \equiv \quad 776(\bmod 1000) \\
\end{aligned}
\)
Since \(2^{40}\) leaves a remainder of 776 when divided by 1000 , its last three digits are 776.