Lesson 23 · Core algorithms

Modular Arithmetic

Modular arithmetic works with congruence classes, preserving addition and multiplication while making division conditional on an inverse.

Congruence classes

Integers a and b are congruent modulo m when m divides a−b. They represent the same residue class. Addition, subtraction, and multiplication preserve congruence, allowing reduction after each operation instead of constructing huge intermediate results.

Use a positive modulus and normalize ((x%m)+m)%m when the language can return negative remainders. A canonical [0,m) representation makes equality and array indexing reliable.

Congruence means equal remainder class
Reduce during computation
Canonical residues avoid sign bugs

Addition, multiplication, and overflow

(a+b) mod m and (a·b) mod m may reduce operands first. Mathematical equivalence does not prevent fixed-width overflow before the remainder is applied; use a wider product, big integers, or overflow-safe multiplication.

Subtraction needs normalization after reducing. Modulus one has a single residue zero, so even the multiplicative identity 1 becomes zero modulo one.

Reduce operands first
Machine overflow is separate from mathematics
Modulus one is a boundary case

Key reference

Terms, operations, and practical uses

Congruence

ResidueResidue is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
NormalizationNormalization is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
ModulusModulus is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Operations

Modular powerModular power is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Multiplicative inverseMultiplicative inverse is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Extended EuclidExtended Euclid is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Preconditions

CoprimalityCoprimality is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Prime modulusPrime modulus is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Overflow-safe productOverflow-safe product is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Extended Euclid finds a modular inverse

def egcd(a,b):
    if b==0:return a,1,0
    g,x,y=egcd(b,a%b)
    return g,y,x-(a//b)*y
g,x,_=egcd(3,11)
print("Inverse:",x%11 if g==1 else None)

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
tuple<long long,long long,long long> egcd(long long a,long long b) {
    if(!b) return {a,1,0};
    auto [g,x,y]=egcd(b,a%b);
    return {g,y,x-a/b*y};
}
int main() {
    auto [g,x,y]=egcd(3,11);
    cout << "Inverse: " << (x%11+11)%11 << '\n';
}

class Main {
    static long[] egcd(long a,long b) {
        if(b==0) return new long[]{a,1,0};
        long[] q=egcd(b,a%b);
        return new long[]{q[0],q[2],q[1]-a/b*q[2]};
    }
    public static void main(String[] args) {
        long x=egcd(3,11)[1];
        System.out.println("Inverse: "+((x%11+11)%11));
    }
}

Watch it run

Step through it

Running on inverse of 3 modulo 11

Output

Inverses and division

A multiplicative inverse x satisfies ax≡1 mod m and exists exactly when gcd(a,m)=1. Extended Euclid finds it for any coprime pair. For prime m and nonzero a, Fermat gives a^(m−2) mod m.

Modular division a/b means a·b⁻¹ and has no value when the inverse does not exist. Ordinary integer division before taking a remainder is generally wrong.

Inverse existence requires gcd=1
Extended Euclid handles composite moduli
Never divide residues directly

Exponentiation and negative powers

Binary exponentiation squares the base and consumes exponent bits, requiring O(log e) multiplications. Reduce after every multiplication. Exponent zero returns 1 mod m.

A negative exponent is meaningful only when the base is invertible: compute the inverse then raise it to the absolute exponent. State whether the API supports this rather than silently looping on a negative integer.

Square while halving the exponent
Zero exponent returns the identity
Negative powers require an inverse

Testing algebraic contracts

Test negative operands, zero, modulus one, noninvertible divisors, large products, and exponent zero. Verify inverse results by multiplication rather than trusting a returned coefficient.

When factorial formulas use modular division, ensure the modulus and denominator meet inverse conditions. Prime-modulus shortcuts cannot be copied into arbitrary composite-modulus problems.

Check inverse by multiplication
Prime assumptions must be explicit
Test numeric limits

Reusable implementation contracts

Provide small functions for normalize, add, subtract, multiply, power, inverse, and divide rather than scattering remainder expressions. Each function should state modulus restrictions and numeric range. This centralizes negative handling and overflow protection.

For repeated inverse queries under a fixed prime, precompute factorial and inverse-factorial tables or linear inverses as appropriate. For arbitrary composite moduli, factorization and the Chinese remainder theorem may be necessary. Do not let a convenient prime-modulus helper silently accept unsupported input.

Congruence supports equality reasoning but does not preserve ordinary ordering; residues cannot be compared to decide which original integer was larger. Similarly, reducing an exponent modulo m is generally invalid—the correct cycle often depends on Euler or Carmichael conditions and coprimality.

The extended Euclidean identity ax+my=gcd(a,m) explains inverse existence: reducing both sides modulo m yields ax≡1 precisely when the gcd is one. This causal proof is safer than memorizing that inverses sometimes fail. Normalize after subtraction because many languages preserve a negative remainder, and reduce multiplication before values exceed the numeric type. For unsigned fixed-width arithmetic, even two valid residues can overflow before the remainder operation. Test identities such as (a+b) mod m and a·inverse(a) mod m across random coprime inputs, then include noncoprime pairs to ensure division is rejected rather than fabricated. Treat the modulus as a validated positive API parameter. Document whether zero modulus throws an error or is rejected before the function call.

Centralize normalization
Expose modulus assumptions
Composite moduli need different tools