Well, contrary to everything I have said before about not continuing on with my OU studies, I have had a change of heart and have decided to see if I can finish my BSc honours maths degree that I signed up for in 2009. Why this change? Well, I realise that I do have a hankering to do something in maths and I may regret it in the future if I don't try and see how far I can get. I also realise that getting ends to meet from my current work in photography is getting harder and harder and so eventually I am going to have to do something else anyway. Coming back from a week in Berlin, I realised that I just have to give it a go, regardless of the potential difficulties of approaching the time of life when most people are thinking of retirement! Still, the government wants us all to work after retirement age, so I will be trying this out. I just hope the brain cells don't wear out before I get to the point where I can contribute something to this subject.
So having made the decision, it's all kind of exciting and daunting at the same time. The first thing is to concentrate on this degree which, due to the reorganisation of these qualifications, I now have to finish by the 31/12/17. This gives me four years and, at 60 points a year, I hope to get the additional 240 points I need to pass (I already have 120 points from MST121, MS221 and M208). There are now two routes a student can follow in this degree. Route A means following what was originally prescribed and, for me, at level 2 that would mean doing the 60 point 'Mathematical methods and models' (MST209) and the 10 point summer school 'Mathematical modelling' (MSXR209). For a number of reasons, I am going to plump for route B, which means doing the new 60 point 'Mathematical methods and models' (MST210) which does not require the summer school any more. However, this does mean that I will have to wait until October 2014 to start this course and it will also mean that I will have to do the new 30 point level 1 course 'Introducing statistics' (M140).
In the mean time I need to get another 60 points under my belt starting this October and I think the best option for me having only done M208 so far, is to do the level 3 30 point courses 'Groups and Geometry' (M336) and 'Number theory and mathematical logic' (M381). This is the final presentation of these two courses before they are replaced by 'Further pure mathematics' (M303). This new course will be available from 2014 and will be an amalgamated version of M336, M381 and the now extinct 'Topology' course (M338). I think I will be pursuing a more pure maths direction in my further studies and number theory is already something I think would like to specialise in, so it all makes good sense.
As for the remaining 90 points, I have only to do 60 more points at level 3 and 30 points from a free choice of OU modules. However, I agree with Chris that I want to squeeze in the level 3 30 point 'Complex Analysis' (M337) and at the moment this is presented on alternate years (I believe), though this could change. I expect I want to get a good grounding in both pure and applied maths in case this comes in useful, so a couple of level 3 30 point applied courses may be an option.
In the mean time it is eyes down again and time to start getting ahead to alleviate future stresses of workload. So I have already got hold of some of the books for the 'Number theory and mathematical logic' course and have started on the first book. It looks like some of this will already be covered by my reading of John Stillwell's book, which I am still making some progress on, so that's all well and good.
Tuesday, 26 March 2013
Friday, 15 February 2013
Using group theory to prove Fermat's little theorem
Here is a demonstration of the use of group theory that I thought was quite neat. Fermat's little theorem states that if p is a prime number and a is a natural number that is not divisible by p (i.e. a is not congruent to 0 (mod p)) then
$$a^{p-1}\equiv 1 \;\mbox{(mod p) ...(1) }$$
Now recall from M208 that if p is prime then
$$(Z^{*}_{p},\times_{p})$$
is a group of order p-1 (see the Handbook for M208 on page 30). Now we can use Lagrange's Theorem (Handbook page 35) to prove Fermat's little theorem as follows. Let a be a natural number that is not divisible by a prime number p, then a will be congruent to an element of the above group, i.e. to one of the set
$$\left\{1,2,3,..,(p-1)\right\}$$
Let this element be g so that
$$a\equiv g \;\mbox{(mod p)}$$
Now g will generate a cyclic subgroup of order n (Handbook page 28) and by Lagrange's Theorem (page 35) n will divide p-1, the order of the group. Hence
$$p-1=mn$$
for some natural number m and thus
$$a^{p-1}\equiv g^{p-1}\equiv g^{mn}\equiv(g^{n})^{m}\;\mbox{(mod p)}$$
Now by definition
$$g^{n}\equiv 1 \;\mbox{(mod p)}$$
and so
$$a^{p-1}\equiv 1^{m}\equiv 1\;\mbox{(mod p)}$$
Hence (1) is proven.
$$a^{p-1}\equiv 1 \;\mbox{(mod p) ...(1) }$$
Now recall from M208 that if p is prime then
$$(Z^{*}_{p},\times_{p})$$
is a group of order p-1 (see the Handbook for M208 on page 30). Now we can use Lagrange's Theorem (Handbook page 35) to prove Fermat's little theorem as follows. Let a be a natural number that is not divisible by a prime number p, then a will be congruent to an element of the above group, i.e. to one of the set
$$\left\{1,2,3,..,(p-1)\right\}$$
Let this element be g so that
$$a\equiv g \;\mbox{(mod p)}$$
Now g will generate a cyclic subgroup of order n (Handbook page 28) and by Lagrange's Theorem (page 35) n will divide p-1, the order of the group. Hence
$$p-1=mn$$
for some natural number m and thus
$$a^{p-1}\equiv g^{p-1}\equiv g^{mn}\equiv(g^{n})^{m}\;\mbox{(mod p)}$$
Now by definition
$$g^{n}\equiv 1 \;\mbox{(mod p)}$$
and so
$$a^{p-1}\equiv 1^{m}\equiv 1\;\mbox{(mod p)}$$
Hence (1) is proven.
Sunday, 3 February 2013
Why is the sun hot?
This is a slight departure from my usual posts here but I wanted to counter something that appears in the course notes for S382 Astrophysics and in the book "Stellar Evolution and Nucleosynthesis" which I think is misleading. Dan has raised the subject of 'Why is the sun hot' in his blog and I want to discuss some of the issues that have been raised here rather than trashing his blog with lots of comments.
First I am going to quote some bits and pieces from "Stellar Evolution and Nucleosynthesis" by Ryan and Norton. In chapter 2 of their book on page 46 they have a section 2.6 entitled "Why are stars hot? Putting fusion in its place". They say:-
"In Chapter 1 you saw that hydrogen fusion provides the power that is radiated by the Sun and other main-sequence stars. In this Chapter, you have seen the importance of the gravitation energy released by a collapsing cloud of gas. In order to understand the roles of these two sources of energy, before we go any further, we pause to consider exactly what fusion is and is not responsible for."
They go on to discuss how much energy is released per cubic metre in the core of the Sun by nuclear fusion and this turns out to be about 300 Watts.
They go on to say:-
"Think about this number: 300 Wm-3. Imagine putting three 100 W lightbulbs in a broom cupboard whose volume is about 1 cubic metre. Would that make the cupboard as bright and hot as the Sun?"
"No, clearly it would not. In fact, 300 W seems like a pathetically tiny power output for a volume as large as 1m3, especially in something as hot as the core of the Sun! Is the calculation grossly wrong? No, the power output per cubic metre is that small. Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse! (But it is a big reservoir!)"
After some further number crunching the books says:
"You might be tempted at this stage to think that, even though the power released in fusion is very small, the energy released heats up the core of a star, and this is why stars are hot. The energy released is indeed very important, but it is not the reason that stars heat up. In fact the opposite is true; fusion prevents a star from getting hotter!"
"In fact, a star's temperature and luminosity are not determined by nuclear burning. However, they are maintained by nuclear burning. Nuclear fusion replenishes the slow leakage of energy from the star's core and eventually from its surface. As you saw in the last Section, the release of gravitational potential energy can do exactly the same thing, but the nuclear fusion energy source has the advantage that it lasts for much longer. That is, nuclear fusion greatly delays the gravitational collapse of the star."
"If someone had asked you at the beginning of this book, 'What makes stars hot?', you could have been forgiven for answering 'It is because they have thermonuclear reaction in their cores.' That answer sounds plausible, but hopefully now you can see that it is incorrect. Stars are hot because they have collapsed from large diffuse clouds and gravitational potential energy has been converted to kinetic energy. That is why stars are hot."
I think that the above discussion and conclusion are very misleading. You could come away with the idea that nuclear fusion in the Sun is not an important source of its energy output ("Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse") but that release of energy from gravitational potential energy is ("the release of gravitational potential energy can do exactly the same thing"). This is of course, incorrect.
The question that needs to be asked is this. Would the Sun be hot now after having existed for approximately 4.6 billion years if nuclear reactions weren't taking place in its core? The answer to this is no. If there was no other energy source in the Sun apart from the release of gravitational potential energy, then at its current luminosity it would only shine for approximately 18 million years , a time-scale that is about 256 times too short. It follows then that the Sun would have cooled to well below its current temperature by now if heating by contraction was its only source of energy. We know, anyway, that the Sun is in equilibrium, which means that it is neither contracting nor expanding. You can't have energy released by gravitational potential if the Sun isn't contracting.
The argument about the three 100 Watt light bulbs in a cupboard is also misleading ("Would that make the cupboard as bright and hot as the Sun? No clearly, it would not!"). The cupboard could get as bright as the surface of the Sun and even as high as the core of the Sun, if the cupboard was perfectly insulated. This is how an ideal oven would work. In fact, I find the langauge used by the authors ("300 W seems like a pathetically tiny power output for a volume as large as 1m3") emotive and inappropriate for a science text.
So is nuclear fusion in the Sun much of a powerhouse? Yes, it is. Although of 300 Watts per metre cubed sounds like a small number it is sufficient to power the output of the Sun for billions of years and maintain the temperature in its core for the duration.
So why is the Sun hot? I would argue it is hot for both of the reasons discussed, neither of which can be disentagled or discounted. The collapse of the gas cloud that led to the formation of the Sun was responsible for getting the core of the Sun up to a temperature where nuclear fusion could take place and nuclear fusion is responsible for maintaining that temperature of the Sun, in both the core and on its surface, until now. To overemphasise the role of gravitational energy in the way that these authors have done in their book is, in my opinion, very misleading and it is disappointing if this is also true of the course notes for the OU Astrophysics course.
First I am going to quote some bits and pieces from "Stellar Evolution and Nucleosynthesis" by Ryan and Norton. In chapter 2 of their book on page 46 they have a section 2.6 entitled "Why are stars hot? Putting fusion in its place". They say:-
"In Chapter 1 you saw that hydrogen fusion provides the power that is radiated by the Sun and other main-sequence stars. In this Chapter, you have seen the importance of the gravitation energy released by a collapsing cloud of gas. In order to understand the roles of these two sources of energy, before we go any further, we pause to consider exactly what fusion is and is not responsible for."
They go on to discuss how much energy is released per cubic metre in the core of the Sun by nuclear fusion and this turns out to be about 300 Watts.
They go on to say:-
"Think about this number: 300 Wm-3. Imagine putting three 100 W lightbulbs in a broom cupboard whose volume is about 1 cubic metre. Would that make the cupboard as bright and hot as the Sun?"
"No, clearly it would not. In fact, 300 W seems like a pathetically tiny power output for a volume as large as 1m3, especially in something as hot as the core of the Sun! Is the calculation grossly wrong? No, the power output per cubic metre is that small. Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse! (But it is a big reservoir!)"
After some further number crunching the books says:
"You might be tempted at this stage to think that, even though the power released in fusion is very small, the energy released heats up the core of a star, and this is why stars are hot. The energy released is indeed very important, but it is not the reason that stars heat up. In fact the opposite is true; fusion prevents a star from getting hotter!"
"In fact, a star's temperature and luminosity are not determined by nuclear burning. However, they are maintained by nuclear burning. Nuclear fusion replenishes the slow leakage of energy from the star's core and eventually from its surface. As you saw in the last Section, the release of gravitational potential energy can do exactly the same thing, but the nuclear fusion energy source has the advantage that it lasts for much longer. That is, nuclear fusion greatly delays the gravitational collapse of the star."
"If someone had asked you at the beginning of this book, 'What makes stars hot?', you could have been forgiven for answering 'It is because they have thermonuclear reaction in their cores.' That answer sounds plausible, but hopefully now you can see that it is incorrect. Stars are hot because they have collapsed from large diffuse clouds and gravitational potential energy has been converted to kinetic energy. That is why stars are hot."
I think that the above discussion and conclusion are very misleading. You could come away with the idea that nuclear fusion in the Sun is not an important source of its energy output ("Clearly hydrogen burning by the proton-proton chain is not much of a powerhouse") but that release of energy from gravitational potential energy is ("the release of gravitational potential energy can do exactly the same thing"). This is of course, incorrect.
The question that needs to be asked is this. Would the Sun be hot now after having existed for approximately 4.6 billion years if nuclear reactions weren't taking place in its core? The answer to this is no. If there was no other energy source in the Sun apart from the release of gravitational potential energy, then at its current luminosity it would only shine for approximately 18 million years , a time-scale that is about 256 times too short. It follows then that the Sun would have cooled to well below its current temperature by now if heating by contraction was its only source of energy. We know, anyway, that the Sun is in equilibrium, which means that it is neither contracting nor expanding. You can't have energy released by gravitational potential if the Sun isn't contracting.
The argument about the three 100 Watt light bulbs in a cupboard is also misleading ("Would that make the cupboard as bright and hot as the Sun? No clearly, it would not!"). The cupboard could get as bright as the surface of the Sun and even as high as the core of the Sun, if the cupboard was perfectly insulated. This is how an ideal oven would work. In fact, I find the langauge used by the authors ("300 W seems like a pathetically tiny power output for a volume as large as 1m3") emotive and inappropriate for a science text.
So is nuclear fusion in the Sun much of a powerhouse? Yes, it is. Although of 300 Watts per metre cubed sounds like a small number it is sufficient to power the output of the Sun for billions of years and maintain the temperature in its core for the duration.
So why is the Sun hot? I would argue it is hot for both of the reasons discussed, neither of which can be disentagled or discounted. The collapse of the gas cloud that led to the formation of the Sun was responsible for getting the core of the Sun up to a temperature where nuclear fusion could take place and nuclear fusion is responsible for maintaining that temperature of the Sun, in both the core and on its surface, until now. To overemphasise the role of gravitational energy in the way that these authors have done in their book is, in my opinion, very misleading and it is disappointing if this is also true of the course notes for the OU Astrophysics course.
Tuesday, 29 January 2013
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!
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!
Wednesday, 19 December 2012
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 (ai,bi) we form pair (ai+1,bi+1) as follows:
$$a_{i+1}=b_{i}, b_{i+1}=r_{i}$$
where ri is the remainder when ai is divided by bi. The process is stopped when bk divides ak for some k in which case gcd(a,b)=bk.
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 Z25={0,1,2,...,24}, that is the element x of Z25 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 Z25 but
$$-11\equiv 14\:(\mbox{mod }25)$$
Thus
$$9\times_{25} 14=1$$
and so x is 14.
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 (ai,bi) we form pair (ai+1,bi+1) as follows:
$$a_{i+1}=b_{i}, b_{i+1}=r_{i}$$
where ri is the remainder when ai is divided by bi. The process is stopped when bk divides ak for some k in which case gcd(a,b)=bk.
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 Z25={0,1,2,...,24}, that is the element x of Z25 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 Z25 but
$$-11\equiv 14\:(\mbox{mod }25)$$
Thus
$$9\times_{25} 14=1$$
and so x is 14.
Friday, 7 December 2012
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 (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 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 a1>b1 then
$$a_{i}>b_{i} i=1,2,...,k-1 ...(4)$$
by the construction of (ai+1,bi+1) in (2).
Now we show that
$$a_{i}>b_{i}>0 i=1,2,...,k-1 ...(5)$$
We know that from (1) a1>b1 and from (2) that a2 is either b1 or a1-b1 whichever is the greater and b2 is b1 or a1-b1 whichever is the smaller. Hence, as b1>0 and a1>b1 implies a1-b1>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 a1 and b1 have greatest common divisor d (a natural number), so that a1=f1d and b1=g1d, for some natural numbers f1 and g1. We show that
$$a_{i}=f_{i}d, b_{i}=g_{i}d i=1,2,...,k-1 ...(6)$$
From (2) we have that a2 and b2 are either b1=g1d or a1-b1=f1d-g1d=(f1-g1)d. Thus we can write a2=f2d and b2=g2d where f2 and g2 are either g1 or f1-g1 and since
$$a_{1}-b_{1}>0\Leftrightarrow (f_{1}-g_{1})d>0\Leftrightarrow f_{1}-g_{1}>0$$
(since d>0) then f2 and g2 are natural numbers. Now, so long as k>2, then (5) holds and so we can repeat this argument to obtain a3=f3d and b3=g3d where f3 and g3 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 ai and bi are decreasing sequences (for i=1 to k). Actually ai is strictly decreasing. We now determine the values of ai+1 and bi+1 using the definition in (2). Look at the following table for i=1,2,...,k-1:
This shows how ai+1 and bi+1 are calculated based on the relative sizes of bi and ai-bi. If bi>ai-bi 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 ai-bi>bi 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 gi is not strictly decreasing more terms other than the last may be 1. It follows that k is determined by the strictly decreasing sequence fi.
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.
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 (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 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 a1>b1 then
$$a_{i}>b_{i} i=1,2,...,k-1 ...(4)$$
by the construction of (ai+1,bi+1) in (2).
Now we show that
$$a_{i}>b_{i}>0 i=1,2,...,k-1 ...(5)$$
We know that from (1) a1>b1 and from (2) that a2 is either b1 or a1-b1 whichever is the greater and b2 is b1 or a1-b1 whichever is the smaller. Hence, as b1>0 and a1>b1 implies a1-b1>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 a1 and b1 have greatest common divisor d (a natural number), so that a1=f1d and b1=g1d, for some natural numbers f1 and g1. We show that
$$a_{i}=f_{i}d, b_{i}=g_{i}d i=1,2,...,k-1 ...(6)$$
From (2) we have that a2 and b2 are either b1=g1d or a1-b1=f1d-g1d=(f1-g1)d. Thus we can write a2=f2d and b2=g2d where f2 and g2 are either g1 or f1-g1 and since
$$a_{1}-b_{1}>0\Leftrightarrow (f_{1}-g_{1})d>0\Leftrightarrow f_{1}-g_{1}>0$$
(since d>0) then f2 and g2 are natural numbers. Now, so long as k>2, then (5) holds and so we can repeat this argument to obtain a3=f3d and b3=g3d where f3 and g3 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 ai and bi are decreasing sequences (for i=1 to k). Actually ai is strictly decreasing. We now determine the values of ai+1 and bi+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 ai+1 and bi+1 are calculated based on the relative sizes of bi and ai-bi. If bi>ai-bi 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 ai-bi>bi 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 gi is not strictly decreasing more terms other than the last may be 1. It follows that k is determined by the strictly decreasing sequence fi.
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.
Friday, 30 November 2012
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=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.
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.
Subscribe to:
Posts (Atom)