Lesson

Modular Arithmetic

Modular arithmetic works with remainders. $a \\bmod m$ is the remainder when $a$ is divided by $m$. It underpins hashing, cryptography, and cyclic structures in computer science.

Practice

Q1

Compute $17 \bmod 5$.

Show hint

$15$ is the largest multiple of 5 below 17.

Q2

Compute $23 \bmod 7$.

Show hint

Take the remainder of $23$ divided by $7$.

The greatest common divisor (gcd) is the largest integer dividing two numbers, and modular exponentiation raises a number to a power under a modulus — the workhorse of public-key cryptography.

Quiz

Q1

Compute $\gcd(12, 18)$.

Show hint

List the common divisors and take the largest.

Q2

Compute $(7 + 8) \bmod 6$.

Show hint

Add first, then take the result mod 6.

Q3

Compute $2^5 \bmod 3$.

Show hint

$2^5 = 32$; then take mod 3.