# document.write (document.title)

 Math Help > Number Theory > Pythagorean Triples > Pythagorean Puzzle

An interesting problem was posed on theproblemsite.com  in the March, 2003

### How many Pythagorean triples exist with a leg that is the product of n primes (and 2 is one of those primes)?

In more detail, here is how the problem was posed:

Exactly four right triangles with integer side lengths exist with a leg equal to 15. These are:

(15, 112, 113), (15, 20, 25), (15, 36, 39), and (8, 15, 17).

How many different right triangle with integer side lengths exist with a leg equal to 42? How do you know?

BONUS QUESTION:

42 is the product of 3 different prime numbers -- 2, 3, and 7.

Resolve this problem given a leg which is the product of n different primes, given that, as in this problem, one of these primes is 2.

My answer to the first question: 4, and to the bonus question: (3n-3)/6

Every primitive (i.e. pairwise coprime) Pythagorean triple can be expressed as (r²-s², 2rs, r²+s²), where r and s are coprime, r is greater than s, and exactly one of them is odd. (See Pythagorean Triples for a demonstration of this)

The first element (a leg of the corresponding triangle) of each primitive Pythagorean triple is odd; the second (another leg) is a multiple of 4; and the hypotenuse is odd.   These facts are clear from the fact that exactly one of r and s is odd, and I demonstrate this on the Pythagorean Triples page as well.

Every Pythagorean triple is some positive integer k multiplied by a primitive Pythagorean triple.  42 can't be the middle element (as I've written it here) because 42 isn't a multiple of 4. We're told 42 is a leg, so it must be the first element. The primitive Pythagorean triple from which our answers are derived must be an odd factor of 42, which means it is 3, 7, or 21.

That means r is at most 11, because all larger values of r result in numbers larger than 21 in the first position of the primitive Pythagorean triple. So at this point, I could just look at the 27 different primitive Pythagorean triples generated by values of r ranging from two through eleven, but it would be more instructive to the "bonus question" if I do a bit more actual thinking here.

Every odd number 2k+1 appears as the first element of a primitive Pythagorean triple when s=k and r=k+1, so 3, 7, and 21 all appear as the first element of a primitive Pythagorean triple at least once.  But prime numbers appear no more than once.

Why is that?  Because r-s is a divisor of r²-s², so r²-s² is not prime unless r-s=1 (a necessary but not sufficient condition).  The number 21 can appear in the first element of a primitive Pythagorean triple more than once because it isn't prime, and in fact it appears twice, because it can be expressed as the difference of squares in two different ways: 121-100 and 25-4. These correspond to r,s values of 11,10 and 5,2, respectively.

Since the first element of the primitive Pythagorean triple is the difference of two squares r²-s², it is also the product of (r+s)(r-s).  Since 21 is the product of two primes, it can only be factored two ways -- 21*1 and 7*3, corresponding to the two values of r,s which define the two primitive Pythagorean triples in which 21 appears as the first element.

So whenever a number, m, is the product three distinct primes (of which 2 is one of them), there are exactly four Pythagorean triples containing m as an element.

This, by the way, is the same as the number of Pythagorean triples containing m as an element, where m is the product of two distinct odd primes. The inclusion of the prime number, 2, is a red herring. This is because r and s have opposite parity, so their difference and their sum can't be even, so no primitive Pythagorean triple has 2 as a factor of its first element, and the second element always has two twice as a factor.

### Now for the bonus question...

I'll explore larger numbers of distinct odd primes in the prime factorization of the first leg.

If m is the product of 3 distinct odd primes, say 3*5*7=105, then the number of triples whose first element is a factor of 105 is:

(r+s)(r-s)=some factor of 105

(2+1)(2-1)=3
(3+2)(3-2)=5
(4+3)(4-3)=7

(8+7)(8-7)=15
(4+1)(4-1)=15

(11+10)(11-10)=21
(5+2)(5-2)=21

(18+17)(18-17)=35
(6+1)(6-1)=35

(53+52)(53-52)=105
(11+4)(11-4)=105
(13+8)(13-8)=105
(19+16)(19-16)=105

The total is 13 triples containing the product of three odd primes (or four primes including 2), as follows:

3*1 triples for each of the three odd primes, plus
3*2 triples for each of the pairs of odd primes, plus
1*4 triples for each of the odd primes taken 3 at a time.

Well, I have to be honest here, and tell you I haven't found 13 primitive Pythagorean triples yet, just 13 different pairs of factors r+s and r-s whose products are factors of 105.  To verify these correspond to primitive Pythagorean triples, I must also show that r is greater than s, they have opposite parity and are coprime.  These are fairly easy, so I'll just rattle them off here:

1. r and s are different, and I'll just stipulate that r is the bigger of the two.

2. The product of r+s and r-s is odd, so r+s is odd, which means they have opposite parity.

3. The product of r+s and r-s is the product of distinct primes, so r+s and r-s have no prime factor in common.
That is, GCD(r+s,r-s)=1
By linear combination GCD(2r,r-s)=1, so GCD(r,r-s)=1, so GCD(r,s)=1
("Linear combination" means this: GCD(a,b)=GCD(a+kb,b), where k is any integer.)

This is 3C1 ways to pick one of the primes times 1, which is half the number of factors of this one prime, plus

3C2 ways to pick two of the primes times 2, which is half the number of factors of the product of two primes, plus

3C3 ways to pick three primes times 4, which is half the number of factors of the product of three primes.

I expect you'll see right away where the 3Ci comes from (the number of ways to pick i primes from among three possibilities), but you may wonder about the "half the number of factors" piece of it. This comes from the fact that the number of ways to factor of the product of n distinct primes is (or any non-square, for that matter) is half the number of factors of that number, and the number of factors of the product of n primes is 2n.  (In general, the number of factors of p1e1 * p2e2 * ... * pnen is (e1+1)(e2+1)...(en+1) )

If n is the number of odd primes, then the number of triples is

nCi 2i-1
i=1

The following table gives, for various numbers of odd primes, the number of Pythagorean triples with an element that can be expressed as the product of this many odd primes:

 n triples 1 1 2 4 3 13 4 40 5 121 6 364 7 1093

A little clever deduction -- see below -- (or a peak at Sloan's integer sequences -- hey, it's a free country!) will convince you that this sequence is

(3n-1)/2

Since the bonus question was phrased so as to include 2 as one of the n primes (and 2 is a red herring, as described above), the answer to the bonus question becomes

(3n-1-1)/2, or

(3n-3)/6,

which is my answer to the bonus question.

### Easy way

It turns out that was the hard way to solve this problem.  Here's the easy way, by Sasha:

The problem: how many pairs of integers (j , k) with k > j exist such that 42² + j² = k²?

42² = k² - j² = (k + j)(k - j)

Since k and j are integers and k > j, k + j and k - j must be positive integers which, when multiplied, equal 42². This seems straightforward - find the number of factors of 42², subtract 1 (since we can't have j = 0), and divide by two.

42 = (2)(3)(7)
42² = 2²3²7²

So 42 has (2+1)³ = 27 factors, and 13 factor pairs.

However, not all factor pairs will give us integer values of j and k. Allow the two factors to be F1 and F2 so that F2 > F1 and F1F2 = 42²

k + j = F2
k - j = F1
k = (F2+F1)/2
j = (F2-F1)/2

We can therefore allow both factors to be odd or both factors to be even, but if they were both odd, their product would be odd, so both factors must be even.  This means we must eliminate all cases where F1 OR F2 = 4k, where k is any factor of 3²7².  There are 9 such factors, so only 4 right triangles with integer side lengths and a leg equal to 42 exist.  In general, we eliminate 3n-1 factor pairs. This leads us to our general equation for the bonus question

1/2(3n - 1) - 1/33n = 1/6(3n-3)

Incidentally, this proves that there are no right triangles with integer side lengths and a leg equal to 2 (that is, for n = 1, 1/6(3n - 3) = 0 ).

### Even simpler

I realized that the number of triangles with a leg that is the product of n primes (of which 2 is one) is equal to the number of triangles with a leg that is the product of n-1 odd primes.

Using that fact, and Sasha's basic method, we have this solution:

The problem: how many pairs of integers (j , k) with k > j > 0 exist such that 42² + j² = k²?  This is the same as the number of pairs of integers (j, k) with k > j > 0 such that 21² + j² = k²?

21² = k² - j² = (k + j)(k - j)

Since k and j are integers and k > j, k + j and k - j must be positive integers which, when multiplied, equal 21². This seems straightforward - find the number of factors of 42², subtract 1 (since we can't have j = 0), and divide by two.

21 = (3)(7)
21² = 3²7²

So 21 has (1+1)³ = 9 factors, and 4 factor pairs.

This leads us to our general equation for the bonus question

1/2(3n-1 - 1) = 1/6(3n-3)

### Proof that

n
nCi 2i-1  =  (3n-1)/2
i=1

First, let me restate it as

n
nCi 2i  =  3n
i=0

This proof will use the same idea as the "Pascal's Triangle" proof that the sum of any row of Pascal's Triangle is twice the sum of the row above it, because in forming the sum, each element of the higher row is used twice as an addend in forming the row below it.

In this case, you can think of the sum, immediately above, as a kind of Pascal's Triangle in which each element is formed from twice the element above-and-to-the-left plus the element above-and-to-the-right.  Thus, each element of the higher row is used three times as an addend in forming the row below it.

Now let's do it with a bit more rigor.  This will be a proof by induction on n...

It's true when n=0.  Let's assume it's true when n=k, and show it's true when n=k+1.

A quick review...

k+1Ci = kCi-1 + kCi , when 0 < i <= k, and

k+1C0 = 1, and k+1Ck+1 = kCk, so

k+1Ci 2i = 2kCi-1 2i-1 + kCi 2i , when 0 < i <= k, and

k+1C0 20 = 1, and k+1Ck+1 2k+1 = 2 kCk 2k , so here we have:

 k+1 ∑ k+1Ci 2i  = 1 +  i=0 k ∑ k+1Ci 2i  + k+1Ck+1 2k+1 = 1 +  i=1 k 2∑ kCi-1 2i-1  +    i=1 k  ∑ kCi 2i  + 2 kCk 2k   i=1

Then, by rearranging the right hand side of this equation (the "1" becomes part of the second sum, and the "2 kCk 2k" becomes part of the first):

 k+1 ∑ k+1Ci 2i  =  i=0 k 2∑ kCi 2i  +    i=0 k  ∑ kCi 2i  =   i=0 k 3∑ kCi 2i  =    i=0 3k+1

### Related pages in this website

Number Theory

Pythagorean Theorem

Prove that the area of a right triangle with integer sides is not a perfect square.  I got some help, and finished this proof!

Formulas for Primitive Pythagorean Triples and their deriviation -- a way to generate all the triples such that a² + b² = c²

Arithmetic Sequence of Perfect Squares, page 3 -- If a², b², c² are in arithmetic sequence, why is their constant difference a multiple of 24?  Look at the second answer to this question for the relationship between Pythagorean Triples and this arithmetic sequence of squares.

Basic Number Theory Definitions

Theorems Involving Perfect Squares -- answers questions such as "why is the square root of x irrational unless x is a perfect square?" and other fundamental questions about perfect squares.

The webmaster and author of this Math Help site is Graeme McRae.