Congruences

In modular arithmetic, congruences are the main way to write equations “modulo” some integer. In this chapter we focus on how congruences work, how to manipulate them, and some basic results that are constantly used in number theory and its applications.

Basic definition and notation

For integers $a,b$ and a positive integer $n$, we write
$$
a \equiv b \pmod n
$$
and read it as “$a$ is congruent to $b$ modulo $n$”.

This means that $a$ and $b$ leave the same remainder when divided by $n$, or equivalently, that their difference is divisible by $n$:
$$
a \equiv b \pmod n \quad \Longleftrightarrow \quad n \mid (a-b).
$$

Examples:

• $17 \equiv 5 \pmod{12}$, because $17-5=12$ is divisible by $12$.
• $25 \equiv 1 \pmod{4}$, because $25-1=24$ is divisible by $4$.
• $-3 \equiv 2 \pmod{5}$, because $-3-2=-5$ is divisible by $5$.

A useful way to think: $a \equiv b \pmod n$ says that $a$ and $b$ are in the same “remainder class” modulo $n$.

Basic properties of congruence

Congruence modulo a fixed $n$ behaves very much like equality. In particular, it satisfies:

• Reflexivity: $a \equiv a \pmod n$ for every integer $a$.
• Symmetry: If $a \equiv b \pmod n$, then $b \equiv a \pmod n$.
• Transitivity: If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a \equiv c \pmod n$.

These follow immediately from the divisibility condition $n\mid(a-b)$.

Because of these, you can treat a congruence like a kind of “equality modulo $n$” and do many of the same algebraic steps, as long as you stay consistent with the same modulus $n$.

Working with congruences

Addition and subtraction

If $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$.

Example:

• $17 \equiv 5 \pmod{12}$ and $11 \equiv -1 \pmod{12}$.
• Then $17+11 \equiv 5+(-1) \pmod{12}$, so $28 \equiv 4 \pmod{12}$, which is true since $28-4=24$ is divisible by $12$.

In practice, this means you can reduce numbers modulo $n$ at any stage to keep them small, then add or subtract.

Multiplication

If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then:
$$
ac \equiv bd \pmod n.
$$

In particular, if $a \equiv b \pmod n$, then for any integer $k$,
$$
ka \equiv kb \pmod n.
$$

Example:

• $17 \equiv 5 \pmod{12}$ and $11 \equiv -1 \pmod{12}$.
• Then $17\cdot 11 \equiv 5\cdot(-1) \pmod{12}$, so $187 \equiv -5 \pmod{12}$.
• Reducing further, $-5 \equiv 7 \pmod{12}$ (since $-5+12=7$), and indeed $187-7=180$ is divisible by $12$.

Again, this lets you replace large numbers with smaller congruent ones before multiplying, which is especially useful for big powers.

Powers (repeated multiplication)

If $a \equiv b \pmod n$, then for any positive integer $k$,
$$
a^k \equiv b^k \pmod n.
$$

This follows by repeated use of the multiplication rule.

Example:

• $7 \equiv -1 \pmod 8$.
• Then $7^4 \equiv (-1)^4 = 1 \pmod 8$.
• Indeed, $7^2=49 \equiv 1 \pmod 8$, and $7^4 = (7^2)^2 \equiv 1^2 = 1 \pmod 8$.

This is extremely useful for simplifying large exponent computations modulo $n$.

Cancellation and its limitations

With ordinary equalities, if $ac=bc$ and $c\neq 0$, you can cancel $c$ to conclude $a=b$. In congruences, there is a similar idea, but it comes with an important condition.

Suppose
$$
ac \equiv bc \pmod n.
$$
This means $n \mid c(a-b)$.

• If $\gcd(c,n) = 1$ (that is, $c$ and $n$ are coprime), then you can “cancel $c$”:
  $$
  ac \equiv bc \pmod n \quad \Longrightarrow \quad a \equiv b \pmod n.
  $$
• If $\gcd(c,n) \neq 1$, then cancellation may fail.

Example where cancellation succeeds:

• Work modulo $7$: $3\cdot 5 \equiv 4\cdot 5 \pmod 7$?
• $15 \equiv 20 \pmod 7$ since $15\equiv 1$ and $20\equiv 6$, and $1 \not\equiv 6 \pmod 7$. Actually the congruence does not hold, so this is not an example of a true congruence to start with. Instead, suppose
  $$
  3x \equiv 10 \pmod 7.
  $$
  Since \equiv 3 \pmod 7$ and $\gcd(3,7)=1$, we can (in a sense) divide both sides by $ to solve for $x$. This is tied to multiplicative inverses, discussed below.

Example where cancellation fails:

• Consider $2a \equiv 2b \pmod 4$.
• This congruence is always true: $2(a-b)$ is always even, but is it always divisible by $4$? Not always. Let’s look more concretely:
• $2\cdot 1 = 2$ and $2\cdot 3 = 6$.
• $2 \equiv 6 \pmod 4$ (both give remainder $2$).
• So $2\cdot 1 \equiv 2\cdot 3 \pmod 4$, but $1 \not\equiv 3 \pmod 4$.
• Here $\gcd(2,4)=2\neq 1$, so cancellation is not valid.

The key lesson: you may only “cancel” a factor $c$ in a congruence modulo $n$ if $c$ and $n$ are coprime.

Solving linear congruences

A linear congruence is an expression of the form
$$
ax \equiv b \pmod n,
$$
where $a,b,n$ are known integers and $x$ is unknown (an integer to be found).

Existence of solutions

Let $d = \gcd(a,n)$. Then:

• If $d \nmid b$, there is no solution.
• If $d \mid b$, there are exactly $d$ distinct solutions modulo $n$.

This is a central fact about linear congruences.

Intuitively, dividing everything by $d$ turns the congruence into one where the coefficient of $x$ is coprime with the new modulus.

Reducing to a simpler congruence

Suppose $d=\gcd(a,n)$ and $d\mid b$. Write
$$
a = d a', \quad b = d b', \quad n = d n'.
$$
Then
$$
ax \equiv b \pmod n
\quad\Longleftrightarrow\quad
d a' x \equiv d b' \pmod{d n'}.
$$

You can divide the whole congruence by $d$:
$$
a' x \equiv b' \pmod{n'}.
$$

Now $\gcd(a',n') = 1$, so $a'$ has a multiplicative inverse modulo $n'$.

Once you find one solution modulo $n'$, you can lift it to obtain $d$ distinct solutions modulo $n$.

Using multiplicative inverses

If $\gcd(a,n)=1$, then $a$ has a multiplicative inverse modulo $n$. Call it $a^{-1}$; by definition it satisfies
$$
a a^{-1} \equiv 1 \pmod n.
$$

Then the congruence
$$
ax \equiv b \pmod n
$$
can be solved by multiplying both sides by $a^{-1}$:
$$
x \equiv a^{-1} b \pmod n.
$$

The main work is to find $a^{-1} \pmod n$, for example via the extended Euclidean algorithm (the details of that algorithm belong elsewhere in the course).

Example:
Solve
$$
3x \equiv 4 \pmod 7.
$$
Here $\gcd(3,7)=1$, so $3$ has an inverse modulo $7$.

Find $3^{-1} \pmod 7$:

• Check small numbers: $3\cdot 1=3$, $3\cdot 2=6$, $3\cdot 3=9\equiv2$, $3\cdot 4=12\equiv5$, $3\cdot 5=15\equiv1 \pmod7$.
• So $3\cdot 5 \equiv 1 \pmod7$, hence $3^{-1} \equiv 5 \pmod7$.

Multiply both sides of $3x \equiv 4 \pmod7$ by $5$:
$$
x \equiv 5\cdot 4 \equiv 20 \equiv 6 \pmod7.
$$

So all integer solutions are of the form $x = 6 + 7k$ for integers $k$.

Example with multiple solutions:
Solve
$$
4x \equiv 8 \pmod{12}.
$$
Compute $d=\gcd(4,12)=4$. Since $4\mid 8$, solutions exist.

Divide everything by $4$:
$$
x \equiv 2 \pmod 3.
$$

The solutions to $x \equiv 2 \pmod 3$ are $x=2+3k$.

To get solutions modulo $12$, list those in one full cycle of length $12$:

• $x=2,5,8,11$.

Check:

• $4\cdot 2 = 8 \equiv 8 \pmod{12}$,
• $4\cdot 5 = 20 \equiv 8 \pmod{12}$,
• $4\cdot 8 = 32 \equiv 8 \pmod{12}$,
• $4\cdot 11 = 44 \equiv 8 \pmod{12}$.

There are $d=4$ distinct solutions modulo $12$, as the general theory predicts.

Systems of congruences and the idea behind Chinese remainders

Sometimes you want an integer $x$ that satisfies several congruences at once, such as
$$
\begin{cases}
x \equiv 2 \pmod 3,\\
x \equiv 1 \pmod 4.
\end{cases}
$$

This is a system of congruences. When the moduli are coprime, such systems behave especially well: there is a unique solution modulo the product of the moduli. This is the content of the Chinese Remainder Theorem, which is treated in more depth elsewhere.

For now, the important congruence-related idea is that:

• Each congruence describes a set of integers (a residue class).
• A system corresponds to the intersection of such sets.
• When moduli are coprime, these intersections follow a regular pattern and always produce a unique congruence class modulo the product modulus.

You can often solve small systems by trial or simple reasoning, using your knowledge of congruences.

Using congruences in practice

Congruences are widely used for:

• Checking divisibility: For example, if $a \equiv 0 \pmod n$, then $n$ divides $a$.
• Simplifying computations: Replace large numbers with smaller congruent ones to make arithmetic easier.
• Working with remainders: Problems about “what remainder do you get when dividing by $n$?” are naturally solved by congruences.
• Structure in number theory: Many important theorems (like Fermat’s little theorem) and cryptographic constructions are most naturally phrased using congruences.

In many later topics, especially in number theory and cryptography, expressions of the form
$$
a \equiv b \pmod n
$$
are the basic “equations” you solve and manipulate. The rules and examples in this chapter form the core toolkit for that work.