Prime Numbers and Number Theory

Definition: A prime number is an integer greater than 1 with no positive divisors other than 1 and itself; every other integer greater than 1 is composite, meaning it can be written as a product of smaller positive integers.

How It Works

• Every integer greater than 1 falls into exactly one of two categories: prime (only 1 and itself divide it evenly) or composite (some smaller integer greater than 1 also divides it evenly).
• 1 is neither prime nor composite by definition: it has exactly one positive divisor (itself), not the two required to be prime, so it sits outside the classification entirely.
• 2 is the only even prime. Every other even number is automatically divisible by 2 in addition to 1 and itself, which makes it composite by definition.
• The Sieve of Eratosthenes finds every prime up to some limit N by elimination rather than by testing each number individually: starting from 2, mark each not-yet-eliminated number as prime, then cross out every multiple of it, and move to the next unmarked number.
• Every number the sieve reaches that hasn’t already been crossed out must be prime, because any smaller prime factor it had would already have eliminated it earlier in the process.
• The Fundamental Theorem of Arithmetic states that every integer greater than 1 has exactly one prime factorization, up to the order the factors are written in: 60 is 2×2×3×5, and no other combination of primes multiplies to 60.
• That uniqueness is what makes primes act like the “atoms” of the integers: any two factorizations of the same number must use identical primes the identical number of times, so a factorization can be treated as a fixed fingerprint rather than one of several possible answers.
• The greatest common divisor (GCD) of two integers is the largest integer that divides both of them evenly; the least common multiple (LCM) is the smallest positive integer that both of them divide into evenly.
• GCD and LCM are linked by a fixed identity, GCD(a, b) × LCM(a, b) = a × b, so once two numbers and either their GCD or their LCM are known, the other is a single division away.
• The Euclidean algorithm computes GCD without factoring anything: repeatedly replace the larger of two numbers with the remainder left after dividing it by the smaller, and repeat until the remainder is 0 — the last nonzero remainder is the GCD.
• Primes never run out. Euclid proved over two thousand years ago, with a short proof by contradiction, that no finite list could ever contain every prime (see Under the Hood), a fact that millennia later underpins the large primes used in modern cryptography.

Illustration

Primes up to N: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

var nIn = document.getElementById(‘prime-n’); var nOut = document.getElementById(‘prime-n-out’); var resetBtn = document.getElementById(‘prime-reset’);

function fmt(n) { return String(Math.round(n)); }

// A real Sieve of Eratosthenes, run fresh on every call. State codes: // 0 = unused (index 0), 1 = prime, 2 = composite, 3 = the number 1 // (neither prime nor composite). function sieve(N) { var state = []; for (var k = 0; k <= N; k++) { state[k] = 0; } state[1] = 3; var primes = []; for (var i = 2; i <= N; i++) { if (state[i] !== 2) { state[i] = 1; primes.push(i); for (var j = i * 2; j <= N; j += i) { state[j] = 2; } } } return { state: state, primes: primes }; }

function update() { var N = parseInt(nIn.value, 10); nOut.textContent = fmt(N);

var result = sieve(N);
var state = result.state;
var primes = result.primes;

// Rebuild the grid from scratch every time, since N changes both the
// cell count and the number of rows.
while (gridGroup.firstChild) {
  gridGroup.removeChild(gridGroup.firstChild);
}

var rows = Math.ceil(N / cols);
var gridWidth = cols * cellSize + (cols - 1) * cellGap;
var gridLeft = (420 - gridWidth) / 2;

for (var n = 1; n <= N; n++) {
  var idx = n - 1;
  var row = Math.floor(idx / cols);
  var col = idx % cols;
  var x = gridLeft + col * (cellSize + cellGap);
  var y = marginTop + row * (cellSize + cellGap);

  var fill, stroke, textFill;
  if (state[n] === 3) {
    fill = 'var(--brass-soft)'; stroke = 'var(--brass)'; textFill = 'var(--ink)';
  } else if (state[n] === 1) {
    fill = 'var(--accent)'; stroke = 'var(--accent-strong)'; textFill = 'var(--accent-ink)';
  } else {
    fill = 'var(--bg-inset)'; stroke = 'var(--border)'; textFill = 'var(--ink-faint)';
  }

  var rect = document.createElementNS(svgNS, 'rect');
  rect.setAttribute('x', x);
  rect.setAttribute('y', y);
  rect.setAttribute('width', cellSize);
  rect.setAttribute('height', cellSize);
  rect.setAttribute('rx', 3);
  rect.setAttribute('fill', fill);
  rect.setAttribute('stroke', stroke);
  rect.setAttribute('stroke-width', '1');
  gridGroup.appendChild(rect);

  var text = document.createElementNS(svgNS, 'text');
  text.setAttribute('x', x + cellSize / 2);
  text.setAttribute('y', y + cellSize / 2 + 4);
  text.setAttribute('text-anchor', 'middle');
  text.setAttribute('font-size', '11.5');
  text.setAttribute('font-family', 'var(--font-mono)');
  text.setAttribute('fill', textFill);
  text.textContent = String(n);
  gridGroup.appendChild(text);
}

var gridHeight = rows * cellSize + (rows - 1) * cellGap;
svg.setAttribute('viewBox', '0 0 420 ' + (marginTop + gridHeight + marginBottom));

titleTxt.textContent = 'N = ' + fmt(N);
countTxt.textContent = primes.length + ' primes found up to ' + fmt(N);
listSpan.textContent = primes.join(', ');

}

nIn.addEventListener(‘input’, update); resetBtn.addEventListener(‘click’, function () { nIn.value = 50; update(); });

update(); })();

Under the Hood

Euclid’s proof that there are infinitely many primes (Elements, Book IX), stated precisely as a proof by contradiction:

Claim: There are infinitely many primes.

Proof (by contradiction):
Suppose, for contradiction, that there are only finitely many
primes in total: p1, p2, ..., pn (a complete list of every
prime that exists).

Let N = (p1 × p2 × ... × pn) + 1.

Dividing N by any pi on the list leaves remainder 1, since
p1×p2×...×pn is exactly divisible by pi and N is exactly one
more than that product. So no pi on the list divides N evenly.

Now consider N itself:
  - If N is prime, N is a prime number not on the original
    list (it is larger than every pi on it), contradicting the
    assumption that p1, ..., pn was a complete list of every
    prime.
  - If N is composite, then by the Fundamental Theorem of
    Arithmetic it has some prime factor q. Since no pi on the
    list divides N, q cannot be any of p1, ..., pn — so q is a
    prime not on the original list, again contradicting
    completeness.

Either way, the assumed list fails to contain every prime.
Since this contradiction follows no matter how the list
p1, ..., pn was chosen, no finite list of primes can ever be
complete.

Therefore, there are infinitely many primes. ∎

• The argument never depended on which primes were in the assumed list or how many there were, which is exactly why it rules out a largest prime existing at all, not just that one particular list happened to be incomplete.

Worked Example 1: Prime factorization. Given: find the prime factorization of 60. Step 1: 60 is even, so divide by the smallest prime, 2: 60 = 2 × 30. Step 2: 30 is also even: 30 = 2 × 15. Step 3: 15 is not even; divide by the next prime, 3: 15 = 3 × 5. Step 4: 5 is itself prime, so factoring stops here. Answer: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5.

Worked Example 2: GCD via the Euclidean algorithm. Given: find GCD(252, 105). Step 1: 252 ÷ 105 = 2 remainder 42, so 252 = 2×105 + 42. Step 2: 105 ÷ 42 = 2 remainder 21, so 105 = 2×42 + 21. Step 3: 42 ÷ 21 = 2 remainder 0, so 42 = 2×21 + 0. Answer: the last nonzero remainder is 21, so GCD(252, 105) = 21.

Worked Example 3: LCM using GCD × LCM = a × b. Given: find LCM(252, 105), reusing the GCD (21) found above. Step 1: solve the identity for LCM: LCM(a, b) = (a × b) / GCD(a, b). Step 2: LCM(252, 105) = (252 × 105) / 21 = 26460 / 21. Answer: LCM(252, 105) = 1260.

History

• Euclid’s Elements (Book IX, Proposition 20, c. 300 BCE) contains the proof that there are infinitely many primes, one of the oldest surviving proofs by contradiction in all of mathematics.
• Eratosthenes of Cyrene (c. 240 BCE), chief librarian at Alexandria, is credited with the sieve that bears his name; the elimination method he described is still taught essentially unchanged today.
• The Euclidean algorithm for computing GCD also comes from Euclid’s Elements (Book VII), making it one of the oldest algorithms still in common practical use, well over two thousand years later.
• For most of their history, primes were studied purely for their own sake with no known practical application, a rare and long-lived example of “pure” mathematics pursued for its own interest.
• The search for ever-larger known primes became a large-scale computing effort in the 20th and 21st centuries: the Great Internet Mersenne Prime Search (GIMPS), a distributed-computing project launched in 1996, has found every record-largest known prime since, each a Mersenne prime of the form 2^p - 1.
• Since the 1970s, RSA public-key cryptography has relied on the practical difficulty of factoring the product of two large primes, turning number theory almost overnight from an abstract pursuit into the backbone of digital security.

Why It Matters

• RSA public-key cryptography, which secures the majority of the internet’s HTTPS traffic, relies directly on the practical difficulty of factoring the product of two very large primes.
• Simplifying a fraction to lowest terms is just dividing its numerator and denominator by their GCD, done constantly in arithmetic, spreadsheets, and unit conversions alike.
• Scheduling and timing problems, like “two repeating events happen every 4 days and every 6 days, when do they next coincide,” are solved directly using LCM.
• Hash table sizing in computer science often deliberately uses a prime number of buckets, since it reduces collisions and spreads keys more evenly than an arbitrary table size would.
• Primality testing, deciding whether a given number is prime, is a foundational algorithms topic in its own right, with efficient tests underpinning both cryptography and computational number theory.
• Error-detecting and error-correcting codes lean on properties of prime numbers and modular arithmetic to catch corrupted data during transmission or storage.

Common Pitfalls

• Treating 1 as prime. It is explicitly excluded by definition, since a prime must have exactly two distinct positive divisors, and 1 has only one.
• Assuming a number is prime just because it’s odd. Plenty of odd numbers are composite, like 9, 15, 21, and 25; being odd only rules out divisibility by 2, not by everything else.
• Forgetting that 2 is the only even prime, and mistakenly skipping it while scanning only odd candidates for primality.
• Confusing GCD and LCM, or mixing up which is which: the GCD of two numbers is always less than or equal to both of them, while the LCM is always greater than or equal to both of them.
• Stopping a prime factorization too early, leaving a composite number sitting in the answer instead of continuing to break it down until every factor is prime.
• Assuming the Euclidean algorithm requires factoring the numbers first. It doesn’t, and that’s precisely what makes it fast: it only ever divides and keeps the remainder.

Comparison

Quantity	Represents	Relative to a and b	Example: a = 12, b = 18
GCD(a, b)	Largest integer dividing both evenly	Always ≤ both a and b	GCD(12, 18) = 6
LCM(a, b)	Smallest positive integer both divide into evenly	Always ≥ both a and b	LCM(12, 18) = 36

Check: GCD × LCM = 6 × 36 = 216, and a × b = 12 × 18 = 216 — the identity holds.

FAQ

How do we know there isn’t a biggest prime? Euclid’s proof (see Under the Hood) shows that assuming a largest prime, or any complete finite list of primes, always leads to a contradiction: multiplying every prime on the list together and adding 1 produces a number that needs a prime factor missing from that list. Since the argument works no matter how the list was chosen, no finite list — and therefore no single “biggest prime” — can ever exist.

Why does the Euclidean algorithm actually work? Because of a simple fact: if a = bq + r, then GCD(a, b) = GCD(b, r). Any number dividing both a and b must also divide r (since r = a - bq), and any number dividing both b and r must also divide a. So the pairs (a, b) and (b, r) always share the exact same common divisors, including the greatest one, and each step shrinks the numbers until the remainder hits 0.

Is testing every number for primality practical for the huge numbers used in cryptography? Not by simple trial division. The sieve above is efficient for finding all primes up to a moderate limit, but cryptographic primes are hundreds of digits long, far beyond what trial division or a sieve could check in any reasonable time; specialized probabilistic primality tests are used instead.

Example

Every time a browser opens an HTTPS connection, it relies on a pair of large prime numbers chosen specifically because multiplying them together is fast, while factoring the result back into those two primes is, with current algorithms and hardware, computationally infeasible for numbers hundreds of digits long. That asymmetry, easy to build and hard to break, is what turns the humble prime number, first proven inexhaustible by Euclid over two thousand years ago, into the mathematical backbone of modern digital security.

Related Terms

• Complex Numbers
• Modular Arithmetic