Modulär aritmetik är aritmetik på en cirkel. Två tal är kongruenta modulo n om de skiljer sig med ett multiplum av n. En klocka räknar modulo 12: 10 timmar efter klockan 5 är klockan 3, inte 15. Den här enkla idén ligger till grund för all modern kryptografi, hashfunktioner, felkorrigerande koder och stor del av talteorin.
Varje rad och kolumn innehaller {0,1,2,3,4} exakt en gang. De fem elementen bildar en sluten grupp under addition mod 5.
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Modulär aritmetik definierar kongruens: a är kongruent med b mod n om n delar a-b. Gauss systematiserade det 1801. Det ligger till grund för all modern publick-nyckel-kryptografi: RSA-kryptering förlitar sig på Fermats lilla sats, som säger att a^(p-1) är kongruent med 1 mod p för varje primtal p som inte delar a. Hashfunktioner använder modulära operationer för att avbilda stora indata till utdata av fast storlek. Heltalen mod n bildar en komplett ring, och när n är primtal ett ändligt kropp.