Pythagorean triples

A Pythagorean triple is a set of integers a, b, and c such that

a^2 + b^2 = c^2

We want primitive triples, those where a, b and c do not have a common factor.

Euclid presents a formula for that:  take any two integers n > m > 0, then

b = 2mn
a = n^2 - m^2
c = n^2 + m^2

One more restriction:  m and n must not have any common factor, they should be co-prime, otherwise the triple will not be primitive.

It is easy to show that when a, b, and c are found in this way, they satisfy the Pythagorean equation.

The trick is to see where this comes from, and more importantly, to show that it describes all such triples.

Derivation

I found a very nice derivation in Maor (The Pythagorean theorem).  We start by investigating the properties of a, b and c.  

For example a and b cannot both be even, for in that case, c will also be even, and then there is a common factor.

Recall that any even number can be written as 2k, and any odd number as 2k + 1 for positive integer k (or k = 0 for n = 1), so it is easy to see that if n is even, so is n^2.  And if n is odd then so is n^2 as well.  Therefore an even perfect square implies an even integer square root, and an odd square implies an odd root.

In the case where a and b are both odd, c must be even, since odd plus odd equals even.  To see a problem with this re-write the equation 

(2i + 1)^2 + (2j + 1)^2 = (2k)^2

The left-hand side is not a multiple of 4, but the right-hand side is.  This is impossible.  Hence one of a or b must be even and the other odd.  Let a be odd.  Then b can be written as b = 2t for some integer t.  We have

(2t)^2 = c^2 - a^2 = (c + a)(c - a)

Every a, b and c must satisfy this equation.  Furthermore, we see that there is a factor of 4 on the left-hand side, hence we can get a divisor of 2 for each factor on the right:

t^2 = (c + a)/2 . (c - a)/2

a and c are both odd:

a = 2i + 1
c = 2k + 1

so their sum and difference are even, since

2k + 1 + 2i + 1 = 2(k + i) + 2
2k + 1 - 2i - 1 = 2(k - i)

After canceling the factor of 2 we get

(c + a)/2 = k + i + 1
(c - a)/2 = k - i

Thus both of these factors on the right-hand side are integers, while the left-hand side (t^2) is a perfect square.

Key step

Here's the last step.  We claim that these two terms do not have a common factor.  

Whenever x and y have a common factor, so do their sum and difference since x + y = fp + fq = f(p + q).  and so on.  The converse is also true.  

But the sum and difference for these terms are:

(c + a)/2 + (c - a)/2 = c
(c + a)/2 - (c - a)/2 = a

On the supposition that (c+a)/2 and (c-a)/2 did have a common factor, then they would share that common factor with both c and a.   Since we know that a and c (at least the particular ones we're interested in) do not have a common factor, neither do these two terms.

So the two terms have no common factor and yet multiply together to give a perfect square.

t cannot be prime itself (because there would not be two different factors).

So clearly there are two factors m^2 and n^2 (m and n not necessarily prime), and both terms are perfect squares!  Write:

n^2 = (c + a)/2
m^2 = (c - a)/2

n^2 + m^2 = c
n^2 - m^2 = a

And

m^2n^2 = t^2
mn = t

Since b^2 = 4t^2, b = 2t = 2mn.

These properties of m and n follow from the standard rules about factors, applied to a, b and c.  Therefore, any triple a, b, and c can be written in terms of an integer m and n by this method.

I checked this by using a Python script to search the entire space of squares below an arbitrary limit, for those which sum to give another square, keeping only those triples of squares with no common factors.

I tested each triple by taking the even member, dividing by 2, and then finding its factors.  This gives candidate pairs m and n with 2mn = b.  Then, just check for whether n^2 - m^2 = a.

The gist is here.

It is interesting to see which patterns among the triples come from which choices of m and n.

Pi again

 I was working on a post about Archimedes calculation for pi, and I saw a reference that said Ptolemy used 377/120 as a rational approximation to the value.  

And then I also read that 355/113 is an even better approximation, and it is credited to the Chinese mathematician Zu Chongzhi (5th century CE).

There is a whole article in wikipedia about this subject.  Recall that Archimedes established upper and lower bounds on pi of 22/7 (3.14285714) and 3-10/71 (3.14084507)

In decimal form, Ptolemy's value is 

377/120 = 3.14166...

This is correct to the third digit after the decimal point.  The error is 7401 parts in ten million.  And really, it is accurate enough for any practical work.

I found it curious that the other value has a smaller denominator, but was not found by Ptolemy, and yet it is better, much better.

355/113 = 3.14159292

This is correct to the sixth digit after the decimal point.  The error is 27 parts in ten million.  That's about 275 times better than Ptolemy's value.

There is some text from Pi: A Source Book, by Berggren et al online.  In a chapter by Tam Lay-Young and And Tian-Se, I found a calculation ascribed to Liu Hui (3rd century CE).

The calculation does not seem to be any kind of a technical breakthrough, it is just a basic usage of the Pythagorean theorem.  (However, there are some values given that I don't see where they came from, so maybe I'm missing something).

Start with a circle of radius 10, and inscribe a hexagon.  One of the six equilateral triangles is shown.

DC = 5.17638.

Repeat until you're satisfied.  Keep track of n, the total number of sides.

At the end, compute the area of the polygon as 1/2 times the radius times n times the chord.  Since r = 10, the area of the circle is pi times 100.

The estimate based on the dodecagon is 6 x 10 x 5.17638 divided by 100 = 3.10582854.

In the end, they obtain 314-64/625, 314-169/625 as the bounds on pi (it's not clear to me how an upper bound was obtained).

In decimal, this means that 3.141024 < pi < 3.142704, which is slightly better than Archimedes.  

Apparently, Zu Chongzhi (5th century CE) went farther, far enough to recognize that 355/113 matches an improved estimate very well.  

The wikipedia article on Zu Chongzhi claims that he is "most notable for calculating pi as between 3.1415926 and 3.1415927".  It claims that his works show he calculated pi to 6 digits using a "12,288-gon".  

That's obtained by doubling a hexagon 9 times.  Using Python the other day, we obtained the sixth digit (after the decimal point) on round 9 of hexagon doubling as well. 

The answer as to how Ptolemy missed it seems to be that he didn't know the true value of pi well enough to believe that 355/113 was any better than 377/120.  The other possibility is that he was led to his value by some logic, and didn't check nearby values systematically.

I wrote a Python program to find rational approximations to (irrational) numbers.  The gist is here.

355/113 is a spectacular success.  

No other value comes close for a long time.  Aside from 355/113, every other fraction that becomes a better approximation is a very gradual improvement on what came before.  The first fraction to be a better approximation for pi than 355/113 is 52163/16604.

A Dedekind cut has to land somewhere.  I suppose 355/113 just lands particularly close to pi by accident.

Here is a plot of the errors.  The x-axis is the denominator.  The log of the absolute value of the difference from pi is plotted for all fractions that are closest to pi for a given denominator and also in lowest terms.  (gist).  You can see how special 355/113 is, and it stays that way (not shown).

I've written up the math for the area and perimeter methods for estimating pi and compared it to Archimedes (here).

Archimedes and pi

In this post we take a look at Archimedes' approximation of the value of pi.  I'll try to make things as simple as I possibly can, but no simpler.

Here is the fundamental idea.  We will approximate the distance around a circle, called its circumference, by the distance around a regular polygon that just fits inside the circle, called its perimeter.  The points or vertices of the polygon will lie on the circle.

                                                 

It doesn't actually matter what kind of a polygon it is (i.e. how many sides there are), but it has to be regular, with sides all of the same length.  

For an inscribed polygon, the perimeter will be smaller than the circumference of the circle.

But the trick is, there is a way to compute the new perimeter for a polygon with twice the number of sides, 2n, given the original perimeter for n sides.  

Let's look at that what that means physically.  Actually, I'm going to show below just a small arc of the circle.  One side of our initial polygon will be colored red, and the chord it makes is the red line in the figure below.  The white area shows that it doesn't track very closely with the circle, and its length will be smaller than the length of this arc of the circle.

But then, when we double the number of sides, we get a polygon of 2n sides, and its perimeter follows the two blue lines.  This is clearly more like the circumference, there is less white space.  One side has become 2.

Double the number of sides again, to 4n.  The result is the magenta perimeter.  I hope you can see that as the number of sides gets larger, the perimeter of the polygon becomes a better and better approximation to the circumference of the circle.

This method is great, if you can find a way to express the new perimeter in terms of the old one each time. This is called the method of exhaustion and it was probably invented by a Greek mathematician named Eudoxus who lived before Archimedes.

To make things easier, we will only compute the lower limit.  That is, we will use inscribed polygons and compute their perimeters as we double the number of sides again and again.  

Python will do the actual computation.  Archimedes has this estimate in the end as 3-10/71 or about 3.140845.   Let's see how we compare.

Remember that pi is the ratio of the circumference of a circle, C, to its diameter.  If we use a circle whose diameter is equal to 1, then the circumference C will be equal to pi.  

The procedure we follow here is to inscribe a hexagon into a circle of diameter 1, and then calculate the length of the perimeter of the hexagon.  We do this because a hexagon's perimeter is particularly easy to find.

We will then derive a simple method to calculate the length of the perimeter after the number of sides is doubled (to give a 12-sided polygon).  This method will be applied repeatedly.  Archimedes reached 96 sides.  That is 4 doublings (6 - 12 - 24 - 48 - 96).

What he achieved is not just an estimate for the value of pi, it is an algorithm to compute the value of pi to any desired accuracy.

Begin with the hexagon.  A hexagon can be viewed as a group of six equilateral triangles.  Since the diameter of the circle will be 1, we choose the length of each triangle's side as 1/2.  This matches the diameter, made from two sides, and it results in a total perimeter of 6 times 1/2 or just 3.  

3 is our first lower bound for pi.

I introduced the side length of 1/2 above in order to see, even before we really get started, what the perimeter of the hexagon is and give a first estimate for the value of pi.  I must ask you to set that value aside for a minute.

We will need two ratios of sides in a right triangle, and it will make the math slightly easier if we scale the next equilateral triangle up to have a side length of 2 (we'll scale it back later, all we need are the ratios).  

Obtain a right triangle by cutting an equilateral triangle of side length 2 in half, so the base of the halved triangle is 1.  Pythagoras gives us the other side as the square root of 3, since 1^2 + 3 = 2^2.

Since the original triangle was equilateral, with angles of 60 degrees each, the halved triangle has one angle of 30 degrees.  Archimedes would call that measure one-third of a right angle, and the essential ratios for him would be 2 to 1 (hypotenuse to short side), and the square root of 3 to 1.

We have the angle that we're going to start with, 30 degrees, and we have two essential ratios.

The next graphic is a proof without words of Thales' famous circle theorem:  any angle inscribed in a semicircle is a right angle.  Since PQ is a diameter, the angle PRQ is a right angle.  

Proof.  the two smaller triangles formed by the radius OR are both isosceles, so by Euclid I.5 they have equal base angles.  Since the total of all the angles in a triangle is equal to two right angles and angle PRQ is one-half that, the result follows.

We're going to choose the angle P to have the particular value of 30 degrees.  Then the complementary angle Q is 60 degrees, and RQ can be viewed as one side of an inscribed hexagon.  (We won't prove it, but the peripheral angle P is one-half the measure of the central angle ROQ which cuts off the same arc of the circle).  That makes ROQ equilateral.

The ratios that we had above will apply, because P is a 30 degree angle in a right triangle.  So the ratio of PQ to RQ is 2, and the ratio of PR to RQ is the square root of 3.

We said that we will inscribe a hexagon into circle.  I don't actually have a picture of that, but I do have a picture of an octagon, so I'll show that, and ask you to use your imagination.

Let us just focus on one of the six sides.  Suppose ROQ is an equilateral triangle, as we had before, so that RQ is one of the six sides of an inscribed hexagon.  We approximated the value of pi by finding the length of RQ (in diameter units) and then multiplying by n = 6.

Our procedure is going to be as follows:  at each step we will halve the angle at P, then compute the new length SQ.  After one cycle, SQ is one side of a 12-sided polygon, so we multiply by 12 to get an approximation for pi.

To carry out this program, we need one more preliminary result.  It is called the angle bisector theorem.  This theorem provides a way to start with the special ratios for any angle, and find the same ratios for one-half that angle.

The line segment b bisects the angle at the left, so the two half-angles labeled theta are equal.  In the upper triangle, we draw the altitude to side c and label it d.  We can do this because the larger of the two triangles formed by the altitude is congruent to the triangle in red with sides a,b,d.  

Next, the small triangle with sides e and d at the top right is similar to the whole starting triangle with sides a,f,c (both are right triangles with one smaller angle gamma).  Similar triangles gives us this ratio:

e/d = c/a

Now add 1 to both sides

e/d + d/d = c/a + a/a

f/d = c/a + a/a

a/d = c/f + a/f

On the right-hand side we have what are called in trigonometry the cosecant and cotangent of the angle 2 theta.  For the case of 2 theta equal to 30 degrees, these are the ratios from above:  c/f = 2 and a/f = square root of 3.  The left-hand side is the cotangent of the half-angle, theta, which is obtained by simple addition.  So the cotangent of 15 degrees is 2 + square root of 3.

Let's just check:

To get the other ratio for the half-angle (b/d), recall that our new triangle has sides a,b,d, and we know the ratio a/d.  But we also know from the Pythagorean theorem that

a^2 + d^2 = b^2 

so

b/d = sqrt(1 + a^2/d^2)

And that's it!  

Going back to this figure

We have that PR/RQ = square root of 3 and PQ/RQ = 2.  We compute the ratios for the half-angle, PS/SQ and PQ/SQ using the method laid out above. 

To get an estimate for pi, invert the last ratio to get SQ/PQ, recall that PQ is equal to 1, and multiply by the number of sides.  We've doubled the number of sides so n = 12. 

The essential code  is:

I set it up as a generator, which is initialized with the values of sine and cosine for 30 degrees.  A gist for the whole program is here.

Here's a screenshot of the results:

The fifth entry gives the result from four doublings as 3.141032.  Archimedes has this estimate in the end as 3-10/71 or about 3.140845.  His lower bound is smaller than ours, because we've used a powerful computer to do very accurate calculations.

One interesting aspect of the whole story is to think about how he may have obtained a rational approximation to the square root of three (all of his calculations were with rational numbers).  That's for another day.

Many thanks to the author of this page and to Neil Carothers.  (His pages have since been disappeared by his university, which hosted them, you may be able to find them by using the wayback machine).  The  post you're reading does things the way Archimedes did them, but there is a simpler formula using the values for the perimeter itself (see my pdf).

Ptolemy again

 My last post was about Ptolemy's theorem.  In the meantime, I've come across a cool "proof without words" for this.

credit

I can see how, knowing that we want ac + bd could lead you to work on scaling triangles into the parallelogram, which would then give all the angles for the central triangle (although note the switch in order for gamma and delta).

It's simply beautiful.

Ptolemy's theorem

 Ptolemy's theorem says that for a cyclic quadrilateral, the product of opposing sides, summed, is equal to the product of the diagonals:

AB CD + BC AD = AC BD

Proof. adapted from wikipedia (here).

Let the angle s (red dot) subtend arc AB and the angle t (black dot) subtend arc CD.  Then the central angle DPC = s + t and it has sin s + t.  The other central angle APD has the same sine, as it is supplementary to s + t.

Let the components of the diagonals be AC = q + s and BD = p + r.  

Twice the areas of the four small triangles will then be equal to

(pq + qr + rs + sp) sin s + t

Simple algebra will show that 

(pq + qr + rs + sp) = (p + r)(q + s) = AC BD

The product of the diagonals times the sine of either central angle is equal to twice the area of the quadrilateral.  We're on to something.

Now, the great idea.  Move D to D', so that AD' = CD and CD' = AD.  

The triangles ACD and ACD' are congruent, by SSS, so they have the same area.

Therefore the area of ABCD is equal to the area of ABCD'.

Some of the angles switch with the arcs.  In particular, angle t (black dot) now subtends arc AD'.  As a result s + t is the measure of the whole angle at vertex C.  The whole angle at vertex A is supplementary, and the sine of the whole angle at vertex A is equal to that at C.

So twice the area of triangle ABD' is AB AD' sin s + t, and twice that of BCD' is BC CD' sin s + t.  Add these two areas, equate them with the previous result, and factor out the common term sin s + t:

AC BD = AB AD' + BC CD' 

But AD' = CD and CD' = AD so

AC BD = AB CD + BC AD

This is Ptolemy's theorem. 

Here is one result from the theorem.  Draw an equilateral triangle and its circumcircle.  Pick any other point P on the circle and connect it to the vertices as shown.

Ptolemy says that

ps = qs + rs

p = q + r