Math and number theory guide · 6/6

Real-world use

Number theory is not just for contests: it sits inside cryptography, hashing, random number generators and check digits. This chapter covers where it appears, the library functions to use, and the C++ and Java traps.

Public-key cryptography: RSA

RSA uses every tool in this guide. Pick primes p and q, set n = p × q and φ = (p - 1)(q - 1), choose e coprime to φ, and get d = e^(-1) mod φ from extended Euclid. Encryption c = m^e mod n and decryption m = c^d mod n are fast exponentiation. A toy example:

p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)   # 3233, 3120
e = 17
d = pow(e, -1, phi)                  # 2753

message = 65
cipher = pow(message, e, n)          # 2790
print(cipher, pow(cipher, d, n))     # 2790 65

Real RSA needs moduli of 2048 bits or more, secure padding (OAEP, PSS) and constant-time arithmetic, so never ship your own; use a vetted library such as OpenSSL. Diffie-Hellman and elliptic-curve cryptography also rest on modular exponentiation and inverses.

Other places it appears

Hashing: polynomial string hashes (Rabin-Karp) work modulo a large prime; some hash tables use a prime bucket count.
Random numbers: a linear congruential generator computes x = (a × x + c) mod m; its full-period conditions involve GCDs and prime factors.
Check digits: ISBN-10 uses mod 11 and the Luhn algorithm for card numbers uses mod 10.
Scheduling and screens: when cycles line up again (LCM), and aspect ratios (1920 × 1080 divided by GCD 120 is 16:9).
Counting: contests and interviews ask for huge answers modulo 10^9 + 7 or 998244353.

Standard libraries

Language	What it provides
Python	`math.gcd`, `math.lcm`, `math.isqrt`, `math.comb`, `pow(a, e, m)`, `pow(a, -1, m)`
C++	`std::gcd`, `std::lcm` (C++17, `numeric` header); write modular exponentiation yourself
Java	`Math.floorMod`, `Math.multiplyExact`, `BigInteger.gcd`, `modPow`, `modInverse`

Pitfall 1: multiplication overflow in C++ and Java

Python integers are unbounded, but C++ and Java int is 32 bits and long long/long is 64 bits. Two residues below 10^9 + 7 multiply to about 10^18, which fits only in 64 bits. The classic bug is widening after the multiplication, when the int product has already overflowed (undefined behavior in C++, silent wraparound in Java).

#include <cstdint>
#include <iostream>

const long long MOD = 1'000'000'007LL;

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // both below mod: fits in 64 bits
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// modulus near 10^18: multiply in 128 bits (GCC/Clang)
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
    return static_cast<uint64_t>(static_cast<unsigned __int128>(a) * b % m);
}

int main() {
    int a = 1'000'000'000, b = 1'000'000'000;
    long long wrong = a * b;              // overflows in int arithmetic first
    long long right = 1LL * a * b % MOD;  // widen to 64 bits before multiplying
    std::cout << right << ' ' << mod_pow(2, 1'000'000'000'000LL, MOD) << '\n';
    (void)wrong;
}

Pitfall 2: remainders of negative numbers

In Python -7 % 3 is 2; in C++ and Java it is -1. Normalize with ((x % m) + m) % m or Java's Math.floorMod, including the possibly negative x from extended Euclid.

import java.math.BigInteger;

public class ModPitfalls {
    public static void main(String[] args) {
        final long MOD = 1_000_000_007L;
        int a = 1_000_000_000, b = 1_000_000_000;
        long wrong = a * b;              // wrapped int product: -1486618624
        long right = (long) a * b % MOD; // 49
        System.out.println(wrong + " " + right);

        System.out.println(-7 % 3);               // -1
        System.out.println(Math.floorMod(-7, 3)); // 2

        BigInteger x = BigInteger.valueOf(3);
        BigInteger m = BigInteger.valueOf(MOD);
        System.out.println(x.modInverse(m));                        // 333333336
        System.out.println(x.modPow(BigInteger.valueOf(200), m)); // 136318165
    }
}

Pitfall 3: other common mistakes

Fermat's a^(p-2) is the inverse only when the modulus is prime. For a composite modulus use extended Euclid and check coprimality.
lcm(a, b) = a * b / gcd(a, b) overflows in the product first. Compute a / gcd(a, b) * b instead.
C++ pow and JavaScript Math.pow use floating point and lose precision on large integer powers; sqrt(n) does too, so write loop bounds as i * i <= n or use math.isqrt.
A sieve beyond about 10^8 entries strains memory; use a bit array or a segmented sieve.
JavaScript number is exact only up to 2^53, so multiply residues modulo 10^9 + 7 as BigInt (for example (999_999_999n * 999_999_999n) % 1_000_000_007n is 64n, while the number version gives 63).

Summary

RSA, hashing, random number generators and check digits all rest on modular arithmetic. Use the standard library first (gcd, pow, BigInteger); in your own code, check for multiplication overflow, negative remainders, non-prime moduli and floating-point powers. Never build cryptography yourself.