Map of relatively prime pairs

Here is something which I thought was impressive. Imagine dividing a plane into two halves with the vector (1,0) labelling the left half and the vector (0,1) labelling the right. Imagine then creating a downward split in this line, a bifurcation, such that the new region created below the point of the split is labelled with the vector that is the sum of (1,0) and (0,1) namely (1,1). Now create two new bifurcations on these lines with the labels for the newly created regions being the sum of the vectors for the regions either side of the line leading to the point of the split. So, we end up with two new regions labelled with the vectors (1,0)+(1,1)=(2,1) and (1,1)+(0,1)=(1,2). Now repeat this process again ad infinitum creating 4, then 8, then 16...regions. This is the map of relatively prime pairs.

The top of this map can be seen on the front of Stillwell's book. It has some interesting properties. Firstly, each region of the map (except (1,0) and (0,1)) is labelled by a relatively prime (or coprime) pair of natural numbers. This means that for such a region (a,b), a and b have no common divisor apart from 1 (that is gcd(a,b)=1). Now what is even more amazing is that every possible pair of relatively prime natural numbers (a,b) appears as a label once, and only once, in this diagram. What is more, starting from the top of the diagram you can follow a unique path down the tree to a particular pair (a,b) of your choosing.

I think if someone asked me if it was possible to come up with some orderly way of finding every possible pair of coprime natural numbers I would have said that it was impossible and yet here is a way. What's more, it is a fairly structured diagram. If natural number pair (k,l) is anywhere to the left of natural number pair (m,n) then (k/l)>(m/n), so the ratio of the pairings decreases from left to right. In fact, if we consider the fraction a/b for any natural number pair (a,b) then this diagram contains all possible reduced fractions (i.e. fractions where a and b have no common divisor) and the fractions decrease in size from left to right.

What a cool thing!

Euclid's Algorithm again

I now want to try and relate what I know about gcd's (greatest common divisors) to what we were taught about Euclid's algorithm at the OU (in courses MS221 and M208). I have so far mentioned Euclid's subtraction algorithm but there is a faster division algorithm which is defined as follows.

Suppose we want to find the gcd(a,b) of two natural numbers a and b. Let a>b and let
$$a_{1}=a,   b_{1}=b$$
Then for each pair (a_i,b_i) we form pair (a_i+1,b_i+1) as follows:
$$a_{i+1}=b_{i},    b_{i+1}=r_{i}$$
where r_i is the remainder when a_i is divided by b_i. The process is stopped when b_k divides a_k for some k in which case gcd(a,b)=b_k.

Let's take an example from the MS221 handbook (p83) and find the gcd(25,9). We have
$$(a_{1},b_{1})=(25,9)$$
$$(a_{2},b_{2})=(9,25-2\times 9)=(9,7)$$
$$(a_{3},b_{3})=(7,9-7)=(7,2)$$
$$(a_{4},b_{4})=(2,7-3\times 2)=(2,1)$$
As 1 divides 2 then the gcd(25,9)=1. This is not unexpected as 25 and 9 are coprime and so their only common divisor is 1. In MS221 and M208 we were interested in finding multiplicative inverses and this necessarily meant that we were only interested in numbers a and b that were coprime.

Now let's repeat the gcd calculation but replace 25 and 9 by the symbols a and b.
$$(25,9)=(a,b)$$
$$(9,7)=(b,a-2b)$$
$$(7,2)=(a-2b,b-(a-2b))=(a-2b,3b-a)$$
$$(2,1)=(3b-a,a-2b-3(3b-a))=(3b-a,4a-11b)$$
From this we deduce that 4a-11b=4x25-11x9=1. This process is called the extended Euclidean algorithm.

We can now see better what was actually going on in the method that we were taught at the OU. Here is the full OU example. We are asked to find the multiplicative inverse of 9 in Z₂₅={0,1,2,...,24}, that is the element x of Z₂₅ such that
$$9\times_{25} x=1$$
We applied the division algorithm repeatedly (i.e. we found the gcd(25,9)):
$$25=2\times 9+7$$
$$9=1\times 7+2$$
$$7=3\times 2+1$$
We then worked backwards from the last of these equalities (the extended algorithm):
$$1=7-3\times2$$
$$\Leftrightarrow 1=7-3\times (9-1\times 7)$$
$$\Leftrightarrow 1=-3\times 9+4\times 7$$
$$\Leftrightarrow 1=-3\times 9+4\times (25-2\times 9)$$
$$\Leftrightarrow 1=4\times 25-11\times 9$$
The last line is the result we had before. Thus we can write
$$9\times(-11)=(-4)\times 25 +1$$
That is
$$9\times(-11)\equiv 1\:(\mbox{mod }25)$$
or alternatively
$$9\times_{25} (-11)=1$$
However, -11 is not in Z₂₅ but
$$-11\equiv 14\:(\mbox{mod }25)$$
Thus
$$9\times_{25} 14=1$$
and so x is 14.

Proof of Euclid's algorithm

In my last blog I described how to obtain the gcd (greatest common divisor) of two natural numbers by using Euclid's subtraction algorithm. I now want to prove that this algorithm always works.

Let a and b be natural numbers and let a>b. We perform the following iterations. Let
$$ a_{1}=a,        b_{1}=b    ...(1)$$  
then for each pair (a_i,b_i) we form the pair (a_i+1,b_i+1), where
$$a_{i+1}=max(b_{i},a_{i}-b_{i}),         b_{i+1}=min(b_{i},a_{i}-b_{i})   ...(2)$$
and we continue this process until
$$a_{k}=b_{k}   ...(3)$$
for some k.

Firstly, we note that for two numbers x an y, one of the following is true
$$x>y,   x=y,   x<y$$
and since the iterations in (2) only continue until (3) is true and we begin with a₁>b₁ then
$$a_{i}>b_{i}      i=1,2,...,k-1         ...(4)$$
by the construction of (a_i+1,b_i+1) in (2).

Now we show that
$$a_{i}>b_{i}>0      i=1,2,...,k-1         ...(5)$$
We know that from (1) a₁>b₁ and from (2) that a₂ is either b₁ or a₁-b₁ whichever is the greater and b₂ is b₁ or a₁-b₁ whichever is the smaller. Hence, as b₁>0 and a₁>b₁ implies a₁-b₁>0, then with (4)
$$a_{2}>b_{2}>0$$
provided k>2. By the same argument we can show that
$$a_{3}>b_{3}>0$$
provided k>3 and so on. Hence, (5) is proven.

Now let a₁ and b₁ have greatest common divisor d (a natural number), so that a₁=f₁d and b₁=g₁d, for some natural numbers f₁ and g₁. We show that
$$a_{i}=f_{i}d,      b_{i}=g_{i}d       i=1,2,...,k-1       ...(6)$$
From (2) we have that a₂ and b₂ are either b₁=g₁d or a₁-b₁=f₁d-g₁d=(f₁-g₁)d. Thus we can write a₂=f₂d and b₂=g₂d where f₂ and g₂ are either g₁ or f₁-g₁ and since
$$a_{1}-b_{1}>0\Leftrightarrow (f_{1}-g_{1})d>0\Leftrightarrow f_{1}-g_{1}>0$$
(since d>0) then f₂ and g₂ are natural numbers. Now, so long as k>2, then (5) holds and so we can repeat this argument to obtain a₃=f₃d and b₃=g₃d where f₃ and g₃ are natural numbers and so on. Hence (6) is proven.

Having laid the foundations we now come to the crux of the proof. We show that
$$a_{1}>a_{2}>...>a_{k-1}>a_{k}   ...(7)$$
and
$$b_{1}\geq b_{2}\geq ...\geq b_{k-1}\geq b_{k}   ...(8)$$
So a_i and b_i are decreasing sequences (for i=1 to k). Actually a_i is strictly decreasing. We now determine the values of a_i+1 and b_i+1 using the definition in (2). Look at the following table for i=1,2,...,k-1:

	bi>a i-bi	ai-bi>bi
ai+1	bi	ai-bi
bi+1	ai-bi	bi

This shows how a_i+1 and b_i+1 are calculated based on the relative sizes of b_i and a_i-b_i. If b_i>a_i-b_i then using (5)
$$a_{i+1}=b_{i}<a_{i}\Rightarrow a_{i+1}<a_{i}    i=1,2,...,k-1$$
and using the above table
$$b_{i+1}=a_{i}-b_{i}<b_{i}\Rightarrow b_{i+1}<b_{i}    i=1,2,...,k-1$$
On the other hand if a_i-b_i>b_i then
$$a_{i+1}=a_{i}-b_{i}<a_{i}\Rightarrow a_{i+1}<a_{i}    i=1,2,...,k-1$$
and
$$b_{i+1}=b_{i}    i=1,2,...,k-1$$
Hence (7) and (8) are proven.

Now from (6), (7) and (8) we have
$$f_{1}d>f_{2}d>...>f_{k-1}d>f_{k}d$$
and
$$g_{1}d\geq g_{2}d\geq ...\geq g_{k-1}d\geq g_{k}d$$
Hence as d>0 this implies
$$f_{1}>f_{2}>...>f_{k-1}>f_{k}$$
and
$$g_{1}\geq g_{2}\geq ...\geq g_{k-1}\geq g_{k}$$
Thus we have two decreasing sequences of natural numbers and by descent we must eventually have
$$f_{k}=g_{k}=1    ...(9)$$
for some k. Note that because the sequence g_i is not strictly decreasing more terms other than the last may be 1. It follows that k is determined by the strictly decreasing sequence f_i.

Hence (3) is proven to be true since (9) implies that
$$df_{k}=dg_{k}=d$$
and hence
$$a_{k}=b_{k}=d$$
as required.

gcd by subtraction

I am now getting into chapter 2 of Stillwell's number theory book and one of the first things I have seen is how to find the greatest common divisor (gcd) of two natural numbers using Euclid's subtraction algorithm. The greatest common divisor is equivalently known as the highest common factor (HCF) of two numbers. The OU defined the HCF of two natural numbers as "the largest number which is a factor of both or, alternatively, the product of the lowest power of each prime factor common to both" (see the OU's Revision Pack for MST121).

Let's see how this definition works. If I want the HCF of, say, 66 and 312, then breaking the numbers down into their prime factors we have 60=2²x3x5 and 312=2³x3x13. 2 and 3 are prime factors that are common to both numbers and the lowest power of 2 here is 2 and the lowest power of 3 is 1. Hence the HCF or gcd of 60 and 312 is 2²x3=12.

Now let's see how Euclid's subtraction algorithm works. Let a, b be natural numbers with a>b. We let
$$ a_{1}=a,        b_{1}=b    ...(1)$$  
Then for each (a_i,b_i) we form the pair (a_i+1,b_i+1), where
$$a_{i+1}=max(b_{i},a_{i}-b_{i}),         b_{i+1}=min(b_{i},a_{i}-b_{i})   ...(2)$$
and this is another example of descent because both a_i and b_i are decreasing sequences. Eventually,
$$a_{k}=b_{k}   ...(3)$$
for some k and we have that the gcd(a,b)=a_k=b_k.

So how does this work in practice? Taking our example from above, then we obtain the following sequence of pairs of numbers:
$$( a_{1}=312, b_{1}=60)$$
$$( a_{2}=252, b_{2}=60)$$
$$( a_{3}=192, b_{3}=60)$$
$$( a_{4}=132, b_{4}=60)$$
$$( a_{5}=72, b_{5}=60)$$
$$( a_{6}=60, b_{6}=12)$$
$$( a_{7}=48, b_{7}=12)$$
$$( a_{8}=36, b_{8}=12)$$
$$( a_{9}=24, b_{9}=12)$$
$$( a_{10}=12, b_{10}=12)$$ 
We stop at i=10 where a₁₀ and b₁₀ are equal. Hence the gcd(312,60)=12 as we have already discovered. It looks like the sequence a_i (i=1 to k) is strictly decreasing whereas the sequence b_i isn't. This in fact turns out to be the case and one of the tasks I set myself was to prove that this algorithm does indeed always work and this (lengthy) proof will be the subject of my next blog.

Very pleased

I have just seen from The Particle Physics Jedi that the OU maths results are out and I have just checked my result for M208 - distinction woopee and my mark was 99%. I just can't complain about that! Beers all round.

Progress and Plimpton 322

I have now worked through the rest of the first chapter of 'Elements of Number Theory' and some further topics were introduced, namely, Diophantine Equations, Pythagorean Triples, The Diophantus chord method and Gaussian integers.

Pythagorean triples are natural numbers (x,y,z) which are solutions of the Pythagorean equation
$$x^{2}+y^{2}=z^{2}$$

A Babylonian clay tablet called Plimpton 322 (this is its museum catalogue number) shows that such numbers were known about 3,800 years ago - a whole 1,300 years before Pythagoras! As presented in Stillwell's book, there are 15 pairs of real numbers which can be interpreted as values of y and z since z²-y² is a perfect square. Further investigation of these numbers (exercises 1.8.2 and 1.8.3 of this book) shows that six of these triples can be constructed from other smaller triples. If (a₁,b₁,c₁) and (a₂,b₂,c₂) are Pythagorean triples, then so too is (a₁a₂-b₁b₂, a₁b₂+b₁a₂,c₁c₂). This also means that a triple (a,b,c) can also generate triple (a²-b², 2ab, c²). Clearly, if we are looking for triples of this type, then the component z must not be prime.

For example, for the triple in Plimpton 322 that is (4800,4601,6649), we have 6649=61x109 (both 61 and 109 are prime), so we can have c₁=61 and c₂=109. There are two triples with these z values (60,11,61) and (91,60,109) and indeed these two triples do generate (4800,4601,6649) as you can check. Another example is the triple (240,161,289) and this can be generated from the single triple (15, 8,17) since 17²=289. Note that these two examples from Plimpton 322 are what are termed primitive triples, since their x, y and z terms do not have a common prime divisor.

It all goes to show that the Babylonians knew a thing or two about maths if they were aware of these complicated relationships.

Proof of Fibonacci's algorithm for Egyptian fractions

In my previous post I described Fibonacci's algorithm for Egyptian fractions. Here I want to go through the proof of why this algorithm always works as I think it is rather neat. This is exercise 1.2.2 of John Stillwell's 'Elements of Number Theory' and I wouldn't have got very far without being pushed in the right direction by this exercise. Note, though, that there are no solutions to the exercises in the book, so this is my own solution.

Let a, b and q be natural numbers such that
$$\frac{1}{q+1}<\frac{b}{a}<\frac{1}{q}   ...(1)$$
then 1/q is at most 1 and so it follows that b<a as we saw previously. It also follows from (1) that 1/(q+1) is the largest unit fraction less than b/a since 1/(q+1) and 1/q straddle b/a. Now
$$\frac{b}{a}-\frac{1}{q+1}=\frac{b(q+1)-a}{a(q+1)}   ...(2)$$
so let
$$b'=b(q+1)-a   ...(3)$$
and
$$a'=a(q+1)   ...(4)$$
First we show that b'>0. From (1) we have that
$$\frac{b}{a}>\frac{1}{q+1}\Leftrightarrow b(q+1)>a\Leftrightarrow b(q+1)-a>0\Leftrightarrow b'>0$$
as required. Next we show that b'<b. Also from (1) we have
$$\frac{b}{a}<\frac{1}{q}\Leftrightarrow bq<a\Leftrightarrow bq+b-a<b\Leftrightarrow b(q+1)-a<b\Leftrightarrow b'<b$$
as required. It also follows from the definitions of a' and b' and the fact that b'>0 that a' and b' are natural numbers.

Finally we show that b'<a'. From (2), (3) and (4) we have
$$\frac{b}{a}-\frac{1}{q+1}=\frac{b'}{a'}   ...(5)$$
and so
$$ \frac{b}{a}<1\Leftrightarrow \frac{b}{a}-\frac{1}{q+1}=\frac{b'}{a'}<1-\frac{1}{q+1}=\frac{q}{q+1}<1\Leftrightarrow \frac{b'}{a'}<1$$

We now demonstrate why Fibonacci's algorithm always works. Let b₁/a₁ be the initial fraction such that
$$\frac{1}{q_{1}+1}<\frac{b_{1}}{a_{1}}<\frac{1}{q_{1}}   ...(6)$$
where a₁, b₁, and q₁ are natural numbers, then 1/(q₁+1) is the largest possible unit fraction less than b₁/a₁. Thus, on the first iteration, on subtracting 1/(q₁+1) from b₁/a₁ we obtain the fraction
$$\frac{b_{1}}{a_{1}}-\frac{1}{q_{1}+1}=\frac{b_{2}}{a_{2}}   ...(7)$$
where a₂ and b₂ are natural numbers and b₂<b₁ and b₂<a₂. On the second iteration we find q₂ such that
$$\frac{1}{q_{2}+1}<\frac{b_{2}}{a_{2}}<\frac{1}{q_{2}}   ...(8)$$
then 1/(q₂+1) is the largest possible unit fraction less than b₂/a₂. Thus, on the second iteration, on subtracting 1/(q₂+1) from b₂/a₂ we obtain the fraction
$$\frac{b_{2}}{a_{2}}-\frac{1}{q_{2}+1}=\frac{b_{3}}{a_{3}}   ...(9)$$
where a₃ and b₃ are natural numbers and b₃<b₂<b₁ and b₃<a₃ and so on.

Hence, by a process of descent we must eventually end up with a b_j=1 for some j, and we have from (7), (9) etc
$$\frac{b_{1}}{a_{1}}=\frac{1}{q_{1}+1}+\frac{1}{q_{2}+1}+ ... +\frac{1}{a_{j}}   ...(10)$$

as expected. Phew! That was tricky to write out correctly!