Modular Arithmetic

Table of Contents

1. Math That Wraps Around
2. Remainder and Division
3. Even, Odd, and Every Nth Item
4. The Negative Number Trap
5. Carousels and Circular Buffers
6. Clocks and Days of the Week
7. Hash Buckets
8. Check Digits and the Luhn Algorithm
9. Recipe: modular.js for mathlab
10. Try It Yourself

1. Math That Wraps Around

If it is 10 o'clock and you wait 5 hours, it is not 15 o'clock on a 12-hour clock. It is 3 o'clock. The numbers wrapped around after reaching 12. Mathematicians call this modular arithmetic, and % is the operator that does it.

You already met % as the "remainder" operator. In this chapter you see how that one small symbol drives:

• carousels and "next/previous" buttons that loop,
• zebra-striped table rows,
• days of the week and times on a clock,
• the buckets inside a hash table (and so inside every Set and Map),
• the check digit on a bank card that catches typing mistakes.

It also hides one nasty trap, covered in section 4. Most developers hit it once, in production, on a Monday morning.

2. Remainder and Division

Remember long division from school: 17 ÷ 5 = 3 with 2 left over. The 3 is the quotient and the 2 is the remainder. In JavaScript:

console.log(Math.floor(17 / 5)); // 3  (the quotient)
console.log(17 % 5);             // 2  (the remainder)

The two always fit together: 5 × 3 + 2 = 17. In general:

dividend = divisor × quotient + remainder

The remainder is always smaller than the divisor, so n % 5 can only give 0, 1, 2, 3, or 4. That is the secret of wrapping: no matter how big n grows, n % 5 always lands inside that small range, and it cycles in order as n goes up:

When n % 5 is 0, n divides evenly by 5. We say n is a multiple of 5, or that 5 divides n.

A real example: a video is 130 seconds long. How should the player show it?

const total = 130;

console.log(Math.floor(total / 60)); // 2   minutes
console.log(total % 60);             // 10  seconds

That is "2:10". Division gives the big unit, remainder gives what is left. The same pattern turns 47 items into pages: Math.floor(47 / 10) is page 4 (counting from 0) and 47 % 10 is slot 7 on that page.

3. Even, Odd, and Every Nth Item

The simplest modular question is "even or odd?", which is "what is n % 2?":

console.log(10 % 2); // 0  -> even
console.log(7 % 2);  // 1  -> odd

Even numbers leave remainder 0. Odd numbers leave 1. Zebra striping a table with row numbers 0, 1, 2, ... is therefore a one-liner:

const rows = [0, 1, 2, 3].map((r) => (r % 2 === 0 ? "light" : "dark"));

console.log(rows); // [ 'light', 'dark', 'light', 'dark' ]

Replace 2 with any number to get "every Nth":

// Show an ad after every 5th post
for (let post = 1; post <= 12; post++) {
  if (post % 5 === 0) console.log(`ad after post ${post}`);
}
// ad after post 5
// ad after post 10

Round-robin works the same way. Three servers share requests in turn, and request number n goes to server n % 3:

const servers = ["s1", "s2", "s3"];

console.log([0, 1, 2, 3, 4].map((n) => servers[n % 3]));
// [ 's1', 's2', 's3', 's1', 's2' ]

4. The Negative Number Trap

Now the trap. Try % with a negative number:

console.log(-1 % 5); // -1   (!)
console.log(-7 % 5); // -2

You might expect 4 because on a clock with 5 positions, going back one step from 0 lands on 4. But JavaScript's % gives -1.

The reason: % is the remainder operator, not the modulo operator. The two agree for positive numbers and disagree for negatives. JavaScript's remainder keeps the sign of the left-hand number, so a negative number in gives a negative (or zero) number out.

Where does this bite? Anywhere an index can go down: a "previous" button that does (index - 1) % length will produce -1 when index is 0, and slides[-1] is undefined. A blank carousel. The fix is a small function that always returns a number from 0 to m - 1:

function mod(n, m) {
  return ((n % m) + m) % m;
}

console.log(mod(-1, 5)); // 4
console.log(mod(-7, 5)); // 3
console.log(mod(7, 5));  // 2
console.log(mod(10, 5)); // 0

Why does it work? Step by step with n = -7 and m = 5:

1. n % m is -2: in range from -(m - 1) to m - 1.
2. Add m: -2 + 5 = 3. Now the value is never negative (the smallest possible is -(m - 1) + m = 1, and positive inputs only get bigger).
3. Take % m again: 3 % 5 = 3. This second % handles inputs that were already positive, such as 7 % 5 = 2, then 2 + 5 = 7, then 7 % 5 = 2.

One caveat: m must be positive. mod(5, 0) gives NaN, because dividing by zero has no remainder.

5. Carousels and Circular Buffers

A carousel shows slide i of length slides. "Next" adds one and "previous" subtracts one, and both wrap around at the ends. With mod:

function nextIndex(i, length) {
  return mod(i + 1, length);
}

function prevIndex(i, length) {
  return mod(i - 1, length);
}

console.log(nextIndex(4, 5)); // 0   (last slide, next goes to first)
console.log(prevIndex(0, 5)); // 4   (first slide, previous goes to last)

No if statements, no special cases. That is the beauty of modular arithmetic: the "edge case" disappears into the formula.

The same trick builds a circular buffer (also called a ring buffer): a fixed-size list that keeps only the most recent items, such as the last 3 log messages. When it is full, a new item overwrites the oldest one.

class Ring {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.start = 0; // index of the oldest item
    this.size = 0;
  }

  push(item) {
    const slot = (this.start + this.size) % this.items.length;
    if (this.size < this.items.length) {
      this.size++;
    } else {
      this.start = (this.start + 1) % this.items.length; // drop oldest
    }
    this.items[slot] = item;
  }

  toArray() {
    return Array.from(
      { length: this.size },
      (_, k) => this.items[(this.start + k) % this.items.length],
    );
  }
}

const recent = new Ring(3);
for (const n of [1, 2, 3, 4, 5]) recent.push(n);

console.log(recent.toArray()); // [ 3, 4, 5 ]

Instead of shifting every element left each time (which costs more as the list grows), the buffer just moves two indexes around a loop. Audio players, network buffers, and "undo history" screens use this idea.

Sometimes you want to wrap into a range that does not start at 0, like months 1..12. Shift down, wrap, shift back:

function wrap(n, min, max) {
  return min + mod(n - min, max - min + 1);
}

console.log(wrap(13, 1, 12)); // 1   (month 13 is January)
console.log(wrap(0, 1, 12));  // 12  (month 0 is December)

6. Clocks and Days of the Week

Clock arithmetic is the original modular arithmetic. Three hours after 11 o'clock on a 12-hour clock:

console.log((11 + 3) % 12); // 2

For hours on a 24-hour clock, with a fix for going backwards, use mod from above:

const pad = (n) => String(n).padStart(2, "0");

console.log(pad(mod(22 + 5, 24))); // "03"  (5 hours after 22:00)
console.log(pad(mod(2 - 5, 24)));  // "21"  (5 hours before 02:00)

Days of the week are a loop of 7. Number them 0 for Sunday through 6 for Saturday, which is exactly what JavaScript's getDay() does:

const days = ["Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"];

// Today is Wednesday (3). What day is 10 days from now? 5 days ago?
console.log(days[mod(3 + 10, 7)]); // "Sat"
console.log(days[mod(3 - 5, 7)]);  // "Fri"

Look at the second line: (3 - 5) % 7 would be -2 and days[-2] is undefined. The mod helper saves you again.

Calendar tools (the "which weekday does this month start on?" grid) are built from exactly this: the weekday number plus the day count, taken mod 7.

7. Hash Buckets

Back in chapter 5 we said a Set answers "is X in here?" almost instantly. Here is the trick behind it, and it is modular arithmetic.

Imagine 8 empty buckets, numbered 0 to 7. To store a name, you turn it into a number with a hash function, then use % 8 to pick a bucket. Later, to look the name up, you compute the same number and open only that one bucket instead of searching everything.

A tiny hash function that adds up the character codes:

function hash(text) {
  let h = 0;
  for (const char of text) {
    h = (h * 31 + char.codePointAt(0)) % 1000003;
  }
  return h;
}

for (const name of ["dara", "sokha", "vanna", "sreyneang"]) {
  const h = hash(name);
  console.log(name, h, h % 8);
}
// dara 75939 3
// sokha 617537 1
// vanna 974089 1
// sreyneang 70922 2

Here h * 31 + code mixes each letter into the number, and % 1000003 keeps it from growing too big (a technique that also avoids the limits you will see in the next chapter). Then h % 8 picks the bucket: dara goes to bucket 3, sokha and vanna both land in bucket 1, and sreyneang goes to bucket 2.

Two names in the same bucket is called a collision. It is normal and every hash table handles it, for example by keeping a short list in each bucket. Searching a short list is still far quicker than searching everything. With more buckets than items, collisions stay rare. You will count exactly how likely they are in Probability Basics.

Real hash functions are far better mixed than this toy, and real languages choose the details for you. You will never write one by hand, but knowing hash % size explains why a Set is quick and why a bad hash makes it slow.

8. Check Digits and the Luhn Algorithm

The last digit of a bank card number is not random. It is a check digit, computed from the other digits so that a typing mistake is almost always detected. Credit and debit cards, many ID numbers, and IMEI numbers use the Luhn algorithm, invented in 1954 and still everywhere. It catches any single mistyped digit and most swapped neighbors, and it needs only %.

The recipe for checking a number:

1. Starting from the rightmost digit, move left. Leave the first digit as it is, double the second, leave the third, double the fourth, and so on.
2. If a doubled digit is greater than 9, subtract 9 (it's the same as adding its two digits, so 16 becomes 1 + 6 = 7).
3. Add everything up.
4. The number is valid if the total is a multiple of 10, which is total % 10 === 0.

Walk through the standard test number 79927398713. Reading from the right:

The doubled 8 is 16, minus 9 gives 7. The doubled 9 is 18, minus 9 gives 9. The total is 3 + 2 + 7 + 7 + 9 + 6 + 7 + 4 + 9 + 9 + 7 = 70, and 70 % 10 === 0, so the number is valid.

In code:

function luhnCheck(digits) {
  const clean = String(digits).replace(/\D/g, ""); // drop spaces and dashes
  if (clean.length < 2) return false;

  let sum = 0;
  let double = false;

  for (let i = clean.length - 1; i >= 0; i--) {
    let d = Number(clean[i]);
    if (double) {
      d *= 2;
      if (d > 9) d -= 9;
    }
    sum += d;
    double = !double; // alternate: no, yes, no, yes...
  }

  return sum % 10 === 0;
}

console.log(luhnCheck("79927398713")); // true
console.log(luhnCheck("79927398714")); // false (last digit mistyped)

/\D/g is a pattern meaning "every character that is not a digit", so "4539 1488 0343 6467" becomes plain digits. Using double = !double is the boolean toggle from Boolean Logic.

To create a card number, you work backwards: choose the check digit that makes the total a multiple of 10. Trying all ten possibilities is simple and fast enough:

function luhnCheckDigit(partial) {
  const clean = String(partial).replace(/\D/g, "");
  for (let d = 0; d <= 9; d++) {
    if (luhnCheck(clean + d)) return d;
  }
}

console.log(luhnCheckDigit("7992739871")); // 3

A word of caution: Luhn detects typos, not fraud. Anyone can generate a number that passes. It is a first, cheap check in a form, so you can say "that does not look right" before you ever contact a payment service such as KHQR or a card processor. Never treat it as proof that a card is real.

9. Recipe: modular.js for mathlab

Create src/modular.js in mathlab and collect everything from this chapter:

// A true modulo: the result is always between 0 and m - 1.
export function mod(n, m) {
  return ((n % m) + m) % m;
}

// Wrap n into the range min..max (both included).
export function wrap(n, min, max) {
  return min + mod(n - min, max - min + 1);
}

// Carousel helpers: indexes loop around.
export function nextIndex(i, length) {
  return mod(i + 1, length);
}

export function prevIndex(i, length) {
  return mod(i - 1, length);
}

// Luhn check: is this card-style number valid?
export function luhnCheck(digits) {
  const clean = String(digits).replace(/\D/g, "");
  if (clean.length < 2) return false;

  let sum = 0;
  let double = false;
  for (let i = clean.length - 1; i >= 0; i--) {
    let d = Number(clean[i]);
    if (double) {
      d *= 2;
      if (d > 9) d -= 9;
    }
    sum += d;
    double = !double;
  }
  return sum % 10 === 0;
}

// Which final digit makes the number valid?
export function luhnCheckDigit(partial) {
  const clean = String(partial).replace(/\D/g, "");
  for (let d = 0; d <= 9; d++) {
    if (luhnCheck(clean + d)) return d;
  }
}

Add the export to src/index.js:

export * from "./modular.js";

Then update demo.js:

import {
  mod,
  wrap,
  nextIndex,
  prevIndex,
  luhnCheck,
  luhnCheckDigit,
} from "./src/modular.js";

console.log(-1 % 5, mod(-1, 5));
console.log(mod(7, 5), mod(-7, 5), mod(10, 5));
console.log(wrap(13, 1, 12), wrap(0, 1, 12));
console.log(nextIndex(4, 5), prevIndex(0, 5));
console.log(luhnCheck("79927398713"), luhnCheck("79927398714"));
console.log(luhnCheckDigit("7992739871"));
console.log(luhnCheck("4539 1488 0343 6467"));
console.log(luhnCheck("4539 1488 0343 6476"));

Run it:

node demo.js

-1 4
2 3 0
1 12
0 4
true false
3
true
false

The first line shows the trap and the fix side by side. The last two lines show Luhn catching a typo: swapping the last two digits of the valid card number 6467 into 6476 makes it fail.

10. Try It Yourself

1. Remainder or modulo? Predict, then check: -10 % 3, mod(-10, 3), 10 % -3. Which of them are unexpected?
2. Page and slot. A table shows 25 rows per page. Write locate(n) that returns { page, row } for item number n (counting from 0). What does item 100 give?
3. Build a clock. Write addMinutes(time, delta) where time is minutes since midnight (0 to 1439) and delta can be negative. Format the result as "HH:MM". What is 00:10 minus 30 minutes?
4. Next Friday. Using days and mod, write daysUntil(today, target) that returns how many days from today until the next target weekday (both numbers 0 to 6). The answer for today = Friday and target = Friday should be 0.
5. Break Luhn. Take a valid number and change one digit. Does luhnCheck always fail? Now swap two neighboring digits and try again. Find one example of a swap that Luhn does not catch (hint: swap the neighboring digits 09 into 90 in 123409567).
6. Bucket spread. Hash 20 different words with the hash function and count how many land in each of the 8 buckets. Are they evenly spread? Try 16 buckets and compare.

Modular arithmetic works because numbers in a computer have a fixed size and wrap around, just like the clock. In the next chapter, Integers, Overflow and Precision, we look at what happens when a number runs out of room, and why money should never be stored as a floating-point number.