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=22x3x5 and 312=23x3x13. 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 22x3=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 (ai,bi) we form the pair (ai+1,bi+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 ai and bi are decreasing sequences. Eventually,
$$a_{k}=b_{k} ...(3)$$
for some k and we have that the gcd(a,b)=ak=bk.
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 a10 and b10 are equal. Hence the gcd(312,60)=12 as we have already discovered. It looks like the sequence ai (i=1 to k) is strictly decreasing whereas the sequence bi 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.
Friday 30 November 2012
Tuesday 27 November 2012
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.
Monday 26 November 2012
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 z2-y2 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 (a1,b1,c1) and (a2,b2,c2) are Pythagorean triples, then so too is (a1a2-b1b2, a1b2+b1a2,c1c2). This also means that a triple (a,b,c) can also generate triple (a2-b2, 2ab, c2). 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 c1=61 and c2=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 172=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.
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 z2-y2 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 (a1,b1,c1) and (a2,b2,c2) are Pythagorean triples, then so too is (a1a2-b1b2, a1b2+b1a2,c1c2). This also means that a triple (a,b,c) can also generate triple (a2-b2, 2ab, c2). 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 c1=61 and c2=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 172=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.
Wednesday 14 November 2012
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 b1/a1 be the initial fraction such that
$$\frac{1}{q_{1}+1}<\frac{b_{1}}{a_{1}}<\frac{1}{q_{1}} ...(6)$$
where a1, b1, and q1 are natural numbers, then 1/(q1+1) is the largest possible unit fraction less than b1/a1. Thus, on the first iteration, on subtracting 1/(q1+1) from b1/a1 we obtain the fraction
$$\frac{b_{1}}{a_{1}}-\frac{1}{q_{1}+1}=\frac{b_{2}}{a_{2}} ...(7)$$
where a2 and b2 are natural numbers and b2<b1 and b2<a2. On the second iteration we find q2 such that
$$\frac{1}{q_{2}+1}<\frac{b_{2}}{a_{2}}<\frac{1}{q_{2}} ...(8)$$
then 1/(q2+1) is the largest possible unit fraction less than b2/a2. Thus, on the second iteration, on subtracting 1/(q2+1) from b2/a2 we obtain the fraction
$$\frac{b_{2}}{a_{2}}-\frac{1}{q_{2}+1}=\frac{b_{3}}{a_{3}} ...(9)$$
where a3 and b3 are natural numbers and b3<b2<b1 and b3<a3 and so on.
Hence, by a process of descent we must eventually end up with a bj=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!
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 b1/a1 be the initial fraction such that
$$\frac{1}{q_{1}+1}<\frac{b_{1}}{a_{1}}<\frac{1}{q_{1}} ...(6)$$
where a1, b1, and q1 are natural numbers, then 1/(q1+1) is the largest possible unit fraction less than b1/a1. Thus, on the first iteration, on subtracting 1/(q1+1) from b1/a1 we obtain the fraction
$$\frac{b_{1}}{a_{1}}-\frac{1}{q_{1}+1}=\frac{b_{2}}{a_{2}} ...(7)$$
where a2 and b2 are natural numbers and b2<b1 and b2<a2. On the second iteration we find q2 such that
$$\frac{1}{q_{2}+1}<\frac{b_{2}}{a_{2}}<\frac{1}{q_{2}} ...(8)$$
then 1/(q2+1) is the largest possible unit fraction less than b2/a2. Thus, on the second iteration, on subtracting 1/(q2+1) from b2/a2 we obtain the fraction
$$\frac{b_{2}}{a_{2}}-\frac{1}{q_{2}+1}=\frac{b_{3}}{a_{3}} ...(9)$$
where a3 and b3 are natural numbers and b3<b2<b1 and b3<a3 and so on.
Hence, by a process of descent we must eventually end up with a bj=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!
Saturday 10 November 2012
Fibonacci's algorithm for Egyptian fractions
I found this exercise in John Stillwell's 'Elements of Number Theory' interesting because it involves a process of descent which I have heard about but am not familiar with. The aim is to represent any fraction of the form b/a where b<a as a sum of distinct terms 1/n called unit fractions (here a, b, and n are natural numbers). Apparently the ancient Egyptians represented fractions as sums of such unit fractions in this way.
To express a fraction such as 7/15 as a sum of unit fractions we use the following method of Fibonacci. First, subtract the largest unit fraction less than 7/15 from 7/15. We have
$$\frac{7}{15}-\frac{1}{3}=\frac{2}{15} ...(1)$$
Then subtract the largest unit fraction less than 2/15 from 2/15 so
$$\frac{2}{15}-\frac{1}{8}=\frac{1}{120} ...(2)$$
Hence we can write
$$\frac{7}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}$$
and this is in the form that we want. If we consider the numerators of the fractions that are produced by this algorithm (the RHS of equations (1) and (2)) then these numerators (2 and 1 in this case) always form a strictly decreasing sequence ending in 1. I will try and show the proof of this in another blog.
Sometimes it isn't obvious what the largest unit fraction less than a fraction is but a bit of manipulation will help. Suppose we wanted the smallest n such that
$$\frac{1}{n}<\frac{3}{71}$$
then this is equivalent to
$$n>\frac{71}{3}=23\frac{2}{3}$$
So here n=24.
Notice that I have started using Mathjax to display these equations.
To express a fraction such as 7/15 as a sum of unit fractions we use the following method of Fibonacci. First, subtract the largest unit fraction less than 7/15 from 7/15. We have
$$\frac{7}{15}-\frac{1}{3}=\frac{2}{15} ...(1)$$
Then subtract the largest unit fraction less than 2/15 from 2/15 so
$$\frac{2}{15}-\frac{1}{8}=\frac{1}{120} ...(2)$$
Hence we can write
$$\frac{7}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}$$
and this is in the form that we want. If we consider the numerators of the fractions that are produced by this algorithm (the RHS of equations (1) and (2)) then these numerators (2 and 1 in this case) always form a strictly decreasing sequence ending in 1. I will try and show the proof of this in another blog.
Sometimes it isn't obvious what the largest unit fraction less than a fraction is but a bit of manipulation will help. Suppose we wanted the smallest n such that
$$\frac{1}{n}<\frac{3}{71}$$
then this is equivalent to
$$n>\frac{71}{3}=23\frac{2}{3}$$
So here n=24.
Notice that I have started using Mathjax to display these equations.
Thursday 1 November 2012
Post OU
Now that my work with the OU is over for the moment and I can relax again, I have been turning my attention back to my main interest, numbers. As I planned to do, I have begun reading Elements of Number Theory by John Stillwell and have started working through the first chapter. This is one of many books in the Undergraduate Texts in Mathematics series published by Springer. This book appealed to me because it is based on a lecture course with exercises to work through (there are no solutions mind you) and it isn't just a mass of theorems, as some books on number theory are.
Some interesting bits that I have seen so far are Fibonacci's algorithm for Egyptian fractions, the McNugget problem, binary numerals for numbers using division with remainder and some bits about Mersenne primes and perfect numbers. I might try and describe some of these topics here and show some of the nice simple proofs and properties.
For those of you who like tinkering around with computer programs and numbers I also have a blog where I describe some simple programs that I have written for a Casio programmable calculator. Have a look at http://casio-fx-50f-plus.blogspot.co.uk/.
Some interesting bits that I have seen so far are Fibonacci's algorithm for Egyptian fractions, the McNugget problem, binary numerals for numbers using division with remainder and some bits about Mersenne primes and perfect numbers. I might try and describe some of these topics here and show some of the nice simple proofs and properties.
For those of you who like tinkering around with computer programs and numbers I also have a blog where I describe some simple programs that I have written for a Casio programmable calculator. Have a look at http://casio-fx-50f-plus.blogspot.co.uk/.
Subscribe to:
Posts (Atom)