15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Modular arithmetic keeps only the remainder after dividing by a modulus m. Two numbers are congruent mod m when m divides their difference. Addition, subtraction and multiplication work on the reduced values, and each result is normalized into 0 through m - 1. Ordinary division is not a general modular operation.
| Congruence | a ≡ b (mod m) when m divides a - b, so 7 ≡ 2 (mod 5) |
|---|---|
| Add, subtract, multiply | Reduce each operand, combine, reduce again |
| Canonical residue | ((x % m) + m) % m, always in 0 through m - 1 |
| Division | No general rule; do not reduce an ordinary quotient |
| Cost | O(1) for a fixed expression, O(k) for k values, O(1) extra space |
The lesson assumes you can work with positive divisors from gcd and lcm.
A modulus is a positive integer . Modulo , we keep only the remainder class of an integer.
For , the canonical residue of is the one value such that:
and differs from by a multiple of .
We write:
when divides . For example:
because:
and divides .
A language’s remainder operator may return a negative result for a negative dividend. The algorithm always returns the mathematical, canonical residue in the range through .
Repeated reduction also applies in larger modular computations such as modular exponentiation: reduce intermediate values instead of carrying an unreduced expression further than necessary.
Evaluate:
The modulus is:
Before doing multiplication or subtraction, reduce each input into the canonical range through .
| Original value | Reduction | Canonical residue |
|---|---|---|
The smaller equivalent expression is:
Each replacement is valid because the original value is congruent to its residue modulo :
Start with the reduced inputs:
Reduce inputs, multiply, reduce, subtract: 1 − 3 lands at −2, left of zero. Adding the modulus 5 once wraps it into the canonical range 0 to 4, giving 3.
Reduce again:
The accumulator for the product is now .
| Step | Current expression | Value before reduction | Canonical residue |
|---|---|---|---|
| Multiply |
Now subtract :
The value is congruent to the answer, but it is not in the required canonical range through .
| Step | Current expression | Value before normalization |
|---|---|---|
| Subtract |
Add the modulus once, then reduce:
So:
| Step | Accumulator before normalization | Normalized accumulator |
|---|---|---|
| Final reduction |
The ordered calculation is:
Each time we reduce an intermediate value, two facts remain true:
The invariant is:
After every reduction, the current accumulator is congruent to the expression processed so far modulo and is stored in the range through .
For the example:
The arithmetic rules that preserve congruence are:
For a canonical subtraction result, use:
And for multiplication:
Division does not belong in these general rules. Ordinary integer division is not a general modular operation. No modular division is defined here.
We need two operations.
First, normalize one value. A normalization function must:
The normalization formula is:
The second operation evaluates:
Reduce each input first. Then multiply the first two residues and reduce. Then subtract the third residue and normalize the result.
For the board example, the sequence is:
For an expression with input values, reduce one value, combine it with the accumulator, then reduce the accumulator again.
% below means the language’s remainder operator. It may produce a negative remainder when its left operand is negative.
normalizeModx; positive integer mx modulo m, in the range 0 through m - 1m <= 01FUNCTION normalizeMod(x, m)
21. IF m <= 0
32. RAISE InvalidModulus
43. END IF
54.
65. remainder <- x % m
76. normalized <- (remainder + m) % m
87. RETURN normalized
9END FUNCTIONevaluateModProductDifferencea, b, and c; positive integer mmm <= 0 through normalizeMod1FUNCTION evaluateModProductDifference(a, b, c, m)
21. ra <- normalizeMod(a, m)
32. rb <- normalizeMod(b, m)
43. rc <- normalizeMod(c, m)
54.
65. productResidue <- normalizeMod(ra * rb, m)
76. answer <- normalizeMod(productResidue - rc, m)
87. RETURN answer
9END FUNCTIONUse the original example:
1a = 17
2b = 23
3c = 8
4m = 5Call:
1evaluateModProductDifference(17, 23, 8, 5)| Pseudocode line | State change |
|---|---|
| 1 | Call normalizeMod(17, 5). |
| 5 in helper | remainder <- 17 % 5 = 2 |
| 6 in helper | normalized <- (2 + 5) % 5 = 2 |
| 7 in helper | Return 2. Therefore, ra <- 2. |
| 2 | Call normalizeMod(23, 5). |
| 5 in helper | remainder <- 23 % 5 = 3 |
| 6 in helper | normalized <- (3 + 5) % 5 = 3 |
| 7 in helper | Return 3. Therefore, rb <- 3. |
| 3 | Call normalizeMod(8, 5). |
| 5 in helper | remainder <- 8 % 5 = 3 |
| 6 in helper | normalized <- (3 + 5) % 5 = 3 |
| 7 in helper | Return 3. Therefore, rc <- 3. |
| 5 | Compute ra * rb = 2 * 3 = 6. Call normalizeMod(6, 5). |
| 5 in helper | remainder <- 6 % 5 = 1 |
| 6 in helper | normalized <- (1 + 5) % 5 = 1 |
| 7 in helper | Return 1. Therefore, productResidue <- 1. |
| 6 | Compute productResidue - rc = 1 - 3 = -2. Call normalizeMod(-2, 5). |
| 5 in helper | remainder <- -2 % 5. In a language that keeps the dividend’s sign, this is -2. |
| 6 in helper | normalized <- (-2 + 5) % 5 = 3 |
| 7 in helper | Return 3. Therefore, answer <- 3. |
| 7 | Return 3. |
The final returned value is:
We show that evaluateModProductDifference(a, b, c, m) returns the canonical residue of:
provided that .
Let remainder be x % m.
The remainder differs from by a multiple of , so:
Adding does not change the congruence class:
The final % m chooses the canonical representative in the range:
There is exactly one representative of each congruence class in this range. If two values and in that range were congruent modulo , then would divide . But:
The only multiple of in that interval is . Therefore .
So normalizeMod(x, m) returns exactly one canonical residue congruent to .
Lines 1 through 3 compute:
Each of ra, rb, and rc is in the canonical range because normalizeMod guarantees that property.
At line 5:
and:
Multiplication preserves congruence, so:
Normalizing that product does not change its congruence class. Therefore:
and productResidue is canonical.
At line 6:
and:
Subtraction preserves congruence, so:
The final call to normalizeMod returns the unique canonical residue in this congruence class.
The function performs a fixed sequence of helper calls and arithmetic operations. There is no loop or recursion. After line 7, it returns the canonical residue congruent to:
Thus the algorithm is correct.
For the fixed expression:
the pseudocode performs:
That is a fixed number of arithmetic and remainder operations. Therefore it uses:
arithmetic steps.
For a longer expression with input values, reduce each value once and combine it with constant work per value. That gives:
time.
The fixed-expression pseudocode stores:
The pseudocode stores a constant number of values, so auxiliary space is:
A running-residue version for values also keeps only the modulus, the current input residue, and the accumulator, so it still uses auxiliary space.
Incorrect assumption:
1x % m is always the desired modular resultSmallest exposing input:
1x = -2
2m = 5In languages where % keeps the dividend’s sign:
1-2 % 5 = -2But is not in the canonical range through . The correct result is:
Correction:
1((x % m) + m) % mIncorrect line:
1answer <- (a % m - b % m) % mExposing input:
1a = 1
2b = 3
3m = 5Wrong intermediate state in languages with negative remainders:
1(1 - 3) % 5 = -2The required canonical result is:
Correction:
1answer <- ((a % m) - (b % m) + m) % mOr normalize the subtraction through the helper:
1answer <- normalizeMod(ra - rb, m)Incorrect operation:
1(1 / 2) mod 4An implementation might perform ordinary integer division first:
11 / 2 = 0and then assert that the modular result is .
That does not define general modular division. The lesson provides addition, subtraction, multiplication, congruence, and normalization only.
Correction: do not reduce an ordinary quotient as though modular division always works.
Incorrect line:
1remainder <- x % mwithout checking m.
Exposing input:
1x = 7
2m = 0Wrong outcome: a remainder operation with zero modulus causes a runtime error or invalid operation.
Correction:
1IF m <= 0
2 RAISE InvalidModulus
3END IF| Input | Required result |
|---|---|
normalizeMod(-2, 5) | 3 |
normalizeMod(29, 1) | 0 |
normalizeMod(0, 7) | 0 |
evaluateModProductDifference(17, 23, 8, 5) | 3 |
Any call with m = 0 | Reject as invalid |
Implement:
1normalizeMod(x, m)for , returning the canonical residue of x.
Then implement:
1evaluateModProductDifference(a, b, c, m)returning the canonical residue of:
Your implementation contract will be tested with:
1def normalize_mod(x, m):
2 if m <= 0:
3 raise ValueError("modulus must be positive")
4 remainder = x % m
5 return (remainder + m) % m # fixes a negative remainder in other languages
6
7def evaluate_mod_product_difference(a, b, c, m):
8 ra, rb, rc = normalize_mod(a, m), normalize_mod(b, m), normalize_mod(c, m)
9 product_residue = normalize_mod(ra * rb, m)
10 return normalize_mod(product_residue - rc, m)
11
12print("normalizeMod(-2, 5) =", normalize_mod(-2, 5))
13print("normalizeMod(29, 1) =", normalize_mod(29, 1))
14print("(17 * 23 - 8) mod 5 =", evaluate_mod_product_difference(17, 23, 8, 5))1public class Main {
2 static long normalizeMod(long x, long m) {
3 if (m <= 0) throw new IllegalArgumentException("modulus must be positive");
4 long remainder = x % m; // negative when x is negative
5 return (remainder + m) % m;
6 }
7
8 static long evaluateModProductDifference(long a, long b, long c, long m) {
9 long ra = normalizeMod(a, m), rb = normalizeMod(b, m), rc = normalizeMod(c, m);
10 long productResidue = normalizeMod(ra * rb, m);
11 return normalizeMod(productResidue - rc, m);
12 }
13
14 public static void main(String[] args) {
15 System.out.println("normalizeMod(-2, 5) = " + normalizeMod(-2, 5));
16 System.out.println("normalizeMod(29, 1) = " + normalizeMod(29, 1));
17 System.out.println("(17 * 23 - 8) mod 5 = " + evaluateModProductDifference(17, 23, 8, 5));
18 }
19}1#include <iostream>
2#include <stdexcept>
3using namespace std;
4
5long long normalizeMod(long long x, long long m) {
6 if (m <= 0) throw invalid_argument("modulus must be positive");
7 long long remainder = x % m; // negative when x is negative
8 return (remainder + m) % m;
9}
10
11long long evaluateModProductDifference(long long a, long long b, long long c, long long m) {
12 long long ra = normalizeMod(a, m), rb = normalizeMod(b, m), rc = normalizeMod(c, m);
13 long long productResidue = normalizeMod(ra * rb, m);
14 return normalizeMod(productResidue - rc, m);
15}
16
17int main() {
18 cout << "normalizeMod(-2, 5) = " << normalizeMod(-2, 5) << endl;
19 cout << "normalizeMod(29, 1) = " << normalizeMod(29, 1) << endl;
20 cout << "(17 * 23 - 8) mod 5 = " << evaluateModProductDifference(17, 23, 8, 5) << endl;
21}1function normalizeMod(x, m) {
2 if (m <= 0) throw new Error("modulus must be positive");
3 const remainder = x % m; // negative when x is negative
4 return (remainder + m) % m;
5}
6
7function evaluateModProductDifference(a, b, c, m) {
8 const ra = normalizeMod(a, m), rb = normalizeMod(b, m), rc = normalizeMod(c, m);
9 const productResidue = normalizeMod(ra * rb, m);
10 return normalizeMod(productResidue - rc, m);
11}
12
13console.log("normalizeMod(-2, 5) = " + normalizeMod(-2, 5));
14console.log("normalizeMod(29, 1) = " + normalizeMod(29, 1));
15console.log("(17 * 23 - 8) mod 5 = " + evaluateModProductDifference(17, 23, 8, 5));Both numbers are smaller than 4, so the quotient is 0 and the remainder is the number itself. 3 mod 4 is 3 and 2 mod 4 is 2.
Java, C++ and JavaScript keep the sign of the dividend, so -2 % 5 is -2. Python gives the result the sign of the modulus, which is 3. Writing ((x % m) + m) % m returns 3 in all of them.
Subtract the residues, add m, then reduce again. For 1 - 3 mod 5 the raw difference is -2, and (-2 + 5) mod 5 gives 3.
Answers can grow past the integer range, so each step is reduced. Residues below 10^9+7 multiply to under about 10^18, which fits in a 64-bit signed integer.
Not by plain integer division. 1 / 2 is 0 in integers, which says nothing about the residue mod 4. Modular division needs an inverse, which this lesson does not cover.