Contents Supplements and Links

I. Introduction

The Pythagorean theorem carries the name of the Greek mathematician Pythagoras, who lived in the 6th century BCE, though the theorem had been known elsewhere for some time before. Although the Pythagorean theorem arose in geometry, we will be concerned strictly with the number theoretic properties of the Pythagorean equation, using the connection to geometry only as a jumping off point.

Theorem 1 (Pythagorean Theorem and converse)  Let x, y, and z be positive reals. Then z is the length of the hypotenuse of a right triangle with side lengths x, y, and z if and only if

A Pythagorean triple is an ordered triple (x, y, z) of three positive integers such that x2 + y2 = z2. If x, y, and z are relatively prime, then the triple is called primitive.

Let us first note the parity of x, y, and z in primitive triples, that is their values modulo 2. Since 02 ≡ 0, 12 ≡ 1, 22 ≡ 0, and 32 ≡ 1 mod 4, the only squares modulo 4 are 0 and 1. Letting X = x2, Y = y2, and Z = z2, we have the following solutions to X + YZ mod 4:

0 + 0 ≡ 0
0 + 1 ≡ 1
1 + 0 ≡ 1

(1 + 1 ≡ 2 is not a solution because 2 is not a square modulo 4.) The first of these solutions corresponds only to nonprimitive triples — x, y, and z are all divisible by 2. Therefore any primitive triple corresponds to one of the other two solutions. In either case, Z is odd, and exactly one of X and Y is always odd. Thus z is odd, and exactly one of x and y is odd. To establish a convention, let us say that x is always odd and y is always even, since otherwise we can rename the variables of a given triple to obtain this. A primitive Pythagorean triple therefore has a unique representation (x, y, z), where y is even and x and z are odd.

Let a = zx and b = zy. Substituting for x and y into (1) gives

or In fact, only one of these values for z holds. The solution results in x or y being negative, so we take



Then the following hold:

Solving for r and for s, we find


The generators r and s will provide the basis of study for primitive triples. Most texts use the more common generators m and n, where x = m2n2, y = 2mn, and z = m2 + n2. Though I believe r and s as defined above are more natural choices (since they emphasize symmetry in the generators and not in the side lengths), the analysis is the same in the end, as m = r + s and n = r.

II. Properties of r, s, x, y, and z

Theorem 2  A Pythagorean triple is primitive if and only if r and s are integers, s is odd, and (r, s) = 1.

Proof. Let (x, y, z) be a primitive Pythagorean triple (with even y). The quantities z + y and 2y are relatively prime because z and y are relatively prime in primitive triples and z + y is odd. We have

so z + y and zy are relatively prime (because any common divisor would also divide 2y). The Pythagorean relation (1) implies that

so z + y and zy must both be squares because they are relatively prime. Therefore is an odd integer. By (4), r is also an integer because

is even.
Now that we have established that r and s are integers for primitive triples, we will show that they are relatively prime. Let m = (r, s). Since m divides both r and s, m divides x, y, and z by (3). But since x and y (in particular) are relatively prime, this means m = 1.

For the converse, assume s is odd and (r, s) = 1. Because , we have that (r, z) = 1, since any divisor of both r and z is a divisor of s but r and s are relatively prime. By the definition of r, x + 2r2 = z, so similarly (x, z) = 1. Therefore the triple (x, y, z) is primitive. ■

Corollary  The number of primitive Pythagorean triples is countably infinite.

Proof. Since each relatively prime pair (r, s) with odd s gives a unique primitive triple, it suffices to consider the cardinality of the set S = {(r, s) | r and s are relatively prime and s is odd}. This set is infinite since for each odd s there is at least one r relatively prime to s, but S is no larger than the rationals (by mapping S injectively into the rationals by sending (r, s) to r / s). Therefore the set S is countably infinite. ■

Next we will prove several results regarding triples modulo 3, 4, and 5.

Remark 1  If (x, y, z) is a primitive Pythagorean triple, then y ≡ 0 mod 4, z ≡ 1 mod 4, exactly one of {x, y} satisfies k ≡ 0 mod 3, and exactly one of {x, y, z} satisfies k ≡ 0 mod 5.

Proof. From (3), y = 2r (r + s). Either r is even or r + s is even (since s is odd), so 4 divides y.
As shown above, the only squares modulo 4 are 0 and 1. Since z = r2 + (r + s)2 is a sum of two squares and s is odd, there are two possibilities. If r is odd then z ≡ 1 + 0 ≡ 1 mod 4, and if r is even then z ≡ 0 + 1 ≡ 1 mod 4.

The only squares modulo 3 are 0 and 1. With X = x2, Y = y2, and Z = z2, the congruence X + YZ mod 3 has the following solutions:

0 + 0 ≡ 0
0 + 1 ≡ 1
1 + 0 ≡ 1

The first case is nonprimitive, so either x2 or y2 is divisible by 3, and this implies that either x or y is divisible by 3.

The only squares modulo 5 are 0, 1, and 4, so X + YZ mod 5 has solutions (up to permutation of X and Y):

0 + 0 ≡ 0
0 + 1 ≡ 1
0 + 4 ≡ 4
1 + 4 ≡ 0

Again, the first case is nonprimitive so exactly one side is divisible by 5. ■

To convince yourself that these are the only three generalizations we can make like this, experiment with different prime moduli with the Tripes Modulo p JavaScript program. Larger numbers (7, 11, 13,...) yield no obvious statements about the divisors of the respective triple members.

III. Counting Triples

Definition  Two triples are siblings if they have a common hypotenuse.

The first such pair of primitive triples stem from the hypotenuse 65 (332 + 562 = 632 + 162 = 652):


There are also primitive siblings of the hypotenuse 85:


If we search larger numbers, we can find larger sets of siblings. There are, for example, four primitive triples with hypotenuse 1105:


In general, the number of primitive Pythagorean triples of hypotenuse n is dependent on the number of prime factors of n that are congruent to 1 modulo 4. It turns out that only powers of 2 appear as these numbers. The numbers in the sequence 5, 65, 1105, 32045, 1185665, 48612265, 2576450045,... are the smallest hypotenuses that harbor 1, 2, 4, 8, 16, 32, 64,... primitive Pythagorean triples. The terms are given by multiplying successive primes that satisfy p ≡ 1 mod 4:

The hypotenuse 32045 has eight primitive triples:


But why do primitive triples form only in sets of 2α, and what is the connection to primes p ≡ 1 mod 4? Let us look at the prime factors of n more closely.

By examining the data, it appears that the prime factors of each hypotenuse satisfy p ≡ 1 mod 4. Further, each prime hyptenuse holds only one triple, and the more factors a hypotenuse has, the more triples it holds. Specifically, if ω(n) is the number of distinct prime factors of n and all of the prime factors of n satisfy p ≡ 1 mod 4, then n appears to be the hypotenuse of exactly 2ω(n) – 1 primitive Pythagorean triples. (If n has any prime factors p ≡ 2 or 3 mod 4, then n is not the hypotenuse of any primitive triples.) In light of this, it makes sense that the first sibling sets of order 2α will be found on the multiples of the first α primes that satisfy p ≡ 1 mod 4.

Of course, explaining where 2ω(z) – 1 arises is more tricky. Some experimentation shows that, for n with the above criteria, (3) has 2ω(n) – 1 positive integral solutions for r and s. We are interested in solutions to n = r2 + (r + s)2 where r and r + s are relatively prime (or, equivalently, (r, s) = 1). To see what is happening, first let us quote a theorem attributed to Fermat, the proof of which we leave to a book covering introductory number theory.

Theorem 3 (Fermat)  Let p be a prime such that p ≡ 1 mod 4. Then p can be expressed uniquely as a sum of two squares.

By "uniquely" it is meant that there exist unique integers a and b such that 0 < a < b and p = a2 + b2. Using Fermat's theorem, we decompose a number n into is prime factors and write each prime as a sum of two squares. We then make use of the Fibonacci identity,


by which we can write the product of sums of two squares again as the sum of two squares. Multiplying together the sum of squares representations for the prime factors of n gives a sum of squares representation for n, and since the hypotenuse of a primitive triple is a sum r2 + (r + s)2 of two squares (by (3)), we will be able to generate primitive triples of hypotenuse n simply by knowing the sum of squares representations of the prime factors of n.

For example, for n = 1105,

This solution corresponds to r = 23, s = 1, which generate the triple (47, 1104, 1105). The other solutions to 1105 = r2 + (r + s)2 can be obtained by changing the order in which the factors are multiplied together and by reversing the sum of squares expressions of some factors.

Actually counting the solutions that we get in this way is cumbersome, however. The system is not a very natural one, and "Fibonacci multiplication" is in fact not even associative. Much better are the Gaussian integers — complex numbers of the form a + bi, where a and b are ordinary integers and i2 = –1. By Fermat's theorem, each prime factor p ≡ 1 mod 4 of n conveniently has the representation p = a2 + b2 = (a + bi) (abi). Multiplying two Gaussian integers exactly results in the Fibonacci identity:

Rather than multiplying sum of squares representations, we will multiply Gaussian integers. We obtain the four solutions to 1105 = r2 + (r + s)2 by multiplying (Gaussian) "halves" of its (integer) factors p = (a + bi) (abi) . For each of the three primes dividing 1105, we have two choices of which Gaussian factor to take. Complex conjugation of a solution does not change the sum of squares representation, so we can choose the first such factor to have positive imaginary part. The solutions are then

By multiplying each by its complex conjugate, these correspond to the four representations of 1105 as a sum of two relatively prime squares (and thus to the four primitive triples with hypotenuse 1105).

Proposition  Let n > 1 be a natural number whose prime factors all satisfy p ≡ 1 mod 4. Then the number of distinct ways that n can be expressed as a sum a2 + b2 of two squares with a and b are relatively prime is 2ω(n) – 1, where ω(n) is the number of distinct prime factors of n.

This result allows us to count triples of a given hypotenuse: Because z has 2ω(z) – 1 sum of squares representations when all its factors satisfy p ≡ 1 mod 4, there are 2ω(z) – 1 distinct solutions to (3). In each of these solutions, r and s are relatively prime (because r + si is not divisible by any integer prime) and s is odd (because an even s results in an even z). Therefore z is the hypotenuse of exactly 2ω(z) – 1 primitive Pythagorean triples. Not only does it allow counting, however, but it provides an algorithm to actually construct the triples given the sums of square representations of its prime factors. A simple program can readily compute, for example, the 214 = 16384 primitive triples with hypotenuse n = 16880412096169215173498945, which is the product of the first fifteen primes that satisfy p ≡ 1 mod 4.

Until now we have considered triples based only on z; with what we have learned it is now easy to understand them sorted also by x or by y (where "P" denotes a prime leg and "P" denotes a prime power leg):

xyzrs     xyzrs xyzrs     xyzrs
3P4511 21
202923 34P511 4528
5P121321 21220221101 158P1713 19528197113
7P242531 23P264265111 512
1321 25532P257115
9P404141 25P312313121 35123715 7736
11P606151 27P364365131 6316P6517 32336325117
13P848561 29P420421141 2120
2923 940
81713 31P480481151 992010119 39940401119
1511211371 33
566543 724
2531 11744
17P14414581 33544545161 14324145111 48344485121

Very similar to the case of z, the prime factors of a given x determine how many triples have x as a leg (without the restriction that the prime factors must satisfy p ≡ 1 mod 4): If x ≡ 1 mod 2, then x is a leg of 2ω(x) – 1 primitive triples. And if y ≡ 0 mod 4, then y is a leg of 2ω(y) – 1 primitive triples.

Theorem 3  Let ω(n) be the number of distinct prime factors of a natural number n > 1. The number of primitive Pythagorean triples of which n is a member is


We now generalize the problem of counting to include nonprimitive triples. (For a nonprimitive triple, r and s are irrational unless the common factor of the triple is a square.)

Theorem 4  If the natural number z decomposes into distinct primes as

with pi ≡ 1 mod 4 for all i and qj ≡ 3 mod 4 for all j, then z is the hypotenuse of exactly
Pythagorean triples.

Proof. Let z be a natural number. Since primes q ≡ 3 mod 4 and the prime 2 do not contribute to primitive triples, these factors in z do not contribute to the total number of triples with hypotenuse z (i.e., removing all of these factors from a given z results in an integer that is the hypotenuse of the same number of triples as z). Therefore it suffices to consider natural numbers of the form with pi ≡ 1 mod 4 for each i. The number of divisors of z that can be written as a product of powers of exactly j primes is σj(α1,α2,...,αk), the jth elementary symmetric polynomial on the exponents α1, α2, ..., αk. Each such divisor d of z is the hypotenuse of 2ω(d) – 1 = 2j – 1 primitive triples, by Theorem 3, and so contributes 2j – 1 nonprimitive triples of hypotenuse z by simply multiplying by z / d. Thus, by a property of the elementary symmetric polynomials,

For example, 3142875 = 3 · 53 · 172 · 29 is the hypotenuse of exactly T(3142875) = ((2 · 3 + 1) (2 · 2 + 1) (2 · 1 + 1) – 1) / 2 = 52 Pythagorean triples.

Corollary  Let z = Q p1 p2 ... pk > 1 be a natural number with exactly k distinct prime factors satisfying p ≡ 1 mod 4 and no factor of the form p2 for any prime p ≡ 1 mod 4. Then the number of Pythagorean triples with hypotenuse z is T(z) = (3k – 1) / 2.

IV. Restrictions on Primitive Triples

In this section we will be interested in triples that satisfy certain conditions. Sometimes a triple that has a pair of sides with only a unit difference is referred to as a "twin." For example, the triples (3, 4, 5), (5, 12, 13), (7, 24, 25), and (21, 20, 29) each have a pair of sides that differ by 1. By browsing data, one finds that triples satisfying zy = 1 are more common than those satisfying |xy| = 1. There are infinitely many of both types, but the latter much less densely populate the world of primitive triples.

To find triples with b = zy = 1, we solve x2 + (z – 1)2 = z2 for z to find


Any odd x then gives such a triple. Substituting this into the definition of r gives

Since s = √b = 1, the first few triples with b = 1 are:


Moreover, the sequence of y values is 4 times the triangular numbers, since, by (3),

This same procedure can be used for any valid a or b value because the resulting equation will always be linear in z. From (3) we see that the nth triples with fixed a and b values are given by


We now turn to primitive triples with the restriction that |xy| is a given difference d. The following is a list of the first few triples for which d = 1. (The first twenty-five of these triples are listed.)


To find the general form of these triples we must resort to a new technique, for the equation x2 + (x + d)2 = z2 does not lead to a natural assignment of an index to one of the generators. But since r and s display simple patterns in fixed-a and -b triples, we might suspect that they will for fixed-d triples also. We notice two (among many) recurrence relations that seem to hold: rn = rn – 1 + sn – 1 and sn = rn + rn – 1. Substituting for sn – 1 we find

Second-order recurrence relations have solutions of the form rn = kn. Thus, from the recurrence relation,

the nonzero solutions of which satisfy k2 – 2k – 1 = 0. So we have

Both of these values for k satisfy the recurrence, but we want the first and second terms to be 1 and 2 (the r values of the first two triples). Since a linear combination of the two values for k also satisfies the recurrence, we construct the general solution for rn,

and solve for the constants we introduce by specifying the first two terms:

We find that


and by the recurrence relations,

So the nth triple satisfying |xy| = 1 is given (from (3)) by


Clearly the difference of xn and yn is always 1. Intuitively, we know that as n gets large, the triples (xn, yn, zn) approach the side lengths of a right isosceles triangle, the ratios zn / xn and zn / yn approaching √2. It is interesting, however, to examine the ratio sn / rn as n gets large; one finds that not only does this ratio also approach √2, but sn / rn is the nth continued fraction convergent to √2. This connection becomes apparent when we approach the solution of |xy| = 1 triples another way and obtain a Pell equation, the solutions of which are these convergents:


Because the sequence sn / rn are the continued fraction convergents to √2, rn and sn are relatively prime. Moreover, s is odd, and so r and s generate a primitive triple.

When d ≠ 1, the situation is slightly more complicated. Take d = 7 for example. The first few triples are:


At first glance it appears that these r and s values hardly form nice recurrence relations. But in fact they do; there are two "threads" of the same relation (with different initial values) running through these triples, more easily seen when they are sorted:


Again the recurrence is

Therefore, as above, the general solution is


So the first thread of triples for which |xy| = 7 is given by

and the second thread is given by

In general, xy = s2 – 2r2, and the only numbers of this form, for r and s relatively prime and s odd, are those whose prime factors all satisfy p ≡ ±1 mod 8. These primes comprise the sequence 7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97,...  As representations as a sum of two squares were counted by factoring over Z[i] in Section III, we can count "fundamental" representations of a given number as s2 – 2r2 = (s + r√2) (sr√2) by factoring over Z[√2]. For example, –1 = 12 – 2 · 12. The ring Z[√2] has infinitely many units, given by ±(1 + √2)n for integers n. Call a representation s2 – 2r2 fundamental if sr or s ≥ 2r. Each fundamental representation s12 – 2r12 gives rise to a thread of triples generated by sn + rn√2 = (s1 + r1√2) (1 + √2)n for nonnegative integers n. Each prime factor contributes two fundamental solutions, so we have the following result.

Proposition 2  Let d be a natural number whose prime factors all satisfy p ≡ ±1 mod 8. Then the number of fundamental representations of d in the form s2 – 2r2 for positive integers r and s is 2ω(d), where ω(d) is the number of distinct prime factors of d.

(Alternatively, we could have considered sequences of triples that are infinitely long in both the positive and negative directions. In this case, there are 2ω(d) – 1 (double-sided) threads for a given d, and the case d = 1 must be separated from the others (since it still has only one thread, which is redundant). In this setup, however, we obtain triples with negative legs.)

Each fundamental solution (r1, s1) gives rise to the sequence of triples

For example, let d = 2737 = 7 · 17 · 23. The fundamental representations for these prime factors are

Thus 2737 has the following fundamental representations (where we divide each product by a power of 1 + √2 to obtain fundamental representations, in this case the first power):

An additional four threads come from the fundamental representations of –2737:


Relevant links: