Introduction to Modular Arithmetic

In this lecture, we explore congruences and modular arithmetic!

Congruences in the Integers

Examples:

• $17 \equiv 5 \pmod{12}$ because $12 \mid (17 - 5)$
• $-3 \equiv 7 \pmod{10}$ because $10 \mid (-3 - 7) = -10$
• $100 \equiv 0 \pmod{25}$ because $25 \mid 100$

Basic Properties of Congruences

Congruences behave much like equalities:

1. Reflexivity: $a \equiv a \pmod{n}$ for all integers $a$
2. Symmetry: If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$
3. Transitivity: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$
4. Addition: If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$
5. Multiplication: If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$

Exercise: Prove the five properties listed above using the definition of congruence.

Warning about Cancellation: Unlike ordinary equations, the cancellation property does not always hold for congruences. That is, from $ab \equiv ac \pmod{n}$, we cannot always conclude that $b \equiv c \pmod{n}$.

Exercise: Find integers $a, b, c, n$ such that $ab \equiv ac \pmod{n}$ but $b \not\equiv c \pmod{n}$.

Congruence Equations

A congruence equation is an equation involving congruences that we want to solve. These equations can be linear or nonlinear, and can involve one or multiple variables.

Example 1: Solve $5x + 11 \equiv 2 \pmod{12}$.

We can simplify: $5x \equiv 2 - 11 \equiv -9 \equiv 3 \pmod{12}$.

Now we check values of $x$ from $0$ to $11$:

• $x = 0$: $5 \cdot 0 = 0 \not\equiv 3 \pmod{12}$
• $x = 1$: $5 \cdot 1 = 5 \not\equiv 3 \pmod{12}$
• $x = 2$: $5 \cdot 2 = 10 \not\equiv 3 \pmod{12}$
• $x = 3$: $5 \cdot 3 = 15 \equiv 3 \pmod{12}$ ✓

So $x \equiv 3 \pmod{12}$ is a solution. This means that $x = \ldots, -9, 3, 15, \ldots$ are all solutions. If we continue on this way, we see that these are the only solutions.

Example 2: Solve $3^n \equiv 1 \pmod{17}$ for $n \geq 1$.

We compute powers of $3$ modulo $17$:

• $3^1 \equiv 3 \pmod{17}$
• $3^2 \equiv 9 \pmod{17}$
• $3^3 \equiv 27 \equiv 10 \pmod{17}$
• $3^4 \equiv 30 \equiv 13 \pmod{17}$
• ...continuing this process...
• $3^{16} \equiv 1 \pmod{17}$

So the smallest positive solution is $n = 16$. In this case, $3^{16\cdot 2} \equiv (3^{16})^2 \equiv 1^2 \equiv 1 \pmod{16}$ so $16\cdot 2$ is also a solution. In fact, $n = 16\cdot k$ for any $k \in \mathbb{Z}_{\geq 0}$ is a solution! Moreover, these are all of the solutions (why?).

Exercise: For which integers $k \geq 1$ does $2^k \equiv 3 \pmod{11}$?

Example 3: Find all solutions to $x^2 + y^2 \equiv 3 \pmod{4}$ where $0 \leq x, y < 4$.

We check all possible pairs:

• Possible values of $x^2 \pmod{4}$: $0^2 \equiv 0$, $1^2 \equiv 1$, $2^2 \equiv 0$, $3^2 \equiv 1$
• So $x^2 \pmod{4} \in \{0, 1\}$ and $y^2 \pmod{4} \in \{0, 1\}$
• Possible sums: $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, $1 + 1 = 2$

Since we can only get $0, 1,$ or $2$ as the sum of two squares modulo $4$, there are no solutions to $x^2 + y^2 \equiv 3 \pmod{4}$.

Using SageMath with congruences

Here is a bit of code to get you going with how to work with congruences in Sage math.

Exercise: Try for yourself! Find all solutions to the following congruence equation $8x^2 \equiv 7 \pmod{19}$.

Modular Arithmetic

We saw in the previous section that solving congruence equations is great, because it reduces to a finite check. When we only care about working with congruences modulo $n$ it's pretty convenient to introduce a complete arithmetic system modulo $n$! For this we define the set of Integers modulo $n$:

$$\mathbb{Z}_n := \{0, 1, 2, \ldots, n-1\}$$

In $\mathbb{Z}_n$, all arithmetic operations (addition, subtraction, multiplication) are performed modulo $n$. This means after any operation, we take the remainder when dividing by $n$.

Example: In $\mathbb{Z}_7$:

• $5 + 4 = 9 \equiv 2 \pmod{7}$, so $5 + 4 = 2$ in $\mathbb{Z}_7$
• $6 \cdot 3 = 18 \equiv 4 \pmod{7}$, so $6 \cdot 3 = 4$ in $\mathbb{Z}_7$
• $2 - 5 = -3 \equiv 4 \pmod{7}$, so $2 - 5 = 4$ in $\mathbb{Z}_7$

Notice that we can always talk about numbers like $100$ in $\mathbb{Z}_{11}$, we mean $1 + \cdots + 1$ (with one hundred $1$'s appearing), which would be $100 = 9*11 + 1 = 1$ in $\mathbb{Z}{11}$.

Computing Powers Using Modular Arithmetic

When computing large powers like $2^{100} \pmod{7}$, we can use properties of modular arithmetic to simplify:

Since $2^3 = 8 \equiv 1 \pmod{7}$, we have: $$2^{100} = 2^{3 \cdot 33 + 1} = (2^3)^{33} \cdot 2 \equiv 1^{33} \cdot 2 \equiv 2 \pmod{7}$$

This is much easier than computing $2^{100}$ directly!

Practice Problems

Here are some problems to help you practice working with congruences and modular arithmetic.

Problem 1

Compute $4^{11} - 90 \cdot 17 + 5^3 \pmod{13}$.

Problem 2

Solve $7x = 5$ in $\mathbb{Z}_{18}$.

Problem 3

Find all solutions $(x, y)$ to $y^2 + x^3 \equiv 1 \pmod{5}$ where $x,y \in \mathbb{Z}_{5}$.

---

Random Practice Problems

Use the cells below to generate random practice problems. Run the first cell to generate a problem, then run the second cell to see the answer.

Random Problem Type 1: Arithmetic with modular operations

Random Problem Type 2: Solve a linear congruence equation

---

Coding Challenge

Write a function find_order(a, n) that finds the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{n}$, assuming such a $k$ exists. This value $k$ is called the order of $a$ modulo $n$.

Requirements:

• The function should take two parameters: a (the base) and n (the modulus)
• Return the smallest positive integer $k$ where $a^k \equiv 1 \pmod{n}$
• If no such $k$ exists within a reasonable range (say, $k \leq n$), return None

Test your function:

• find_order(3, 7) should return 6
• find_order(2, 7) should return 3
• find_order(5, 12) should return 2