Modular Arithmetic Basics

It's 9 o'clock. What time will it be in 5 hours? In the States, nobody says 14. You go round the clock and land on 2. That's modular arithmetic: counting on a loop instead of a line. The number of positions on the loop is the modulus; on a 12-hour clock it's 12.

On a 24-hour clock, used in much of the world and by the military, 9:00 plus 5 hours really is 14:00. That clock is a loop too, just a longer one, so the wrap-around comes later: 14:00 plus 15 hours is 29, which lands on 5:00, because 29 mod 24 = 5. Same idea, different modulus.

Mathematicians start their clocks at 0, so a 12-hour clock has the positions 0 to 11 (the 24-hour clock already starts at 00:00). Try different clocks below. With a modulus of 7, the positions are the days of the week; with 2, every number is just “even” (0) or “odd” (1).

a mod n is the remainder when you divide a by n. 14 ÷ 12 is 1 with 2 left over, so 14 mod 12 = 2. The “1” counts the full laps of the clock, and the remainder is where you end up.

Every whole number can be written as a = q × n + r, with r between 0 and n − 1. The remainder r is the answer. Negative numbers work too: going back 3 hours from 0 lands on 9, so −3 mod 12 = 9. (Some calculators and programming languages answer −3 instead; on a clock that's the same position.)

When two numbers land on the same position, we say they're congruent and write 14 ≡ 2 (mod 12), read “14 is congruent to 2, mod 12”. Every ciphertext, message and shared secret in the worksheets is a remainder like this.

You already do modular arithmetic all the time:

• Hours are mod 12 or mod 24: 22:00 plus 5 hours is 27 mod 24 = 3:00.
• Days of the week are mod 7. Number them Sunday = 0 to Saturday = 6, and “100 days after a Tuesday” is (2 + 100) mod 7 = 4, a Thursday.
• Months are mod 12: 5 months after November (month 11) is 16 mod 12 = 4, April.
• Odometers are mod 1,000,000: one more mile after 999,999 rolls over to 000,000.
• Compass bearings are mod 360: turning 90° right from 300° gives 390 mod 360 = 30°.
• The last digit of any number is that number mod 10, and even or odd is mod 2.

Adding, subtracting and multiplying all work on a clock, and you can take the remainder whenever you like: before, during or after. (17 × 23) mod 10 is the same as (7 × 3) mod 10 = 1, which is why a computer can multiply 45-digit numbers mod n without them ever getting bigger than n².

Division is different. Dividing by a means multiplying by a number x with a × x ≡ 1, called the inverse of a. In the table below, a row with a 1 in it has an inverse. Look at mod 10: the rows for 2, 4, 5, 6 and 8 never reach 1, because those numbers share a factor with 10. Now switch to mod 7: every row (except 0) has a 1, because 7 is prime. That's why so many cryptosystems work mod a prime.

Keep multiplying by the same number and the remainders eventually repeat. Powers of 3 mod 7 go 3, 2, 6, 4, 5, 1, and then start again. The length of the loop is the order of 3. Here, 3 visits every non-zero position before repeating, so it's called a generator.

Going forwards is easy: 3⁵ mod 7 = 5. Going backwards, from “5” to “which power?”, is the discrete logarithm. Here you can just read it off the list. For a 45-digit prime the loop can be about 10⁴⁵ steps long, far too long to list. In general that's what makes ElGamal, Diffie–Hellman and their cousins secure. Puzzles get around it by choosing primes with a special weakness; section 11 shows what it is.

Fermat's little theorem. If p is prime and a isn't a multiple of p, then

So every loop of powers mod a prime closes within p − 1 steps, and its length divides p − 1. Try it in section 5: every order mod 7 is 1, 2, 3 or 6.

Euler's φ (“phi”). φ(n) counts the numbers from 1 to n that share no factor with n. For n = 15 they are 1, 2, 4, 7, 8, 11, 13 and 14, so φ(15) = 8. Two cases come up again and again:

Why the second one: from 1 to pq, the numbers that do share a factor are the q multiples of p and the p multiples of q, and pq itself is counted in both lists. That leaves pq − q − p + 1 = (p − 1)(q − 1). For 15: 15 − 5 − 3 + 1 = 8.

Euler's theorem extends Fermat's to any modulus. If a shares no factor with n, then

Why RSA decryption works. RSA picks d so that e × d = 1 + k × φ(n) for some whole number k. Then

Finding d needs φ(n), and finding φ(n) needs the primes p and q. That's why factoring breaks RSA.

A prime has no factors except 1 and itself: 2, 3, 5, 7, 11, 13, … Every whole number splits into primes in exactly one way, for example 360 = 2³ × 3² × 5.

The greatest common divisor, gcd(a, b), is the biggest number that divides both. When it's 1, the numbers “share no factor” (they're coprime), and that's the condition behind inverses (section 4) and Euler's theorem (section 6). Euclid's algorithm finds it without factoring anything; section 8 shows the steps.

φ from the factors. Once you know the primes, φ is quick: multiply n by (1 − 1/p) for each different prime p. For 360: 360 × ½ × ⅔ × ⅘ = 96. With two primes this is the (p − 1)(q − 1) from section 6.

Why factoring is hard. The simplest method tries dividing by every number up to √n. That's instant for the 15-digit numbers below, but a 45-digit number would need about 10²² tries. Cleverer methods, like the quadratic sieve the worksheets use, split 45 digits in about a second. They still slow down steeply: the largest RSA challenge number factored so far, 250 digits, took about 2,700 CPU-core-years in 2020, and real keys are around 600 digits.

Working out 7⁵⁶⁰ mod 561 by multiplying 7 by itself 559 times is slow, and a 45-digit exponent would take forever. Instead, square repeatedly (7, 7², 7⁴, 7⁸, …, taking the remainder each time), and multiply together the squares matching the 1s in the exponent written in binary. A 45-digit exponent needs only about 150 squarings. Big numbers work in these boxes.

To find an inverse, run Euclid's algorithm for the greatest common divisor: divide, keep the remainder, repeat. If the remainders reach 1, the inverse exists. Alongside each remainder the table keeps a multiplier, chosen so that

Each new multiplier is the one from two rows up, minus “goes in” times the one from the row above. Start with 0 for n and 1 for a. On the row where the remainder is 1, the multiplier is the inverse. If it's negative, add n: for 7 mod 40 that row says −17, and −17 + 40 = 23. This is how RSA's private exponent d is found from e.

Picture a 3-hour clock and a 5-hour clock ticking together. Which count shows 2 on the first and 3 on the second? Counting up: 8 (8 mod 3 = 2, 8 mod 5 = 3). Because 3 and 5 share no factor, the pair of positions repeats only every 3 × 5 = 15 ticks, so 8 is the only answer between 0 and 14.

That's the Chinese Remainder Theorem (CRT): knowing a number modulo several moduli that share no factors pins it down modulo their product. Cryptosystems use it to split one big calculation into smaller ones, mod p and mod q, and glue the answers back together.

Which numbers x have x² ≡ a (mod n)? Mod 7, squaring 1 to 6 gives 1, 4, 2, 2, 4, 1, so only 1, 2 and 4 have square roots. Those are called quadratic residues (squares, for short). Mod an odd prime, exactly half the non-zero numbers are squares, and each has two roots, x and p − x (on the clock, x and its mirror image).

Euler's criterion tells squares from non-squares in one power:

The shortcut for primes that leave remainder 3 when divided by 4 (like 7, 11, 19, 23):

It works because x² = a^(p+1)/2 = a × a^(p−1)/2 ≡ a × 1 = a, using Euler's criterion. Other primes need a longer method (Tonelli–Shanks), which the worksheets do for you.

Mod a product of two primes, a square has four roots. Solve mod each prime, then glue the pieces together with the CRT (section 9). For x² ≡ 1 (mod 15): mod 3 the roots are ±1, mod 5 they're ±1, and the four combinations are:

Check: 4² = 16, 11² = 121 and 14² = 196 all leave remainder 1 mod 15. Anyone can square, but finding all four roots needs the two primes. A system that encrypts by squaring rests on exactly that.

Finding x with g^x ≡ h (mod p) is hard in general: the best general methods take about √p steps, around 10²² for a 45-digit prime. But the loop of powers of g has a length that divides p − 1 (section 6), and when p − 1 splits into small primes, the Pohlig–Hellman method solves the problem one small prime at a time:

1. For each prime q dividing p − 1, raise both g and h to the power (p − 1)/q. That pushes both into a loop only q long, where only x mod q matters.
2. Find x mod q by searching that short loop.
3. Glue the answers together with the CRT (section 9).

Worked example. Find x with 3^x ≡ 22 (mod 31). Here p − 1 = 30 = 2 × 3 × 5.

Read each answer from the loop's position: 22¹⁵ ≡ 30 is step 1 of the first loop, 5 is step 2 of the second, 8 is step 2 of the third. Then the CRT: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 2 (mod 5) gives x = 17, and indeed 3¹⁷ mod 31 = 22.

What decides the difficulty is the largest prime factor of p − 1, not the size of p. A 45-digit prime whose p − 1 is built from primes of 13 digits or fewer needs only a few million steps per piece. Real systems avoid this by using “safe primes” p = 2q + 1 with q prime, so one piece is almost as big as p and the trick gains nothing. The worksheets show the pieces for any prime you give them.

Every step of RSA, small enough to check by hand. Work each one out (the widgets above help), then open the answer.

• Remainders (sections 1–3): every ciphertext, message and shared secret is a remainder after dividing by the public modulus.
• Inverses (sections 4 and 8): private exponents, and “dividing out” a shared secret.
• Powers, Fermat and Euler (sections 5, 6 and 8): encrypting and decrypting, and why decryption undoes encryption.
• Factoring and φ (sections 6 and 7): the hard problem behind the systems built on a product of secret primes.
• The CRT (section 9): splitting work into mod p and mod q, then gluing it back together.
• Square roots (section 10): the systems that encrypt by squaring.
• Discrete logarithms (sections 5 and 11): the hard problem behind the systems built on powers of a base, and why puzzle-sized ones break.
• Turning numbers into text: see From Letters to Numbers.

Which system a puzzle uses, and which of these ideas it leans on, is for you to work out. Back to the worksheets.

Days of the week are arithmetic mod 7, and John Conway turned that into a trick for finding the day of the week of any date in your head: the Doomsday rule. It has its own page, with the formulas, why each one works, a calculator and a practice game: Day of the Week.