Integer Division and Modular Arithmetic

Integer Division

When you divide one integer (x) by another positive integer (d), you get:

A quotient (q), how many times d fits in x, and
A remainder (r), what is left over

Think of when you want to split up a pizza among 3 people, where a pizza usually contains 8 slices. How many slices can each person have, and how many are left over? In normal division, we would get 8 ÷ 3 = 2.667, but nobody wants .667 of a pizza!

In integer division, we ask ourselves, “How many times can 3 fit into 8?”, and in this case, it’s 2 times. To get the remainder, we would do 8 – (2*3) = 2. In English, this means three people can have 2 slices of pizza, with 2 slices leftover.

This topic can be represented as the following equation x = d * q + r where:

x is the number being divided,
d is the divisor,
q is the quotient,
r is the remainder, and
0 ≤ r < d

Example: Numbers 0-6 with d = 3

x	Equation	q	r
0	0 = 3 · 0 + 0	0	0
1	1 = 3 · 0 + 1	0	1
2	2 = 3 · 0 + 2	0	2
3	3 = 3 · 1 + 0	1	0
4	4 = 3 · 1 + 1	1	1
5	5 = 3 · 1 + 2	1	2
6	6 = 3 · 2 + 0	2	0

Modular Arithmetic

Modular arithmetic is a type of arithmetic where numbers “wrap around” after reaching a certain value. That specific value that is wrapped around is known as the modulus. This strategy is a quick way to get remainders. In equations, the modulo (the operation for modular arithmetic) is symbolized by mod or %.

Example: Telling Time

Think of a clock — it wraps around after 12 hours.

8 mod 12 = 8 → means 8AM
15 mod 12 = 3 → means 3 PM (because 12 fits into 15 once, leaving 3 leftover)

So “mod” just gives you the remainder after division!

Binary Application

Let’s try using this with our previous binary examples.

Example 1: 1001 (binary to decimal)

First, let’s set up our equation, we’ll use x = d*q + r where

X = 1001 → the current binary number we want to convert
d = 2, which in binary is 10₂ → our divisor, our binary base, since each bit is a power of 2
R = x mod 2 → what remains after removing a bit
Q = x / 2 (integer division) → the current binary digit, has to be 0 or 1

Conversion Table for 26 (decimal to binary)

x	Q = x / 10₂	R = x mod 10₂	Explanation
1001₂	100₂	1	1001₂ = 10₂×100₂ + 1₂ → remainder 1 → least significant bit (1’s place)
100₂	10₂	0	100₂ = 10₂×10₂ + 0₂ → next bit (2’s place)
10₂	1₂	0	10₂ = 10₂×1₂ + 0₂ → next bit (4’s place)
1₂	0₂	1	1₂ = 10₂×0₂ + 1₂ → final bit (8’s place)

Now we can rebuild the decimal number by multiplying each value in the q column by its power of 2 if their r value is 1:

100₂ = 2^3 = 8

1₂ = 2^0 = 1

1001₂→ 8+1 → 9

Example 2: 26 (decimal to binary)

First, let’s set up our equation, we’ll use x = d*q + r where

X = 26 → the current decimal number we want to convert
d = 2 → our divisor, our binary base, since each bit is a power of 2
R = x mod 2 → what remains after removing a bit
Q = x / 2 (integer division) → the current binary digit, has to be 0 or 1

Conversion Table for 26 (decimal to binary)

x	Q = x / 2	R = x mod 2	Explanation
26	13	0	26 = 2×13 + 0 → remainder 0 → last bit is 0
13	6	1	13 = 2×6 + 1 → remainder 1 → next bit is 1
6	3	0	6 = 2×3 + 0 → remainder 0 → next bit is 0
3	1	1	3 = 2×1 + 1 → remainder 1 → next bit is 1
1	0	1	1 = 2×0 + 1 → remainder 1 → final bit is 1

Now read the remainders bottom to top: 26 → 11010

Applications

We have previously seen that integer division and modular arithmetic can be used in telling time but there are other ways this can be used such as:

Hashing (to efficiently store data)
Cryptography (for secure and private messaging)
Scheduling (including clocks, calendars, etc.)
Programming