The Irrationality of sqrt(2): The Pythagoreans' Crisis

Terminology

Term	Definition
Rational number	A number expressible as $\frac{a}{b}$ where $a, b$ are integers and $b \neq 0$; the set of rationals is $\mathbb{Q}$
Irrational number	A real number that cannot be expressed as a ratio of two integers; its decimal expansion is infinite and non-repeating
Lowest terms	A fraction $\frac{a}{b}$ is in lowest terms if $\gcd(a, b) = 1$, meaning $a$ and $b$ share no common factor other than 1
GCD (greatest common divisor)	The largest positive integer that divides both $a$ and $b$; computed efficiently by the Euclidean algorithm
Proof by contradiction	Assume the negation of what you want to prove, then derive a logical impossibility
Parity	Whether an integer is even or odd; even numbers are divisible by 2, odd numbers are not
Dense set	A set $S$ is dense in $\mathbb{R}$ if between any two real numbers there exists an element of $S$; both $\mathbb{Q}$ and the irrationals are dense
Completeness (of $\mathbb{R}$)	The property that every bounded increasing sequence of reals converges to a real number; $\mathbb{Q}$ lacks this property
Algebraic number	A number that is a root of a polynomial with integer coefficients; $\sqrt{2}$ is algebraic (root of $x^2 - 2 = 0$)

What & Why

The ancient Pythagoreans believed that all quantities could be expressed as ratios of whole numbers. Their worldview was shattered when someone (tradition credits Hippasus of Metapontum) proved that $\sqrt{2}$ , the diagonal of a unit square, cannot be written as a fraction. Legend says Hippasus was drowned at sea for revealing this disturbing truth.

The proof that $\sqrt{2}$ is irrational is one of the most elegant arguments in mathematics. It uses proof by contradiction and a simple parity argument: if $\sqrt{2}$ were rational, both the numerator and denominator of its fraction would have to be even, contradicting the assumption that the fraction is in lowest terms.

This result matters because it reveals that the rational numbers, despite being dense on the number line (between any two rationals there is another rational), have "gaps." The real number line is not just rationals: it is filled with irrationals that cannot be captured by any fraction. This insight is foundational for calculus, real analysis, and the theory of computation (where the distinction between countable rationals and uncountable reals has deep consequences).

How It Works

The Classic Proof

Assume, for contradiction, that $\sqrt{2}$ is rational. Then we can write:

$\sqrt{2} = \frac{a}{b}$

where $a$ and $b$ are positive integers with no common factor (the fraction is in lowest terms, so $\gcd(a, b) = 1$ ).

Squaring both sides:

$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$

Since $a^2 = 2b^2$ , we know $a^2$ is even. But the square of an odd number is odd ( $(2k+1)^2 = 4k^2 + 4k + 1$ ), so $a$ must be even. Write $a = 2c$ for some integer $c$ .

Substituting: $(2c)^2 = 2b^2 \implies 4c^2 = 2b^2 \implies b^2 = 2c^2$

Now $b^2$ is even, so $b$ must also be even.

But if both $a$ and $b$ are even, they share the common factor 2. This contradicts our assumption that $\gcd(a, b) = 1$ . Therefore, $\sqrt{2}$ cannot be rational.

Geometric Interpretation

Consider a unit square (side length 1). By the Pythagorean theorem, the diagonal has length $\sqrt{1^2 + 1^2} = \sqrt{2}$ . The irrationality of $\sqrt{2}$ means the diagonal and the side of a square are incommensurable: no unit of length, no matter how small, can measure both exactly. This was the geometric fact that horrified the Pythagoreans.

Generalization

The same proof technique shows that $\sqrt{p}$ is irrational for any prime $p$ . More generally, $\sqrt{n}$ is irrational whenever $n$ is not a perfect square. The argument extends: if $\sqrt{n} = \frac{a}{b}$ in lowest terms, then $a^2 = nb^2$ , and the prime factorization of $a^2$ has even exponents while $nb^2$ has at least one odd exponent (from the non-square factor of $n$ ), giving a contradiction.

Complexity Analysis

Operation	Complexity	Notes
GCD via Euclidean algorithm	$O(\log(\min(a,b)))$	Used to reduce fractions to lowest terms
Rational approximation of $\sqrt{2}$	$O(n)$ digits via Newton's method	Converges quadratically: digits double each iteration
Continued fraction of $\sqrt{2}$	$[1; 2, 2, 2, \ldots]$	Periodic, giving best rational approximations
Perfect square test	$O(\log n)$	Integer square root plus verification

The best rational approximations to $\sqrt{2}$ come from its continued fraction. The $n$ -th convergent $\frac{p_n}{q_n}$ satisfies:

$\left|\sqrt{2} - \frac{p_n}{q_n}\right| < \frac{1}{q_n^2}$

The first few convergents are $\frac{1}{1}, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}$ , each getting closer to $\sqrt{2} \approx 1.41421356\ldots$

Implementation

ALGORITHM ProveIrrationalBySqrt(n)
INPUT: n: a positive integer
OUTPUT: "IRRATIONAL" if sqrt(n) is irrational, "RATIONAL" if it is a perfect square
BEGIN
  root <- FLOOR(SQRT(n))
  IF root * root = n THEN
    RETURN "RATIONAL"  // sqrt(n) = root, an integer
  ELSE
    RETURN "IRRATIONAL"
    // Proof: if sqrt(n) = a/b in lowest terms, then a^2 = n*b^2.
    // Since n is not a perfect square, its prime factorization has
    // an odd exponent. But a^2 has all even exponents. Contradiction.
  END IF
END

ALGORITHM NewtonSqrt(n, precision)
INPUT: n: number to take square root of, precision: desired decimal digits
OUTPUT: rational approximation of sqrt(n)
BEGIN
  x <- n / 2.0  // initial guess

  FOR i FROM 1 TO precision DO
    x <- (x + n / x) / 2  // Newton's iteration: x_{k+1} = (x_k + n/x_k) / 2
  END FOR

  RETURN x
END

ALGORITHM ContinuedFractionSqrt2(terms)
INPUT: terms: number of convergents to compute
OUTPUT: list of rational approximations (convergents) of sqrt(2)
BEGIN
  // sqrt(2) = [1; 2, 2, 2, ...]
  // Recurrence: p_n = a_n * p_{n-1} + p_{n-2}
  //             q_n = a_n * q_{n-1} + q_{n-2}
  convergents <- empty list
  p_prev2 <- 0
  p_prev1 <- 1
  q_prev2 <- 1
  q_prev1 <- 0

  // First term: a_0 = 1
  p <- 1 * p_prev1 + p_prev2  // p = 1
  q <- 1 * q_prev1 + q_prev2  // q = 1
  APPEND (p, q) TO convergents
  p_prev2 <- p_prev1
  p_prev1 <- p
  q_prev2 <- q_prev1
  q_prev1 <- q

  // Remaining terms: a_n = 2 for all n >= 1
  FOR i FROM 1 TO terms - 1 DO
    p <- 2 * p_prev1 + p_prev2
    q <- 2 * q_prev1 + q_prev2
    APPEND (p, q) TO convergents
    p_prev2 <- p_prev1
    p_prev1 <- p
    q_prev2 <- q_prev1
    q_prev1 <- q
  END FOR

  RETURN convergents
END

Real-World Applications

Floating-point arithmetic in computers represents numbers as rationals (with power-of-2 denominators), so irrational numbers like $\sqrt{2}$ are always approximated, leading to rounding errors that accumulate in numerical computation
The irrationality of $\sqrt{2}$ means that pixel grids cannot perfectly represent 45-degree diagonals, which is why anti-aliasing algorithms exist in computer graphics
Continued fraction representations of irrationals provide the best rational approximations, used in calendar design (leap year rules approximate the irrational ratio of Earth's orbital period to its rotation)
In cryptography, the distinction between algebraic irrationals (like $\sqrt{2}$) and transcendental numbers (like $\pi$ and $e$) matters for certain number-theoretic constructions
Paper sizes in the ISO 216 standard (A4, A3, etc.) use the aspect ratio $1:\sqrt{2}$ so that cutting a sheet in half preserves the ratio, an elegant application of this irrational number
The proof technique (infinite descent via parity) appears throughout computer science in correctness proofs for algorithms involving even/odd invariants

Key Takeaways

The proof that $\sqrt{2}$ is irrational uses contradiction: assuming $\sqrt{2} = \frac{a}{b}$ in lowest terms leads to both $a$ and $b$ being even, contradicting the lowest-terms assumption
This discovery shattered the Pythagorean belief that all quantities are ratios of whole numbers, revealing that the number line contains "gaps" that rationals cannot fill
The same technique proves $\sqrt{p}$ is irrational for any prime $p$, and $\sqrt{n}$ is irrational whenever $n$ is not a perfect square
Despite being dense (between any two rationals lies another rational), the rationals are incomplete: sequences of rationals can converge to irrational limits
Continued fractions provide the best rational approximations to irrationals, with convergents satisfying $|\sqrt{2} - p_n/q_n| < 1/q_n^2$
The proof is a masterclass in proof by contradiction, one of the most important techniques in mathematics and theoretical computer science