Modulus & Remainders — Use modulus (%) and interpret remainders - C Plus Plus

SECTION 1

Historical Context & Motivation

The concept of a remainder after division is among the oldest ideas in mathematics, tracing back to Euclid's algorithm for computing greatest common divisors around 300 BCE. When early computer scientists designed instruction sets for the first electronic machines, they recognized that modular arithmetic was indispensable for tasks ranging from address computation to cyclic buffer management. The modulus operator (%) was introduced in the C programming language by Dennis Ritchie and Ken Thompson in the early 1970s, inheriting the percent-sign notation from B, which in turn borrowed it from BCPL. C++ adopted this operator wholesale, preserving its integer-only semantics and later refining its behavior for negative operands in the C++11 standard.

~300 BCE • Euclid's Division Lemma

Euclid formalizes that for integers a and b, there exist unique q and r such that a = b × q + r, with 0 ≤ r < |b|. This identity underpins every modulus implementation.

1801 • Gauss's Disquisitiones Arithmeticae

Carl Friedrich Gauss publishes the foundational treatise on modular arithmetic, introducing the congruence notation a ≡ b (mod m) that becomes standard in number theory and cryptography.

1972 • C Language at Bell Labs

Dennis Ritchie designs C with the % operator for integer remainder. The sign of the result for negative operands is implementation-defined, a source of subtle bugs for decades.

1985 • C++ Inherits %

Bjarne Stroustrup's C++ inherits the % operator with identical semantics. Integer types (int, long, short, etc.) support it; floating-point types do not.

2011 • C++11 Standardizes Truncation

The C++11 standard mandates that integer division truncates toward zero, making the sign of a % b well-defined: the result carries the sign of the dividend. This eliminates decades of portability concerns.

Understanding the modulus operator is essential because it surfaces in nearly every domain of computer science: hashing, scheduling, graphics, cryptography, and everyday input validation. The central question this lesson addresses is deceptively simple—what exactly does the % operator compute, and how do you reason about its result when operands are negative, zero, or part of a complex expression?

SECTION 2

Core Principles & Definitions

The modulus operator (%) in C++ computes the remainder of integer division. Given two integer operands a and b, the expression a % b yields the value r satisfying the invariant a == (a / b) * b + (a % b). This identity is the single most important fact to internalize, because every edge case—including negative operands—follows directly from it and from the rule that C++ integer division truncates toward zero.

Integer-Only Operation

The % operator requires both operands to be integral types (int, long, short, char, etc.). Applying it to float or double is a compile-time error. For floating-point remainders, use std::fmod().

Truncation-Toward-Zero Invariant

Since C++11, a / b truncates toward zero. The remainder a % b is then uniquely determined by the identity a == (a/b)*b + a%b. The result's sign matches the dividend.

Zero Divisor Is Undefined

Evaluating a % 0 is undefined behavior, just like division by zero. On most platforms this triggers a hardware trap (SIGFPE on POSIX). Always guard against a zero divisor at runtime.

Sign of the Result

The result of a % b carries the sign of a (the dividend). Thus -7 % 3 == -1 and 7 % -3 == 1. This is a frequent source of bugs when wrapping indices.

Common Idioms

Testing even/odd (n % 2), cycling through arrays (i % size), extracting digits (n % 10), and implementing hash functions all rely on the modulus operator as a fundamental building block.

✦

KEY TAKEAWAY

Think of the modulus operator like a clock. If you walk 17 steps around a clock face with 12 positions, you end up at position 5 (because 17 % 12 == 5). The operator always tells you where you land after wrapping around. In C++, the twist is that if you walk backwards (negative dividend), the result is also negative—you haven't crossed zero yet, so the sign reflects your direction of travel.

SECTION 3

Visual Explanation

The number line shows 17 divided into three full groups of 5 (colored bands), with a remainder of 2 left over (pink segment). The lower boxes contrast positive and negative operand behavior, both satisfying the fundamental invariant.

The diagram above illustrates the geometric intuition behind the modulus operation. When you compute 17 % 5, you are essentially asking: after subtracting as many complete groups of 5 as possible from 17, how much is left over? The three colored bands represent the three complete groups (the quotient, 3), and the pink segment represents the remainder (2). Notice that the fundamental invariant holds in both the positive and negative cases. For -17 % 5, C++ truncates the quotient toward zero (yielding −3 rather than −4), so the remainder is −2 rather than +3. This truncation-toward-zero convention is critical when reasoning about negative operands.

SECTION 4

Mathematical Framework

The behavior of the C++ modulus operator is fully determined by two rules codified in the ISO C++11 standard (and retained in subsequent editions). Understanding these rules mathematically eliminates all ambiguity, even in edge cases involving negative numbers or mixed-sign operands.

DIVISION INVARIANT

a == (a / b) × b + (a % b)

Where a is the dividend, b is the divisor (b ≠ 0), a / b is the quotient (truncated toward zero), and a % b is the remainder. This identity holds for all integral types.

TRUNCATION RULE

a / b = trunc(a ÷ b)

C++ integer division truncates toward zero, not toward negative infinity. Thus -7 / 2 == -3 (not −4). This is equivalent to discarding the fractional part of the exact mathematical quotient.

SIGN OF REMAINDER

sign(a % b) == sign(a) or a % b == 0

The remainder inherits the sign of the dividend a. The divisor's sign has no effect on the result's sign. This follows directly from the invariant and the truncation rule.

EUCLIDEAN MODULUS (ALWAYS NON-NEGATIVE)

euclidean_mod(a, b) = ((a % b) + |b|) % |b|

When you need a non-negative remainder (e.g., for array index wrapping), apply this formula. It first computes the C++ remainder (possibly negative), adds |b| to shift it into the positive range, then takes % again to handle the case where a % b was already non-negative.

⚠

Floating-Point Remainders

The % operator does not work with float or double. For floating-point remainders, use std::fmod(a, b) from <cmath>. The function std::remainder(a, b) provides the IEEE 754 remainder, which rounds the quotient to the nearest integer rather than truncating.

SECTION 5

Detailed Behavior with Signed & Unsigned Types

To build robust intuition, it is helpful to study the modulus operator across a range of operand combinations. The table below exhaustively covers positive, negative, and mixed-sign cases, demonstrating how the truncation-toward-zero rule and the dividend-sign rule together determine every result. Pay close attention to the sign column, which is the primary source of bugs in production code.

Expression	a / b (trunc)	a % b	Verify: (a/b)*b + a%b
`17 % 5`	`3`	`2`	3×5 + 2 = 17 ✓
`-17 % 5`	`-3`	`-2`	(−3)×5 + (−2) = −17 ✓
`17 % -5`	`-3`	`2`	(−3)×(−5) + 2 = 17 ✓
`-17 % -5`	`3`	`-2`	3×(−5) + (−2) = −17 ✓
`5 % 17`	`0`	`5`	0×17 + 5 = 5 ✓
`0 % 5`	`0`	`0`	0×5 + 0 = 0 ✓
`10 % 2`	`5`	`0`	5×2 + 0 = 10 ✓

Complete behavior of C++ % operator across signed operands

Six essential modulus idioms used throughout C++ programming: parity checks, circular indexing, digit extraction, divisibility, hashing, and safe wrapping for negative operands.

The idiom diagram above is a reference card worth memorizing. Notice the warning in the Even/Odd Check box: testing n % 2 == 1 fails for negative odd numbers because -3 % 2 == -1, not 1. The correct odd test is n % 2 != 0. Similarly, the Euclidean Mod pattern ((a % b) + b) % b is indispensable when wrapping potentially negative values into the range [0, b)—a common need in graphics, game development, and circular data structures.

SECTION 6

Worked Example: Digital Clock Display

Suppose you have a total number of seconds elapsed since midnight and need to display the current time in HH:MM:SS format. This is a classic application of successive modulus and integer division operations. Let's walk through the solution step by step.

Convert 45296 seconds to HH:MM:SS

1
Step 1 — Identify the total seconds

We are given int totalSec = 45296;. Our goal is to extract hours, minutes, and seconds. The key insight is that modulus strips off the 'lower-order' units while integer division extracts the 'higher-order' units.

totalSec = 45296
2
Step 2 — Extract hours

There are 3600 seconds in an hour. Dividing gives the number of complete hours: int hours = totalSec / 3600;. Since 45296 / 3600 = 12 (truncated), we get 12 hours. To get the remaining seconds after removing complete hours: int remaining = totalSec % 3600; which is 45296 − 12 × 3600 = 45296 − 43200 = 2096.

hours = 12, remaining = 2096
3
Step 3 — Extract minutes

From the remaining 2096 seconds, extract complete minutes: int minutes = remaining / 60; yields 2096 / 60 = 34 (truncated). The leftover seconds: int seconds = remaining % 60; gives 2096 − 34 × 60 = 2096 − 2040 = 56.

minutes = 34, seconds = 56
4
Step 4 — Verify with the invariant

Reconstruct: 12 × 3600 + 34 × 60 + 56 = 43200 + 2040 + 56 = 45296, which matches our original input. The invariant a == (a/b)*b + a%b was applied twice—once at the hour level and once at the minute level.

45296 seconds = 12:34:56
5
Step 5 — Write the C++ code

The complete solution: int h = totalSec / 3600; int m = (totalSec % 3600) / 60; int s = totalSec % 60;. Note the elegant compression: the seconds extraction uses totalSec % 60 directly, because the hours don't affect the seconds remainder (3600 is a multiple of 60). This is a consequence of the mathematical property that if c divides b, then a % c == (a % b) % c.

h=12, m=34, s=56

SECTION 7

Pitfalls, Strengths & Best Practices

Pitfall / Scenario	Problem	Solution / Best Practice
Odd test with negative numbers	`-3 % 2 == -1`, not 1. Test `n % 2 == 1` fails.	Use `n % 2 != 0` or `n & 1` for odd check.
Division by zero	`a % 0` is undefined behavior. May crash or produce garbage.	Always validate the divisor: `if (b != 0)` before computing.
Negative index wrapping	`(-1) % 5 == -1`, not 4. Array access with negative index is UB.	Use Euclidean mod: `((a % b) + b) % b`
Using % with floating-point types	Compile error: % requires integral operands.	Use `std::fmod(a, b)` from `<cmath>`.
Signed/unsigned mixing	Mixing signed and unsigned operands triggers implicit conversion. A negative signed value becomes a large unsigned value.	Keep both operands the same signedness. Use `static_cast` explicitly.
INT_MIN % -1	The quotient overflows (since \|INT_MIN\| > INT_MAX). Undefined behavior on most architectures.	Guard against `b == -1` when dividend may be INT_MIN.

Common modulus pitfalls and their remedies

✦

KEY TAKEAWAY

The modulus operator in C++ is like a measuring tape that wraps around—but only in one direction by default. If you measure backwards (negative dividend), the tape reads a negative offset. To get a true circular wrap (always non-negative), you need the Euclidean modulus pattern: ((a % b) + b) % b. Internalizing this distinction between truncated and Euclidean remainder will save you from an entire class of off-by-one and wraparound bugs.

SECTION 8

Connection to Advanced Theory

The modulus operator is the C++ gateway to modular arithmetic, a branch of number theory with deep applications in computer science. From RSA encryption (which relies on modular exponentiation) to hash functions, error-detecting codes like CRC, and the structure of finite fields in coding theory, the humble % operator is the starting point for an enormous theoretical edifice. Understanding its precise semantics in C++ is a prerequisite for implementing these algorithms correctly.

This Lesson: % Basics	Advanced Topic
`a % b` for remainder	Modular exponentiation: `(base^exp) % mod` via repeated squaring (RSA, Diffie-Hellman)
Divisibility check `a % b == 0`	Euclidean GCD algorithm: `gcd(a, b) = gcd(b, a % b)`, foundation of `std::gcd()`
Cyclic index wrapping	Congruence classes and equivalence relations in abstract algebra (ℤ/nℤ rings)
Hash bucket assignment `h % capacity`	Universal hashing and perfect hashing theory; choosing prime-sized tables for uniform distribution
Digit extraction `n % 10`	Radix conversion, Horner's method for polynomial evaluation, and arbitrary-precision arithmetic libraries

From basic % to advanced computer science

As you progress through courses in algorithms and data structures, you will encounter modular arithmetic repeatedly. The C++17 standard library added std::gcd() and std::lcm() in <numeric>, both of which are built on the modulus operator internally. Competitive programming problems frequently require computing results modulo 10⁹ + 7 to prevent overflow—a technique that depends on understanding how modular arithmetic preserves addition and multiplication but not division (which requires modular inverses).

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why -7 % 3 evaluates to -1 in C++, not 2. What mathematical convention does C++ follow, and why does it matter when checking for odd numbers?

Show answer

C++ integer division truncates toward zero, so -7 / 3 == -2 (not −3 as floor division would give). From the invariant a == (a/b)*b + a%b, we get −7 == (−2)×3 + r, so r = −7 − (−6) = −1. The result 2 would come from floored (Euclidean) division where −7 / 3 = −3. This matters for odd checks because -7 % 2 == -1, not 1, so testing n % 2 == 1 incorrectly classifies negative odd numbers as even. Use n % 2 != 0 instead.

Question 2: BASIC CALCULATION

What is the output of the following code? int a = 100; int b = 7; std::cout << a/b << " " << a%b;

Show answer

The output is 14 2. Integer division 100 / 7 truncates to 14 (exact value ≈ 14.2857). The remainder is 100 − 14 × 7 = 100 − 98 = 2. Verification: 14 × 7 + 2 = 98 + 2 = 100 ✓. Both operands are positive, so no sign complications arise.

Question 3: INTERMEDIATE

Write a C++ function int euclideanMod(int a, int b) that returns the Euclidean (always non-negative) remainder when b > 0. Then trace through the function with a = -13, b = 5 and verify the result.

Show answer

Implementation: int euclideanMod(int a, int b) { return ((a % b) + b) % b; }. Trace with a = −13, b = 5: Step 1: -13 % 5 == -3 (since −13 / 5 = −2 truncated, and −2 × 5 + (−3) = −13). Step 2: -3 + 5 = 2. Step 3: 2 % 5 = 2. The result is 2, which lies in [0, 5). Verification: −13 = (−3) × 5 + 2, confirming the Euclidean division identity.

Question 4: APPLIED

You are implementing a round-robin scheduler for N threads. Each task gets a time quantum, then the scheduler moves to the next thread. Given int currentThread and int N (total threads), write the expression to advance to the next thread, wrapping around from N−1 to 0. Then explain what would go wrong if you used (currentThread + 1) % N but currentThread could somehow become negative due to a bug.

Show answer

The standard expression is currentThread = (currentThread + 1) % N;. When currentThread is at N−1, (N−1+1) % N = N % N = 0, correctly wrapping to the first thread. However, if currentThread were negative (say −1 due to a bug), then (−1 + 1) % N = 0 % N = 0, which happens to be fine, but (−2 + 1) % N = (−1) % N = −1, which is an invalid negative index. This would cause undefined behavior if used as an array index. The defensive approach is currentThread = ((currentThread + 1) % N + N) % N;, guaranteeing a non-negative result regardless of input corruption.

Question 5: CRITICAL THINKING

Prove that the Euclidean GCD algorithm gcd(a, b) = gcd(b, a % b) terminates for all positive integers a, b. Then implement it in C++ using a while loop and the % operator, and analyze the time complexity in terms of the number of digits in the smaller input.

Show answer

Termination proof: At each step, the second argument strictly decreases because 0 ≤ a % b < b (for positive b). A strictly decreasing sequence of non-negative integers must reach 0 in finitely many steps. When b reaches 0, gcd(a, 0) = a, and the algorithm halts. Implementation: int gcd(int a, int b) { while (b != 0) { int t = b; b = a % b; a = t; } return a; }. By Lamé's theorem, the number of steps is at most 5 times the number of decimal digits in the smaller input, giving O(log(min(a, b))) divisions. Since each % operation on fixed-width integers is O(1) on hardware, the total complexity is O(log(min(a, b))). For arbitrary-precision integers, each division costs O(n) where n is the number of digits, making the total O(n²).

SUMMARY

Lesson Summary

Summary

The C++ modulus operator (%) computes the remainder of integer division, governed by the fundamental invariant a == (a/b)*b + a%b. Since C++11, integer division truncates toward zero, which means the remainder carries the sign of the dividend. This is critical for handling negative operands correctly: -7 % 3 == -1, not 2. The operator works only with integral types; use std::fmod() for floating-point remainders.

Key idioms include parity checking (n % 2 != 0), circular index wrapping (i % size), digit extraction (n % 10), hash bucket assignment, and the Euclidean modulus pattern ((a % b) + b) % b for guaranteeing non-negative results. Always guard against division by zero (undefined behavior) and be cautious with signed/unsigned mixing. Mastering these fundamentals prepares you for advanced topics like modular exponentiation, the Euclidean GCD algorithm, and cryptographic protocols.