Modular Arithmetic in Congruences

students, imagine a clock that never gets tired 🕒. After $12$ hours, it does not stop; it just starts over. That repeating pattern is the heart of modular arithmetic, one of the most important ideas in Number Theory. In this lesson, you will learn how to describe numbers that “wrap around,” how to use the symbols and vocabulary of congruences, and how modular arithmetic helps simplify calculations in real life, from clocks to calendars to computer systems 💻.

Objectives

By the end of this lesson, you should be able to:

explain the main ideas and terminology of modular arithmetic,
compute and reason with remainders,
use congruence notation such as $a \equiv b \pmod n$,
connect modular arithmetic to congruence classes and arithmetic modulo $n$,
solve simple problems using evidence and examples.

What is modular arithmetic?

Modular arithmetic is arithmetic with a fixed number called the modulus. Instead of letting numbers grow forever, we only care about their remainder after division by the modulus. This creates a cycle.

For example, when working modulo $5$:

$7$ and $2$ are treated the same because both leave remainder $2$ when divided by $5$,
$12$ and $2$ are also treated the same,
$-3$ and $2$ are treated the same, because $-3$ differs from $2$ by a multiple of $5$.

This idea is written using congruence notation:

$$a \equiv b \pmod n$$

which means that $a$ and $b$ have the same remainder when divided by $n$, or equivalently that $n$ divides $a-b$.

So if

$$17 \equiv 2 \pmod 5,$$

that is true because

$$17-2=15,$$

and $5$ divides $15$.

Remainders and the meaning of congruence

A common way to understand modular arithmetic is through division with remainder. For any integer $a$ and positive integer $n$, we can write

$$a=qn+r$$

where $q$ is an integer and $r$ is a remainder with

$$0 \le r < n.$$

The remainder $r$ is the representative of $a$ modulo $n$. For instance, dividing $29$ by $6$ gives

$$29=4\cdot 6+5,$$

so $29$ has remainder $5$ modulo $6$. That means

$$29 \equiv 5 \pmod 6.$$

Now compare $41$ and $5$ modulo $6$:

$$41=6\cdot 6+5,$$

$$41 \equiv 5 \pmod 6.$$

Because both numbers have the same remainder, we also have

$$41 \equiv 29 \pmod 6.$$

This is the main idea behind congruence classes: numbers are grouped according to the remainders they leave after division by $n$. These groups are called congruence classes or residue classes.

For modulo $6$, the possible classes are:

$$[0], [1], [2], [3], [4], [5].$$

Every integer belongs to exactly one of these classes.

Arithmetic modulo $n$

Modular arithmetic follows rules that are similar to ordinary arithmetic, but you reduce the result modulo $n$.

$$a \equiv b \pmod n$$

and

$$c \equiv d \pmod n,$$

then:

$$a+c \equiv b+d \pmod n,$$
$$a-c \equiv b-d \pmod n,$$
$$ac \equiv bd \pmod n.$$

These rules let you simplify calculations before doing large computations.

Addition example

Find

$$38+27 \pmod 7.$$

Instead of adding first, reduce each number:

$$38 \equiv 3 \pmod 7,$$

$$27 \equiv 6 \pmod 7.$$

Then

$$38+27 \equiv 3+6=9 \equiv 2 \pmod 7.$$

So the answer is

$$38+27 \equiv 2 \pmod 7.$$

Multiplication example

Find

$$14\cdot 19 \pmod 5.$$

Reduce first:

$$14 \equiv 4 \pmod 5,$$

$$19 \equiv 4 \pmod 5.$$

Then

$$14\cdot 19 \equiv 4\cdot 4=16 \equiv 1 \pmod 5.$$

$$14\cdot 19 \equiv 1 \pmod 5.$$

This kind of simplification is one reason modular arithmetic is so useful. It keeps arithmetic manageable, especially with very large numbers.

Negative numbers and why they work

Modular arithmetic also includes negative numbers. This can feel surprising at first, students, but it makes sense once you think in terms of differences by multiples of the modulus.

For example, modulo $7$:

$$-1 \equiv 6 \pmod 7,$$

because

$$-1-6=-7,$$

and $7$ divides $-7$.

Likewise,

$$-10 \equiv 4 \pmod 7,$$

because

$$-10+14=4,$$

and $14$ is a multiple of $7$.

You can always add or subtract a multiple of the modulus without changing the congruence class. That means:

$$a \equiv b \pmod n$$

if and only if

$$a+kn \equiv b \pmod n$$

for any integer $k$.

This is very helpful when simplifying expressions. For example,

$$103 \equiv 3 \pmod{10},$$

so in base-10 thinking, the last digit is what matters for the remainder modulo $10$.

Congruence classes and the number line loop

A congruence class is the set of all integers that are congruent to one another modulo $n$. If $a$ is one number, then its class modulo $n$ is the set

$$\{a+kn : k\in \mathbb{Z}\}.$$

For example, modulo $4$ the class of $1$ is

$$\{\dots,-7,-3,1,5,9,13,\dots\}.$$

All of these numbers differ by multiples of $4$.

You can think of this as a number line that loops around after every $n$ steps. On a clock, $14$ o’clock is the same position as $2$ o’clock because

$$14 \equiv 2 \pmod{12}.$$

That is the same idea as congruence classes: different numbers can represent the same position in the modular system.

Real-world applications

Modular arithmetic is not just a classroom idea. It appears in many real situations:

Clocks: Time uses arithmetic modulo $12$ or modulo $24$. For example, if it is $9$ o’clock now and you add $8$ hours, then

$$9+8=17 \equiv 5 \pmod{12},$$

so the time is $5$ o’clock.

Calendars: Days of the week repeat every $7$ days. If today is Tuesday and you count $10$ days ahead, then

$$10 \equiv 3 \pmod 7,$$

so the day will be three days after Tuesday.

Computer science: Computers use modular arithmetic in hashing, encryption, and checking for errors. Large calculations are often reduced modulo a number to keep values inside a fixed range.

These examples show that modular arithmetic helps describe repeating patterns and makes complicated situations easier to manage.

How modular arithmetic connects to congruences

Modular arithmetic and congruences are closely related. In fact, congruence is the language used to talk about modular arithmetic.

When you write

$$a \equiv b \pmod n,$$

you are saying that $a$ and $b$ are the same in the arithmetic system modulo $n$. So modular arithmetic is the process of calculating with remainders, while congruences are the statements that describe those relationships.

For example, the equation

$$23+18 \equiv 1 \pmod 5$$

means that after doing the addition, the result has remainder $1$ when divided by $5$. It also means you could reduce each part first:

$$23 \equiv 3 \pmod 5,$$

$$18 \equiv 3 \pmod 5,$$

$$23+18 \equiv 3+3=6 \equiv 1 \pmod 5.$$

That connection is central to the broader topic of congruences in Number Theory.

Example problem with full reasoning

Suppose students is asked to find

$$(47\cdot 18)+29 \pmod 9.$$

Step 1: reduce each number modulo $9$.

$$47 \equiv 2 \pmod 9,$$

$$18 \equiv 0 \pmod 9,$$

$$29 \equiv 2 \pmod 9.$$

Step 2: substitute the simpler values.

$$ (47\cdot 18)+29 \equiv (2\cdot 0)+2 \pmod 9.$$

Step 3: compute.

$$2\cdot 0+2=2.$$

$$ (47\cdot 18)+29 \equiv 2 \pmod 9.$$

Notice how much easier this is than multiplying $47$ and $18$ directly. Modular arithmetic turns a big problem into a smaller one.

Conclusion

Modular arithmetic is the arithmetic of remainders and repeating cycles. It uses the congruence statement

$$a \equiv b \pmod n$$

to show that two integers behave the same way modulo $n$. By working with congruence classes, you can simplify addition, subtraction, and multiplication, understand patterns like clocks and calendars, and connect these ideas to the larger study of congruences in Number Theory. students, once you understand modular arithmetic, you have a powerful tool for solving problems efficiently and spotting structure in numbers 🔍.

Study Notes

Modular arithmetic means doing arithmetic with a fixed modulus $n$.
The statement $a \equiv b \pmod n$ means $a$ and $b$ have the same remainder when divided by $n$.
It is also true exactly when $n$ divides $a-b$.
Every integer belongs to one congruence class modulo $n$.
The classes modulo $n$ are the possible remainders $0,1,2,\dots,n-1$.
You can add, subtract, and multiply congruences and keep the same modulus.
Negative numbers can be used in modular arithmetic.
Modular arithmetic helps with clocks, calendars, and computer calculations.
Congruences are the notation used to describe modular arithmetic relationships.