Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 37 · Diophantine Equations

Pythagorean Triples

Generate every primitive Pythagorean triple with Euclid's formula, see the tree structure, count triples, and meet Fermat's last theorem for n = 4.

The equation x² + y² = z² has been studied for four thousand years. A clay tablet from Babylon, Plimpton 322, lists triples such as (119, 120, 169). A Pythagorean triple is a set of positive integers (a, b, c) with a² + b² = c²: (3, 4, 5), (5, 12, 13), (8, 15, 17). They are the integer right triangles.

Unlike the linear case, we are no longer solving for a line of solutions but for a whole surface, and yet the answer is beautifully complete: every triple comes from one simple formula. This lesson proves it, generates triples in Python and shows how they form an infinite tree.

Primitive triples

If (a, b, c) is a triple, so is (ka, kb, kc). We call a triple primitive when gcd(a, b, c) = 1. In a primitive triple, a, b and c are pairwise coprime. Exactly one of a, b is even, and c is odd. (Squares are 0 or 1 modulo 4, and 0 + 0, 1 + 1 can't produce a square unless the sum is 1 modulo 4, so one leg is even and the other odd.)

Brute-force search shows the pattern first.

Python Brute-force search for triples

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should find sixteen primitive triples with hypotenuse up to 100, including (3, 4, 5), (20, 21, 29) and (65, 72, 97). Now let us explain them.

Euclid's formula

For integers m > n > 0, define

a = m² - n², b = 2mn, c = m² + n².

Then a² + b² = (m² - n²)² + 4m²n² = (m² + n²)² = c², so this is always a triple. It is primitive exactly when m and n are coprime and of opposite parity (one odd, one even). The remarkable converse: every primitive triple arises this way (up to swapping a and b).

Why? Take a primitive triple with b even. Then b² = (c - a)(c + a), both factors are even, and ((c-a)/2)·((c+a)/2) = (b/2)². The two halves are coprime, so each is a perfect square, say n² and m². Solve for a, c and you recover the formula.

Python Generate primitive triples with Euclid's formula

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two lists agree. The count of primitive triples with hypotenuse up to N grows like N / (2π), so for N = 10000 we expect about 1600 (the printed count is close).

Properties worth knowing

  • One leg is divisible by 3, one leg by 4, and one side by 5. So the area ab/2 of an integer right triangle is always a multiple of 6.
  • Hypotenuses of primitive triples are products of primes of the form 4k + 1. We will explain why in sums of two squares.
  • The inradius (a + b - c)/2 is always an integer.
Python Checking the divisibility facts

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree of primitive triples

Berggren (1934) found that all primitive triples form a ternary tree rooted at (3, 4, 5). Treat a triple as a column vector and multiply by one of three integer matrices to get three children.

Python Berggren's tree

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every primitive triple appears exactly once, so you can enumerate all of them by walking the tree.

flowchart TD
    R["(3, 4, 5)"] --> A["(5, 12, 13)"]
    R --> B["(21, 20, 29)"]
    R --> C["(15, 8, 17)"]
    A --> A1["(7, 24, 25)"]
    A --> A2["(55, 48, 73)"]
    A --> A3["(45, 28, 53)"]

The first two levels of the Berggren tree (each child comes from a matrix product).

No Pythagorean fourth powers

What if the exponent is 4: x⁴ + y⁴ = z²? Fermat proved that this has no solutions in positive integers, using infinite descent: a smallest solution would produce an even smaller one, which is absurd. This implies that x⁴ + y⁴ = z⁴ has none either, the n = 4 case of Fermat's last theorem. Computer search cannot prove a negative statement, but it can fail to find counterexamples, which is reassuring.

Python Searching for x^4 + y^4 = z^2

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The empty list matches Fermat's theorem.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Euclid's formula with m = 4, n = 1 gives which triple?

    a = 16 - 1 = 15, b = 241 = 8, c = 16 + 1 = 17, giving (15, 8, 17).
  2. 2. When does Euclid's formula give a primitive triple?

    If both were odd, all three sides would be even; a common factor would divide them.
  3. 3. Which is always true for a Pythagorean triple?

    One leg is divisible by 3 and one by 4, so ab/2 is divisible by 6.
  4. 4. Which technique proved that x^4 + y^4 = z^2 has no positive solutions?

    Fermat showed that any solution would produce a smaller one, which cannot go on forever.

Summary

  • A primitive triple has gcd(a, b, c) = 1; all others are multiples of primitive ones.
  • Euclid's formula (m² - n², 2mn, m² + n²) with m > n coprime and opposite parity gives every primitive triple.
  • Properties: a leg divisible by 3, a leg by 4, a side by 5, area divisible by 6.
  • Berggren's three matrices generate the complete tree from (3, 4, 5).
  • x⁴ + y⁴ = z² has no solutions, proved by infinite descent.

Next: Pell's Equation and Sums of Squares