FP2 5.3 - Modular arithmetic and congruences

You already know

The division theorem writes an integer as $a=nq+r$, where $n>0$ and $0\leq r<n$. Two integers have the same remainder precisely when their difference is a multiple of $n$. Euclid finds $\gcd(a,n)$, and Bezout's identity expresses it as an integer combination.

Congruence and residues

For integers $a,b$ and a positive integer modulus $n$,

Equivalently, $a,b$ have the same remainder on division by $n$.

The least nonnegative residue is the representative $r$ with $0\leq r<n$. The least positive residue is the representative $s$ with $1\leq s\leq n$. These agree unless the remainder is zero; the zero class has least positive representative $n$.

Every integer congruent to $r$ has the form $r+kn$, where $k\in\mathbb Z$.

Not in the formula booklet: learn it.

Worked example 1: a negative input, a positive remainder

Question. Find the least nonnegative and least positive residues of $-38$ modulo $9$. Write the congruence and describe all integers in its class.

Plan. Use division with a nonnegative remainder, then check whether that remainder is zero.

Why this step? Reducing a negative integer requires the remainder interval $0\leq r<9$; taking the absolute value would give a different class.

Answer. Both requested residues are $7$. The class consists of the integers $7+9k$.

Check. $-38-7=-45=9(-5)$; for example, $-2,7,16$ are also in this class.

Worked example 2: the zero class

Question. Find the least nonnegative and least positive residues of $-36$ modulo $9$.

Plan. Reduce first; if the remainder is zero, move one complete modulus forwards to obtain a positive representative.

Why this step? Zero is nonnegative but not positive. The smallest positive integer congruent to zero modulo $9$ is $9$.

Answer. Least nonnegative residue $0$; least positive residue $9$.

Check. The representatives are the multiples of $9$; no integer strictly between $0$ and $9$ is in this class.

Watch out

“Least positive residue $=0$” is wrong because zero is not positive. For the zero class modulo $9$, write least nonnegative residue $0$, but least positive residue $9$.

Three equivalence properties

For integers $a,b,c$ and the same positive integer modulus $n$:

These follow because $0$, the negative of a multiple of $n$, and the sum of two multiples of $n$ are all multiples of $n$.

Not in the formula booklet: learn it.

Worked example 3: a valid chain

Question. Suppose $a\equiv5\pmod{12}$ and $b\equiv a\pmod{12}$. Show that $b\equiv5\pmod{12}$. Must $b=5$?

Plan. Link the two given congruences, then distinguish a congruence class from a single integer.

Why this step? Transitivity identifies the remainder, not the number of whole moduli added to it.

Answer. $b\equiv5\pmod{12}$, but $b$ need not equal $5$.

Check. $29-5=24=2(12)$, so $29$ is a valid alternative.

Worked example 4: an invalid mixed-modulus chain

Question. Suppose $a\equiv5\pmod{12}$ and $b\equiv a\pmod8$. Must $b\equiv5\pmod{12}$?

Plan. Find values satisfying both premises but failing the proposed conclusion.

Why this step? One counterexample disproves a claim that is supposed to hold for every pair of integers satisfying the premises.

Answer. No. The two different moduli do not form a transitive chain modulo $12$.

Check. $13\equiv1\pmod{12}$, while the claimed residue was $5$.

Watch out

The proposed chain $b\equiv a\pmod8$, $a\equiv5\pmod{12}$, therefore $b\equiv5\pmod{12}$, is invalid: its links use different moduli. With $a=5,\ b=13$, both premises hold but the conclusion fails.

Addition and subtraction laws

If $a\equiv b\pmod n$ and $c\equiv d\pmod n$, then

For example, writing $a-b=kn$ and $c-d=\ell n$ gives

Thus the differences are still multiples of the same modulus.

Not in the formula booklet: learn it.