All courses › Discrete Mathematics › Modular arithmetic

Modular arithmetic

Modular arithmetic is about the remainder after integer division, like a clock that starts over. Two numbers are congruent modulo n if they leave the same remainder. It is used in check digits, hashing and cryptography.

a \equiv b \pmod n

a and b leave the same remainder when divided by n

(a\cdot b) \bmod n = ((a \bmod n)(b \bmod n)) \bmod n

work with remainders along the way

Symbols

$\bmod$	remainder of integer division
$n$	modulus

Example

Which weekday is it in 100 days if today is Monday?

$100 \bmod 7 = 2$ , so it will be Wednesday.

Reduce the numbers along the way, so you never have to handle huge numbers.

Practise graphs and modular arithmetic for free →

← Graphs · Greatest common divisor →

Part of Discrete Mathematics: Graphs and modular arithmetic.