8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

Section 8.2 repeatedly used remainders to shrink a gcd problem. Modular arithmetic changes the viewpoint: instead of treating a remainder as a temporary by-product, we group all integers that have the same remainder.

This produces a finite arithmetic system from infinitely many integers.

Congruence means equal remainder class

Fix a positive integer $n$ , called the modulus. For integers $a$ and $b$ , we write

a\equiv b\pmod n

and say “ $a$ is congruent to $b$ modulo $n$ ” if

n\mid(a-b).

Equivalently, $a$ and $b$ leave the same remainder when divided by $n$ .

Example modulo $5$

Because

17-2=15=5\cdot3,

we have

17\equiv2\pmod5.

Both numbers have remainder $2$ after division by $5$ .

Negative integers also belong to remainder classes. Since

-3-2=-5,

we have

-3\equiv2\pmod5.

The symbol $=$ is still ordinary equality. Congruence is a different relation: $17\ne2$ , although $17\equiv2\pmod5$ .

Residues and residue classes

Every integer is congruent modulo $n$ to exactly one member of

\{0,1,2,\ldots,n-1\}.

These standard representatives are called residues modulo $n$ .

For modulus $5$ , the residue class of $2$ contains

\ldots,-8,-3,2,7,12,17,\ldots

because neighboring entries differ by $5$ .

Congruence is an equivalence relation from Chapter 4:

$a\equiv a\pmod n$ ;

if $a\equiv b\pmod n$ , then $b\equiv a\pmod n$ ;

if $a\equiv b\pmod n$ and $b\equiv c\pmod n$ , then $a\equiv c\pmod n$ .

Therefore congruence partitions $\mathbb Z$ into $n$ disjoint residue classes.

Addition and multiplication respect congruence

Suppose

a\equiv b\pmod n \qquad\text{and}\qquad c\equiv d\pmod n.

Then

a+c\equiv b+d\pmod n

and

ac\equiv bd\pmod n.

For addition,

(a+c)-(b+d)=(a-b)+(c-d),

which is divisible by $n$ .

For multiplication, rewrite the difference as

ac-bd=c(a-b)+b(c-d).

Both terms are divisible by $n$ , so their sum is divisible by $n$ .

These rules let us reduce before or after an operation.

Example: reducing a large product

Compute $38\cdot47\pmod7$ .

First reduce each factor:

38\equiv3\pmod7, \qquad 47\equiv5\pmod7.

Then

38\cdot47\equiv3\cdot5=15\equiv1\pmod7.

No large multiplication was necessary.

Powers can be reduced repeatedly

Congruence multiplication can be applied again and again. For example,

7\equiv2\pmod5,

7^4\equiv2^4=16\equiv1\pmod5.

For very large exponents, repeated squaring reduces both the base and each intermediate square. Section 8.4 will use this technique for RSA.

Loading interactive lab...

Rotate integers around a residue clock, then compose addition and multiplication moves on two synchronized rings. Dragging through negative and oversized values preserves their class trail, while a collision detector explains congruence through both equal remainders and divisible differences.

Loading concept check...

Loading practice...

A modular inverse undoes multiplication

For ordinary nonzero rational numbers, multiplication by $a$ is undone by multiplying by $1/a$ . Inside modular arithmetic, division is possible only when a suitable residue exists.

An integer $x$ is a multiplicative inverse of $a$ modulo $n$ if

ax\equiv1\pmod n.

We may write

x\equiv a^{-1}\pmod n.

The notation $a^{-1}$ here means a modular inverse, not the real-number fraction $1/a$ .

When does an inverse exist?

The inverse exists exactly when

\gcd(a,n)=1.

Integers with gcd $1$ are called coprime or relatively prime.

If $\gcd(a,n)=1$ , Bézout's identity provides integers $x,y$ such that

ax+ny=1.

Reducing modulo $n$ removes the multiple $ny$ and gives

ax\equiv1\pmod n.

So the Bézout coefficient of $a$ is an inverse.

Conversely, if $ax\equiv1\pmod n$ , then $ax-1$ is divisible by $n$ . Thus

ax+ny=1

for some integer $y$ , forcing every common divisor of $a,n$ to divide $1$ . Hence their gcd is $1$ .

Finding an inverse with the extended Euclidean algorithm

Find the inverse of $7$ modulo $26$ .

Euclid's algorithm gives

\begin{aligned} 26&=3\cdot7+5,\\ 7&=1\cdot5+2,\\ 5&=2\cdot2+1. \end{aligned}

Back-substitute:

\begin{aligned} 1 &=5-2\cdot2\\ &=5-2(7-5)\\ &=3\cdot5-2\cdot7\\ &=3(26-3\cdot7)-2\cdot7\\ &=3\cdot26-11\cdot7. \end{aligned}

Therefore

-11\cdot7\equiv1\pmod{26}.

The standard nonnegative representative of $-11$ is $15$ , so

7^{-1}\equiv15\pmod{26}.

Check:

7\cdot15=105=4\cdot26+1.

Solving a linear congruence

To solve

7x\equiv5\pmod{26},

multiply both sides by the inverse $15$ :

x\equiv15\cdot5=75\equiv23\pmod{26}.

This resembles ordinary division, but the inverse exists because $7$ and $26$ are coprime.

More generally, $ax\equiv b\pmod n$ has a solution exactly when

\gcd(a,n)\mid b.

This is the linear-combination criterion from Section 8.2 in modular form.

Combining remainder conditions

Suppose a number must satisfy several clocks at once:

x\equiv2\pmod3,

x\equiv3\pmod5,

and

x\equiv2\pmod7.

The moduli $3,5,7$ are pairwise coprime: every two distinct moduli have gcd $1$ .

The Chinese Remainder Theorem (CRT) states that a system

x\equiv a_i\pmod{n_i} \qquad(1\le i\le k)

with pairwise-coprime positive moduli has exactly one solution modulo

N=\prod_{i=1}^{k}n_i.

“Exactly one modulo $N$ ” means that all integer solutions belong to one residue class $x_0+Nt$ .

Constructing the CRT solution

For each equation, define

N_i=\frac{N}{n_i}.

Because the moduli are pairwise coprime,

\gcd(N_i,n_i)=1,

so $N_i$ has an inverse $y_i$ modulo $n_i$ :

N_i y_i\equiv1\pmod{n_i}.

Then

x\equiv\sum_{i=1}^{k}a_iN_i y_i\pmod N.

Each product $N_i y_i$ behaves like a selector: it is $1$ on clock $n_i$ and $0$ on every other clock because it contains those other moduli as factors.

Worked CRT example

Here

N=3\cdot5\cdot7=105.

For modulus $3$ , $N_1=35$ and $35\equiv2\pmod3$ . Its inverse is $2$ , because $2\cdot2\equiv1\pmod3$ .

For modulus $5$ , $N_2=21\equiv1\pmod5$ , so its inverse is $1$ .

For modulus $7$ , $N_3=15\equiv1\pmod7$ , so its inverse is $1$ .

Therefore

\begin{aligned} x &\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\\ &=233\\ &\equiv23\pmod{105}. \end{aligned}

Check all three clocks:

23\bmod3=2, \qquad 23\bmod5=3, \qquad 23\bmod7=2.

Loading interactive lab...

Set residue targets on two or three independent cyclic beacons, then sweep one shared integer timeline until their signals align. Switch between search mode and constructive selector mode to see both why the solution repeats every product of coprime moduli and how CRT builds it directly.

Loading concept check...

Loading practice...

Note

Congruence groups integers by remainder. Modular division requires a coprime inverse, and CRT combines pairwise-coprime remainder conditions into one unique class modulo the product.

Section bridge

We can now multiply and exponentiate in a finite residue system, find inverses through Bézout coefficients, and combine congruences through CRT. Section 8.4 assembles exactly these tools into a small RSA public-key system.

8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

This produces a finite arithmetic system from infinitely many integers.

Congruence means equal remainder class

Fix a positive integer $n$ , called the modulus. For integers $a$ and $b$ , we write

a\equiv b\pmod n

and say “ $a$ is congruent to $b$ modulo $n$ ” if

n\mid(a-b).

Equivalently, $a$ and $b$ leave the same remainder when divided by $n$ .

Example modulo $5$

Because

17-2=15=5\cdot3,

we have

17\equiv2\pmod5.

Both numbers have remainder $2$ after division by $5$ .

Negative integers also belong to remainder classes. Since

-3-2=-5,

we have

-3\equiv2\pmod5.

The symbol $=$ is still ordinary equality. Congruence is a different relation: $17\ne2$ , although $17\equiv2\pmod5$ .

Residues and residue classes

Every integer is congruent modulo $n$ to exactly one member of

\{0,1,2,\ldots,n-1\}.

These standard representatives are called residues modulo $n$ .

For modulus $5$ , the residue class of $2$ contains

\ldots,-8,-3,2,7,12,17,\ldots

because neighboring entries differ by $5$ .

Congruence is an equivalence relation from Chapter 4:

$a\equiv a\pmod n$ ;

if $a\equiv b\pmod n$ , then $b\equiv a\pmod n$ ;

if $a\equiv b\pmod n$ and $b\equiv c\pmod n$ , then $a\equiv c\pmod n$ .

Therefore congruence partitions $\mathbb Z$ into $n$ disjoint residue classes.

Addition and multiplication respect congruence

Suppose

a\equiv b\pmod n \qquad\text{and}\qquad c\equiv d\pmod n.

Then

a+c\equiv b+d\pmod n

and

ac\equiv bd\pmod n.

For addition,

(a+c)-(b+d)=(a-b)+(c-d),

which is divisible by $n$ .

For multiplication, rewrite the difference as

ac-bd=c(a-b)+b(c-d).

Both terms are divisible by $n$ , so their sum is divisible by $n$ .

These rules let us reduce before or after an operation.

Example: reducing a large product

Compute $38\cdot47\pmod7$ .

First reduce each factor:

38\equiv3\pmod7, \qquad 47\equiv5\pmod7.

Then

38\cdot47\equiv3\cdot5=15\equiv1\pmod7.

No large multiplication was necessary.

Powers can be reduced repeatedly

Congruence multiplication can be applied again and again. For example,

7\equiv2\pmod5,

7^4\equiv2^4=16\equiv1\pmod5.

For very large exponents, repeated squaring reduces both the base and each intermediate square. Section 8.4 will use this technique for RSA.

Loading interactive lab...

Loading concept check...

Loading practice...

A modular inverse undoes multiplication

For ordinary nonzero rational numbers, multiplication by $a$ is undone by multiplying by $1/a$ . Inside modular arithmetic, division is possible only when a suitable residue exists.

An integer $x$ is a multiplicative inverse of $a$ modulo $n$ if

ax\equiv1\pmod n.

We may write

x\equiv a^{-1}\pmod n.

The notation $a^{-1}$ here means a modular inverse, not the real-number fraction $1/a$ .

When does an inverse exist?

The inverse exists exactly when

\gcd(a,n)=1.

Integers with gcd $1$ are called coprime or relatively prime.

If $\gcd(a,n)=1$ , Bézout's identity provides integers $x,y$ such that

ax+ny=1.

Reducing modulo $n$ removes the multiple $ny$ and gives

ax\equiv1\pmod n.

So the Bézout coefficient of $a$ is an inverse.

Conversely, if $ax\equiv1\pmod n$ , then $ax-1$ is divisible by $n$ . Thus

ax+ny=1

for some integer $y$ , forcing every common divisor of $a,n$ to divide $1$ . Hence their gcd is $1$ .

Finding an inverse with the extended Euclidean algorithm

Find the inverse of $7$ modulo $26$ .

Euclid's algorithm gives

\begin{aligned} 26&=3\cdot7+5,\\ 7&=1\cdot5+2,\\ 5&=2\cdot2+1. \end{aligned}

Back-substitute:

\begin{aligned} 1 &=5-2\cdot2\\ &=5-2(7-5)\\ &=3\cdot5-2\cdot7\\ &=3(26-3\cdot7)-2\cdot7\\ &=3\cdot26-11\cdot7. \end{aligned}

Therefore

-11\cdot7\equiv1\pmod{26}.

The standard nonnegative representative of $-11$ is $15$ , so

7^{-1}\equiv15\pmod{26}.

Check:

7\cdot15=105=4\cdot26+1.

Solving a linear congruence

To solve

7x\equiv5\pmod{26},

multiply both sides by the inverse $15$ :

x\equiv15\cdot5=75\equiv23\pmod{26}.

This resembles ordinary division, but the inverse exists because $7$ and $26$ are coprime.

More generally, $ax\equiv b\pmod n$ has a solution exactly when

\gcd(a,n)\mid b.

This is the linear-combination criterion from Section 8.2 in modular form.

Combining remainder conditions

Suppose a number must satisfy several clocks at once:

x\equiv2\pmod3,

x\equiv3\pmod5,

and

x\equiv2\pmod7.

The moduli $3,5,7$ are pairwise coprime: every two distinct moduli have gcd $1$ .

The Chinese Remainder Theorem (CRT) states that a system

x\equiv a_i\pmod{n_i} \qquad(1\le i\le k)

with pairwise-coprime positive moduli has exactly one solution modulo

N=\prod_{i=1}^{k}n_i.

“Exactly one modulo $N$ ” means that all integer solutions belong to one residue class $x_0+Nt$ .

Constructing the CRT solution

For each equation, define

N_i=\frac{N}{n_i}.

Because the moduli are pairwise coprime,

\gcd(N_i,n_i)=1,

so $N_i$ has an inverse $y_i$ modulo $n_i$ :

N_i y_i\equiv1\pmod{n_i}.

Then

x\equiv\sum_{i=1}^{k}a_iN_i y_i\pmod N.

Each product $N_i y_i$ behaves like a selector: it is $1$ on clock $n_i$ and $0$ on every other clock because it contains those other moduli as factors.

Worked CRT example

Here

N=3\cdot5\cdot7=105.

For modulus $3$ , $N_1=35$ and $35\equiv2\pmod3$ . Its inverse is $2$ , because $2\cdot2\equiv1\pmod3$ .

For modulus $5$ , $N_2=21\equiv1\pmod5$ , so its inverse is $1$ .

For modulus $7$ , $N_3=15\equiv1\pmod7$ , so its inverse is $1$ .

Therefore

\begin{aligned} x &\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\\ &=233\\ &\equiv23\pmod{105}. \end{aligned}

Check all three clocks:

23\bmod3=2, \qquad 23\bmod5=3, \qquad 23\bmod7=2.

Loading interactive lab...

Loading concept check...

Loading practice...

Note

Congruence groups integers by remainder. Modular division requires a coprime inverse, and CRT combines pairwise-coprime remainder conditions into one unique class modulo the product.

8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

Congruence means equal remainder class

Example modulo 555

Residues and residue classes

Addition and multiplication respect congruence

Example: reducing a large product

Powers can be reduced repeatedly

A modular inverse undoes multiplication

When does an inverse exist?

Finding an inverse with the extended Euclidean algorithm

Solving a linear congruence

Combining remainder conditions

Constructing the CRT solution

Worked CRT example

Section bridge

8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

8.3 Modular Arithmetic, Inverses, and the Chinese Remainder Theorem

Congruence means equal remainder class

Example modulo 555

Residues and residue classes

Addition and multiplication respect congruence

Example: reducing a large product

Powers can be reduced repeatedly

A modular inverse undoes multiplication

When does an inverse exist?

Finding an inverse with the extended Euclidean algorithm

Solving a linear congruence

Combining remainder conditions

Constructing the CRT solution

Worked CRT example

Section bridge

Example modulo $5$

Example modulo $5$