Engineering Fluency OS

Why This Matters

Every time you use HTTPS, send an encrypted message, or verify a digital signature, divisibility and prime factorization are working behind the scenes. RSA encryption relies on the fact that multiplying two large primes is easy, but factoring their product is computationally infeasible. The Euclidean algorithm — over 2,300 years old — is still one of the most important algorithms in computing because it efficiently finds the greatest common divisor (GCD) of two numbers.

Number theory is the backbone of cryptography, hash functions, error-correcting codes, and random number generation. Understanding divisibility lets you reason about when loops terminate, how hash tables distribute keys, and why certain data structures work. The Euclidean algorithm is a masterclass in efficiency: it reduces a problem exponentially fast, running in O(log(min(a,b))) time.

Define Terms

Visual Model

Divisibilitya divides b if b mod a = 0

Prime NumbersOnly divisible by 1 and itself

Prime Factorization60 = 2^2 * 3 * 5

GCDGreatest Common Divisor

Euclidean Algorithmgcd(a,b) = gcd(b, a mod b)

Extended EuclideanFind x,y: ax + by = gcd(a,b)

CryptographyRSA, Diffie-Hellman

The full process at a glance. Click Start tour to walk through each step.

Number theory flows from divisibility to primes to GCD to cryptography. The Euclidean algorithm is the key computational tool.

Code Example

Code

// Divisibility check
function divides(a, b) {
  return b % a === 0;
}
console.log("3 | 12:", divides(3, 12)); // true
console.log("3 | 10:", divides(3, 10)); // false

// Prime check
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}
console.log("17 is prime:", isPrime(17)); // true
console.log("15 is prime:", isPrime(15)); // false

// Prime factorization
function primeFactors(n) {
  const factors = [];
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.push(d);
      n /= d;
    }
  }
  if (n > 1) factors.push(n);
  return factors;
}
console.log("Factors of 60:", primeFactors(60)); // [2, 2, 3, 5]
console.log("Factors of 84:", primeFactors(84)); // [2, 2, 3, 7]

// Euclidean algorithm for GCD
function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}
console.log("gcd(48, 18):", gcd(48, 18)); // 6
console.log("gcd(100, 75):", gcd(100, 75)); // 25

// Extended Euclidean: returns [gcd, x, y] where ax + by = gcd
function extGcd(a, b) {
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extGcd(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}
const [g, x, y] = extGcd(48, 18);
console.log(`gcd(48,18) = ${g}, x=${x}, y=${y}`); // 6, x=-1, y=3
console.log(`Verify: 48*${x} + 18*${y} = ${48*x + 18*y}`); // 6

Interactive Experiment

Try these exercises:

Find the prime factorization of 2520. How many prime factors does it have?
Trace the Euclidean algorithm by hand for gcd(252, 198). How many steps does it take?
Verify that for any two numbers a and b, gcd(a,b) * lcm(a,b) = a * b.
Use the extended Euclidean algorithm to find x and y such that 35x + 15y = gcd(35, 15).
Find all primes less than 100 using the Sieve of Eratosthenes. How many are there?

Quick Quiz

Coding Challenge

Extended Euclidean Algorithm

Write a function called `extendedGcd` that takes two positive integers a and b, and returns an array of three values [gcd, x, y] such that a*x + b*y = gcd(a, b). This is the Bezout identity. Use the recursive extended Euclidean algorithm: if b is 0, return [a, 1, 0]. Otherwise, recursively compute extendedGcd(b, a % b), then adjust x and y.

Loading editor...

Real-World Usage

Number theory powers critical systems across computing:

RSA encryption: The most widely used public-key cryptosystem. It relies on the difficulty of factoring the product of two large primes and uses the extended Euclidean algorithm to compute decryption keys.
Hash functions: Hash tables use modular arithmetic (a direct application of divisibility) to map keys to buckets. Good hash functions distribute keys evenly.
Error-correcting codes: Reed-Solomon codes (used in QR codes, CDs, and deep-space communication) are built on polynomial arithmetic over finite fields, which depends on prime number theory.
Random number generation: Linear congruential generators use the formula x(n+1) = (a * x(n) + c) mod m. The choice of parameters requires number-theoretic analysis.
Blockchain: Elliptic curve cryptography, used in Bitcoin and Ethereum, is built on number theory over finite fields.

Number Theory