Part 5 · 1 chapters · ~8 min

Number Theory: Modular Arithmetic and Primes

Divisibility and remainders, modular arithmetic and congruences, Euclid's gcd and the extended algorithm, modular inverses, primes and unique factorisation, primality testing, fast modular exponentiation, Fermat's little theorem, and applications in hashing, check digits and cryptography.

Remainders, gcd, exponents, checks

code

const gcd = (a, b) => b ? gcd(b, a % b) : a;             // gcd(1071, 462) → 21
const modpow = (b, e, m) => { let r = 1n; b %= m;          // square-and-multiply on BigInt
  while (e > 0n) { if (e & 1n) r = r * b % m; b = b * b % m; e >>= 1n; } return r; };
modpow(3n, 200n, 1000003n)                                 // 333986n: 8 squarings, not 200 multiplications

// Luhn check digit (cards)
const luhn = s => [...s].reverse().map(Number)
  .reduce((a, d, i) => a + (i % 2 ? (d * 2 > 9 ? d * 2 - 9 : d * 2) : d), 0) % 10 === 0;
luhn('4111111111111111')   // true
luhn('4111111111111112')   // false: a single-digit error is always caught

// JavaScript's % is a remainder, not a modulus: -7 % 3 === -1. For bucket indexes use ((x % n) + n) % n

Fermat's little theorem: for a prime p and a not divisible by p, a^(p-1) ≡ 1 (mod p). It powers fast probabilistic primality tests (Miller-Rabin), which is how keys find large primes quickly.

NUMBER THEORY YOU USE DAILY

remainders, primes and divisors

swipe the figure sideways, or tap expand for full screen

1/5

remainders

hash(key) mod N picks a shard; i mod 3 cycles round robin; (h + 1) mod 24 wraps the clock.

clock arithmeticsharding, round robin