Remainders and Modular Arithmetic

The divisibility-and-primes lesson leaned on one small test over and over. To check whether 7 divides 91, it asked whether the division came out clean. 91 divided by 7 is 13 with nothing left over, so 7 is a factor. That leftover amount, the part that does not divide evenly, is called the remainder, and it carries more information than the clean-or-not verdict alone. A remainder of zero was the only case the factor test cared about. This lesson keeps every other remainder too, and builds a small, sturdy branch of math on top of them.

The remainder and the % operator

When one whole number is divided by another, two facts fall out: how many whole times the second number fits into the first, and how much is left over. Python hands back each fact with its own operator. The double slash // gives the whole count. The percent sign %, read out loud as "mod" or "modulo", gives the remainder.

print(17 // 5)  # 3
print(17 % 5)   # 2

Five fits into seventeen three whole times, which accounts for fifteen of it, and two are left over. The two results always snap back together into the original number: 5 * 3 + 2 is 17. Whenever the remainder is zero, the division was clean and the divisor is a factor, which is exactly the test from the previous lesson written in one symbol. 18 % 6 is 0, so 6 divides 18. 18 % 7 is 4, so 7 does not.

The remainder from % n is always one of the numbers from 0 up to n minus 1. Divide anything at all by 5 and the leftover can only be 0, 1, 2, 3, or 4. Divide by 12 and it lands somewhere from 0 to 11. That bounded, predictable range is the whole point. The modulo operation takes numbers of any size and folds them down into a small fixed set of slots.

Clock arithmetic: wrapping around a fixed size

A twelve-hour clock ran on modular arithmetic centuries before the first computer. Five hours after nine o'clock is not fourteen o'clock. The hands sweep past twelve and land on two. The clock counts up, then wraps back to the start once it reaches its size. That wrap is a modulo by 12.

print((9 + 5) % 12)  # 2

Nine plus five is fourteen, and fourteen mod twelve is two, because twelve fits into fourteen once with two left over. The clock never shows a number outside 0 through 11 no matter how many hours get added, and % 12 enforces the same ceiling. Any counting that loops back on itself after a fixed number of steps is modular arithmetic in disguise: days of the week wrap every 7, compass degrees wrap every 360, and the position of a repeating pattern wraps every cycle length.

Even and odd is a clock of size two

The smallest useful modulus is 2. Dividing any whole number by 2 leaves a remainder of either 0 or 1 and nothing else, so % 2 sorts every number into two buckets. A remainder of 0 means the number is even. A remainder of 1 means it is odd.

print(4 % 2)  # 0
print(7 % 2)  # 1

def is_even(n):
    return n % 2 == 0

print(is_even(10))  # True
print(is_even(3))   # False

That n % 2 == 0 test is the single most common use of modulo in everyday code. It is how a program strips out every other row, alternates two colors, splits a list into two halves, or picks only the even numbers out of a sequence. The same one-line check is what the even-fibonacci challenge later in this module hinges on, so it is worth burning into memory now.

Greatest common divisor, found by remainders

The greatest common divisor of two numbers, written gcd, is the largest whole number that divides both of them with no remainder. The gcd of 48 and 18 is 6, because 6 divides both cleanly and nothing larger does. One way to find it is to list every factor of each number and compare, but that gets slow fast. A far quicker method comes from a single observation the Greek mathematician Euclid wrote down more than two thousand years ago.

Euclid noticed that the gcd of two numbers is the same as the gcd of the smaller number and the remainder of the larger divided by the smaller. In symbols, gcd(a, b) equals gcd(b, a % b). Each step swaps in a strictly smaller remainder, so the numbers shrink quickly, and the moment the remainder hits zero the number sitting beside it is the answer.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6

The loop is worth tracing by hand, because every line is just a remainder. Start with a as 48 and b as 18:

• 48 % 18 is 12, so the pair becomes a = 18, b = 12.
• 18 % 12 is 6, so the pair becomes a = 12, b = 6.
• 12 % 6 is 0, so the pair becomes a = 6, b = 0.
• b is now 0, so the loop stops and returns a, which is 6.

Three remainder steps, and the answer drops out. This is the same algorithm Python's own math.gcd(48, 18) runs under the hood, and it stays fast even on enormous numbers because the values collapse so quickly. The engine driving it is nothing but % applied again and again.

Least common multiple, straight from the gcd

The least common multiple of two numbers, written lcm, is the smallest number that both of them divide into evenly. The lcm of 4 and 6 is 12, because 12 is the first number that appears in both the 4-times table and the 6-times table. It is the number a scheduler wants when two repeating events need to line up: an event every 4 days and one every 6 days coincide every 12 days.

There is no need for a separate search once the gcd is in hand. The product of two numbers equals the product of their gcd and their lcm, so dividing the product by the gcd recovers the lcm directly.

def lcm(a, b):
    return a * b // gcd(a, b)

print(lcm(4, 6))    # 12
print(lcm(48, 18))  # 144

For 4 and 6, the product is 24 and the gcd is 2, so the lcm is 24 // 2, which is 12. Multiplying the two numbers and then dividing out the part they share removes the double-counting, and what remains is the smallest common multiple. The whole computation rides on the gcd, which itself rode on repeated remainders, so a single idea from the top of the lesson quietly powers all of it.

Where the remainder shows up

Modular arithmetic hides inside systems that look nothing like a clock. Two of the most common deserve a concrete look.

A hash table stores items in a fixed number of slots, called buckets, and decides where each item goes by taking the remainder of a key against the bucket count. With 8 buckets, key 12 lands in 12 % 8, which is bucket 4.

buckets = 8
for key in [12, 20, 5, 33]:
    print(key, "->", key % buckets)

That prints bucket 4 for 12, bucket 4 again for 20, bucket 5 for 5, and bucket 1 for 33. Keys 12 and 20 both mapped to bucket 4, which is called a collision, and handling collisions gracefully is one of the central jobs of a hash table. The modulo is what folds an unlimited range of keys down into a small, fixed set of homes.

A Caesar cipher shifts each letter forward by a fixed amount and wraps around the end of the alphabet, which is a clock of size 26. Shifting the letter x forward by 3 should not run off the end into nonexistent letters; it should wrap back to a.

def shift_letter(ch, k):
    base = ord("a")
    return chr((ord(ch) - base + k) % 26 + base)

print(shift_letter("x", 3))  # a

The letter x sits at position 23 in the alphabet, and 23 plus 3 is 26, which mod 26 is 0, the position of a. The cipher wheel is a modulus, plain and simple.

With this in hand, the even test n % 2 == 0 is ready to earn its keep. The even-fibonacci challenge in the Challenges tab asks for the sum of only the even-valued terms of the Fibonacci sequence, and telling even from odd is that one modulo check applied inside the loop. It is a clean first place to put remainders to work on a real problem.

Counting things without listing them one by one is the next tool the Make track reaches for, and it starts in counting-and-combinatorics, where the question shifts from what is left over to how many arrangements exist in the first place.