Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 37 · Modular Arithmetic and CRT

Modular Arithmetic in Practice

Implement square-and-multiply modular exponentiation, compute modular inverses and divisions, work with the usual 10^9+7 modulus, and use modular tricks safely in code.

Chapter 3 gave you the theory of congruences. This lesson turns it into code you can use: raising numbers to huge powers modulo n, dividing modulo n, and avoiding the traps that appear when you move between mathematics and programs. These routines are the engine room of cryptography, hashing, combinatorics and programming-contest solutions.

Fast modular exponentiation

Computing aᵉ mod n by multiplying a by itself e times needs e multiplications, which is impossible when e has hundreds of digits. Square-and-multiply uses the binary digits of e. Write e in binary; for each bit from the top, square the running result, and if the bit is 1, multiply by a. Always reduce mod n so numbers never exceed n².

For 3¹³ mod 7: 13 = 1101 in binary. Start with r = 1. Bit 1: r = 1² · 3 = 3. Bit 1: r = 3² · 3 = 27 ≡ 6. Bit 0: r = 6² = 36 ≡ 1. Bit 1: r = 1² · 3 = 3. So 3¹³ ≡ 3 (mod 7).

The number of multiplications is about 2·log₂(e): a 1000-bit exponent needs under 2000 modular multiplications.

Python Square and multiply

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same idea works for any associative operation, for example matrix powers (Fibonacci numbers mod n in logarithmic time) or powers of permutations.

Python Fibonacci mod n by matrix powers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modular inverses and division

You cannot divide in modular arithmetic, but you can multiply by an inverse. a / b mod n means a · b⁻¹ mod n, and it exists only when gcd(b, n) = 1. Python 3.8+ computes the inverse with pow(b, -1, n). For a prime modulus p, Fermat gives b⁻¹ ≡ b^(p−2).

Python Modular division

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the true quotient is an integer, the modular quotient equals it modulo n, and that is the case in the printout (6/3 = 2). If the true quotient is not an integer, the modular quotient is a "residue standing for the fraction", for example 10/4 = 5/2 is represented by a huge number.

Why 10⁹ + 7?

Programming problems often ask for answers "modulo 1,000,000,007". It is a prime (so every nonzero residue has an inverse), it fits comfortably in a 32-bit integer, and the product of two residues fits in a 64-bit integer. Those properties let a program reduce after each multiplication without overflow. Python has no overflow, but keeping numbers small is still faster.

Binomial coefficients mod a prime

Factorials with inverses give C(n, k) mod p quickly. Precompute n! for all n up to N and the inverse factorials.

Python n choose k modulo a prime

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Traps when moving from math to code

  • Negative remainders: in C, Java and JavaScript, % can be negative. Normalize with ((x % n) + n) % n. Python's % is already non-negative for a positive modulus.
  • Overflow: in a 64-bit language reduce after every multiplication; a·b can exceed 2⁶³ if both are near 10⁹ ... use 128-bit or a mulmod routine for larger moduli.
  • Reducing exponents: you may reduce the exponent modulo φ(n) only when the base is coprime to n (previous lesson).
  • Subtracting: a − b mod n must be written (a - b) % n in Python, or (a - b + n) % n elsewhere.
  • Equality: after reducing, compare residues, not original numbers.
flowchart TD
  A["Need a^e mod n"] --> B{"e small?"}
  B -->|Yes| C["Multiply directly, reduce each step"]
  B -->|No| D["Square-and-multiply on bits of e"]
  D --> E{"gcd(a, n) = 1 and e huge?"}
  E -->|Yes| F["Optionally reduce e mod phi(n) first"]
  E -->|No| G["Keep e; or split n with CRT"]

Choosing a method for modular exponentiation.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many squarings does square-and-multiply need for an exponent with 1000 bits?

    One squaring per bit, plus at most one multiplication per 1 bit.
  2. 2. What does a / b mean modulo n?

    Division is multiplication by the modular inverse.
  3. 3. For a prime p, which formula gives the inverse of a?

    By Fermat, a * a^(p-2) = a^(p-1) = 1 (mod p).
  4. 4. Which language trait causes bugs when porting % code from Python?

    C, Java and JavaScript truncate towards zero, so -7 % 5 is -2 there.

Summary

  • Square-and-multiply computes aᵉ mod n with about 2·log₂ e modular multiplications; Python's pow(a, e, n) does it for you.
  • The same doubling idea speeds up matrix powers and Fibonacci numbers mod n.
  • Division mod n is multiplication by an inverse: pow(b, -1, n) or b^(p−2) for a prime p.
  • 10⁹ + 7 is a popular prime modulus; factorials and inverse factorials give binomials mod p.
  • Watch for negative remainders, overflow and reducing exponents when the base is not coprime to the modulus.

Next: The Chinese Remainder Theorem