Congruences modulo n

This appendix is outside the Fifth-year scientific syllabus, but it shows how elementary arithmetic (gcd, divisors, congruences) became — starting from the 1970s — the basis of modern digital security. It is a splendid example of “pure” mathematics that turns out to be unpredictably applied. The starting point is the congruence relation.

Definition — Congruence modulo $n$

Given $a,b\in\mathbb{Z}$ and $n\in\mathbb{N}$ with $n\ge 2$, we say that $a$ is congruent to $b$ modulo $n$, and we write $a \equiv b \pmod n,$ if $n$ divides $a-b$. Equivalently: $a$ and $b$ give the same remainder in the division by $n$.

Examples: $17\equiv 2\pmod 5$ (since $17-2=15$ is divisible by $5$); $-3\equiv 4\pmod 7$. Modular arithmetic is that of the clock: $14$ hours $+ 13$ hours $= 27\equiv 3\pmod{24}$ (3 o’clock the next morning).

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Congruenza
Skills: Usare formule