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.
Wednesday, 19 December 2012
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.
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/.
Thursday, 18 October 2012
All but for the loss of a factor of n cubed
Well the exam has been and gone and I am pleased about that. It didn't help that on Tuesday I started to get a sore throat which turned into a cold on the day. There was no way I wasn't going to turn up for the exam even though I felt pretty rough in the morning and I hadn't slept that well the night before. In fact it may, in an odd way, have helped, since I stopped worrying about my performance and was just hoping for the best under difficult circumstances.
I took the same approach to this exam as I did for MS221; namely I started with question 1 and worked steadily through Part 1 in the order of the questions. I find this is a good technique. You slowly tick them off one by one, making sure that you get these easier questions well and truly nailed and then you get that growing confidence you can deal with the more difficult section later. My timings were good and I had over an hour left by the time I had finished the last question in Part 1 and I felt as if I hadn't made a mistake yet.
Part 2. An easy (but time consuming) symmetric groups question was an obvious first choice. Worked steadily through it and it was done without a hitch. Now the exam was nearly finished so I headed for my favourite topic in analysis, series - answering this question can be a pain, but it is straightforward. First part ok, second part "bing, bing, bing" something has gone wrong but I couldn't see what it was. I mistakenly thought I had used the wrong approach. Left it and completed the other two parts ok. Five minutes left. I went back to the second part but I couldn't see the problem, so I completed it anyway, saying what I knew to be wrong. Time up! How irritating. So close to being totally happy!
Afterwards I realised what I had done. I had dropped a factor of n3 and I hadn't seen it in time. Oh well. I thought it was a good paper as there weren't any nasty surprises. Before the exam I was reflecting on all the difficult things they could ask which hadn't been covered by my practise of recent papers but it didn't happen. I think the general consensus was that people were happy. I left with my tutor group and we went for a celebratory drink at Diggers and I had two medicinal malt whiskies to wash that cold away!
I took the same approach to this exam as I did for MS221; namely I started with question 1 and worked steadily through Part 1 in the order of the questions. I find this is a good technique. You slowly tick them off one by one, making sure that you get these easier questions well and truly nailed and then you get that growing confidence you can deal with the more difficult section later. My timings were good and I had over an hour left by the time I had finished the last question in Part 1 and I felt as if I hadn't made a mistake yet.
Part 2. An easy (but time consuming) symmetric groups question was an obvious first choice. Worked steadily through it and it was done without a hitch. Now the exam was nearly finished so I headed for my favourite topic in analysis, series - answering this question can be a pain, but it is straightforward. First part ok, second part "bing, bing, bing" something has gone wrong but I couldn't see what it was. I mistakenly thought I had used the wrong approach. Left it and completed the other two parts ok. Five minutes left. I went back to the second part but I couldn't see the problem, so I completed it anyway, saying what I knew to be wrong. Time up! How irritating. So close to being totally happy!
Afterwards I realised what I had done. I had dropped a factor of n3 and I hadn't seen it in time. Oh well. I thought it was a good paper as there weren't any nasty surprises. Before the exam I was reflecting on all the difficult things they could ask which hadn't been covered by my practise of recent papers but it didn't happen. I think the general consensus was that people were happy. I left with my tutor group and we went for a celebratory drink at Diggers and I had two medicinal malt whiskies to wash that cold away!
Thursday, 20 September 2012
Straight 100s
Well I managed to do it. Today I received my assessment back for TMA07, the last in this course, and I scored 100/100. That means I have got a straight 100's for all my M208 TMA's and I feel that I have managed to achieve something here. Even if I don't do very well in the exam, at least I can look back at this and say "I did do this!". I am very happy!
Wednesday, 19 September 2012
Up and Down
Last week I started working though M208's specimen paper and I found it quite hard going. I can't face sitting down to 3 hours of work at one go, so I have been doing a question at a time and timing myself. It was a bit of an eye opener. The first 12 questions (part 1) carry 70 percent of the marks and ideally I would like to spend 10 mins each on these questions leaving an hour for the longer part 2 questions. However my timings varied from 7 mins up to 23 mins and one question I had to abandon because I got in a stew over it. The need for speed also caused some terrible errors. I then went on to do questions 13 and 14 and came a cropper in both as I couldn't complete them and was lost as to what to do.
So a bit of a dip in my confidence followed! I had a rethink about my approach and decided that accuracy and "more haste less speed" was required. So this week I have begun the part 1 questions from the 2007 paper and things have improved a bit. Timings are much the same but the accuracy has got better and I think this is the best I can hope for. If I can get through all of the part 1 questions and have a good stab at one part 2 question then I will be happy. So confidence has gone up a bit again.
The problem with trying to speed up is that once you start to make mistakes, you start to doubt yourself and what you are doing. As panic starts to creep in, so your mind tends to go blank and it all becomes a muddle. My attitude then will be one step at a time and to stay focused and hope that I can keep this up for 3 hours, much like I did for MS221.
So a bit of a dip in my confidence followed! I had a rethink about my approach and decided that accuracy and "more haste less speed" was required. So this week I have begun the part 1 questions from the 2007 paper and things have improved a bit. Timings are much the same but the accuracy has got better and I think this is the best I can hope for. If I can get through all of the part 1 questions and have a good stab at one part 2 question then I will be happy. So confidence has gone up a bit again.
The problem with trying to speed up is that once you start to make mistakes, you start to doubt yourself and what you are doing. As panic starts to creep in, so your mind tends to go blank and it all becomes a muddle. My attitude then will be one step at a time and to stay focused and hope that I can keep this up for 3 hours, much like I did for MS221.
Wednesday, 29 August 2012
Not long now
It has been over a month since I last posted anything here and I thought it was time for an update. The course itself is drawing to a close as, by now, we should have finished all the coursework (bar the last two TMA's). As such I am beginning to feel that slight frisson of anxiety about the impending exam in October and it is starting to get me interested in past papers.
One of the things I did do in the last week or so was to read through the specimen exam paper carefully and see if there were questions that I didn't know how to approach. This was quite useful as it highlighted some holes in my knowledge about infinite quotient groups, which I have since rectified. Also, if there are methods which I suddenly think to myself "how the hell do you do that again" I have been looking them up and adding yet more examples and notes to my handbook. One of these was the counting theorem which I would like to get off pat before the exam and I think I will have to test myself with some examples.
Generally things are going ok. I am keeping up my 100% score on the TMA's which keeps me happy and I am still ploughing on with the further questions in the course text. I stopped doing these at random and instead went for the more consistent approach of tackling a block at a time. I have done about half the questions now and they keep highlighting areas where the material hasn't sunk in very far. Strangely enough, the material I feel most comfortable with is analysis as I think I have a good feel for what's involved. Some parts of group theory and linear algebra still have the ability to cause me problems. Ideally, when I get to the exam, I would like to feel that there was no part of the paper that I couldn't do, so that it gives me confidence right from the start. I think my game plan for the first 12 questions will be to do them in order as I did in MS221. It will mean I can avoid wasting time deciding which to do first. I can't wait until around mid September when I will start doing the past papers properly and really testing out my knowledge.
One of the things I did do in the last week or so was to read through the specimen exam paper carefully and see if there were questions that I didn't know how to approach. This was quite useful as it highlighted some holes in my knowledge about infinite quotient groups, which I have since rectified. Also, if there are methods which I suddenly think to myself "how the hell do you do that again" I have been looking them up and adding yet more examples and notes to my handbook. One of these was the counting theorem which I would like to get off pat before the exam and I think I will have to test myself with some examples.
Generally things are going ok. I am keeping up my 100% score on the TMA's which keeps me happy and I am still ploughing on with the further questions in the course text. I stopped doing these at random and instead went for the more consistent approach of tackling a block at a time. I have done about half the questions now and they keep highlighting areas where the material hasn't sunk in very far. Strangely enough, the material I feel most comfortable with is analysis as I think I have a good feel for what's involved. Some parts of group theory and linear algebra still have the ability to cause me problems. Ideally, when I get to the exam, I would like to feel that there was no part of the paper that I couldn't do, so that it gives me confidence right from the start. I think my game plan for the first 12 questions will be to do them in order as I did in MS221. It will mean I can avoid wasting time deciding which to do first. I can't wait until around mid September when I will start doing the past papers properly and really testing out my knowledge.
Monday, 16 July 2012
Further Exercises
After a two-week holiday at the beginning of June in Germany, I have slowly got back into the swing of things in the last three weeks by starting to do the further exercises in M208. I have been attempting to do these questions with only the aid of the handbook and nothing else, just as we will be expected to do in the exam. For the most part, I seem to be managing ok but it is clear that the handbook is sometimes a bit turgid when you are trying to figure out how to answer a question and additional underlinings and notes seem essential. And yes, I must admit, that in some cases I have written out complete answers to particular questions in the back. Why? Well, either I have a complete mental block over some questions, and I need this sort of example to assist me, or the required answer has such detail that I need a template to refer to.
So I have complete answers written out for 1) finding the image of a function (mental block), 2) proving the continuity of a function using the epsilon-delta definition (template), 3) proving something by mathematical induction (template) 4) (orthogonally) diagonalising a matrix (template) and 5) finding the image of a homomorphism (mental block). I am sure there will be others. So is it cheating? Well, you are allowed to do this, so my view is that it isn't and you should grasp every opportunity that is offered.
Occasionally there are some interesting problems in these further exercises. Take for example GTA3 Ex 4.8. I hope the OU doesn't mind if I quote the question - (a) Write down an element of (the symmetric group) S5 of order 6 and hence find a cyclic subgroup of S5 of order 6 (b) Given that S5 contains exactly 20 permutations of order 6, find the number of cyclic subgroups of S5 of order 10. I liked this question because it really made me think and I was quite pleased with myself when I figured it out!
I notice that some of my other fellow students are spending time writing stuff out on cards, memorising theorems etc. I just can't force myself to do this, although I wish I was that well organised. Instead, I am relying on practise and that unarguably helpful organ, my gut (!) which keeps me informed about how it thinks a question should be answered!! I hope it doesn't fail me in the exam.
So I have complete answers written out for 1) finding the image of a function (mental block), 2) proving the continuity of a function using the epsilon-delta definition (template), 3) proving something by mathematical induction (template) 4) (orthogonally) diagonalising a matrix (template) and 5) finding the image of a homomorphism (mental block). I am sure there will be others. So is it cheating? Well, you are allowed to do this, so my view is that it isn't and you should grasp every opportunity that is offered.
Occasionally there are some interesting problems in these further exercises. Take for example GTA3 Ex 4.8. I hope the OU doesn't mind if I quote the question - (a) Write down an element of (the symmetric group) S5 of order 6 and hence find a cyclic subgroup of S5 of order 6 (b) Given that S5 contains exactly 20 permutations of order 6, find the number of cyclic subgroups of S5 of order 10. I liked this question because it really made me think and I was quite pleased with myself when I figured it out!
I notice that some of my other fellow students are spending time writing stuff out on cards, memorising theorems etc. I just can't force myself to do this, although I wish I was that well organised. Instead, I am relying on practise and that unarguably helpful organ, my gut (!) which keeps me informed about how it thinks a question should be answered!! I hope it doesn't fail me in the exam.
Thursday, 7 June 2012
Getting into revision mode
I have now got into revision mode by working on the further exercises of the course. There are about 100 sections in all with these additional exercises and so there is plenty to do. As planned, I am doing these at random - literally, as I am using a calculator to generate a random number which indicates which section I should tackle next. This avoids me favouring certain sections and avoiding others. It also means that I get used to working on any part of the course rather than just one particular bit. I am also working with just the Handbook and if I think it doesn't give me what I need I am adding extra notes (and this happens quite a bit).
I have now completed all the TMAs and am in the process of writing up the last two in neat. I did well on TMA03 scoring another 100%. I keep thinking that I must make a mistake at some point. I have to keep pinching myself when I think that I only dropped one mark in the TMA/CMAs for MST121 and none in the TMAs for MS221 and now I haven't yet dropped a mark for M208. It'll all end in tears at some point!!
This leads me to think sometimes that I have missed my vocation. The problem is that it is all too late now. If I wanted to take it all further, it would mean another 3 years or so of a degree, then some sort of masters or PhD, by which time I would be pushing late 50's. Who would want to give me a job then and how much would I realistically expect to achieve? I should have done this all 10 or 20 years ago.
Ach, well, I can still study. I have just acquired another book on number theory in a sale at Blackwells. This is Elements of Number Theory by John Stillwell. It looks more approachable than some of the other number theory books and it may get me deeper into this subject. Edinburgh library has a good selection of books and I was surprised to find such a technical book as A first course in general relativity by Bernard F. Schutz. I couldn't resist taking it out on loan even though I know I will probably only read a few pages. If only I had more hours in the day!
I have now completed all the TMAs and am in the process of writing up the last two in neat. I did well on TMA03 scoring another 100%. I keep thinking that I must make a mistake at some point. I have to keep pinching myself when I think that I only dropped one mark in the TMA/CMAs for MST121 and none in the TMAs for MS221 and now I haven't yet dropped a mark for M208. It'll all end in tears at some point!!
This leads me to think sometimes that I have missed my vocation. The problem is that it is all too late now. If I wanted to take it all further, it would mean another 3 years or so of a degree, then some sort of masters or PhD, by which time I would be pushing late 50's. Who would want to give me a job then and how much would I realistically expect to achieve? I should have done this all 10 or 20 years ago.
Ach, well, I can still study. I have just acquired another book on number theory in a sale at Blackwells. This is Elements of Number Theory by John Stillwell. It looks more approachable than some of the other number theory books and it may get me deeper into this subject. Edinburgh library has a good selection of books and I was surprised to find such a technical book as A first course in general relativity by Bernard F. Schutz. I couldn't resist taking it out on loan even though I know I will probably only read a few pages. If only I had more hours in the day!
Saturday, 19 May 2012
TMA06
I have now completed TMA06 and just have to write it up neat. There weren't any nasty surprises in this TMA and it all pretty much fell into place. One thing I found, though, was that the answers to the exercises for the AB books tended to make more assumptions about continuity and the behaviour of limits. I wanted to follow this example but found that I wasn't always happy making these assumptions. In the end I decided to add an appendix to my answers where I proved some of the assumptions I was making. Not surprisingly some of these proofs were nearly as long as the answers themselves, which probably explains why assumptions have started to creep into the text.
Wanting to get all the course work out of the way I have started TMA07. The first question was a bit of a tease which surprised me a bit, but I saw the light in the end.
I have started reading a few books now that I have more time. One is "Einstein, A Life in Science" by John Gribbin and Michael White and the other is "The Millennium Problems - the seven greatest unsolved mathematical puzzles of our time" by Kevin Devlin. The Einstein book is a biography and I enjoy these type of books. It is clear that the young Einstein didn't like authority, tended to avoid lectures at University and only wanted to study things that interested him. It is fortunate for us that this didn't ultimately affect his career!
The Millennium Problems interest me. In 2000 the Clay Mathematics Institute decided to offer seven $1 million prizes for those who could solve seven of the most currently difficult outstanding problems of current mathematical research. This was a bit like the 23 problems outlined by David Hilbert in 1900. One of the Millennium Problems, the Poincare Conjecture, has already been solved by Grigori Perelman but he rejected the prize! The problem that interests me the most is the Riemann Hypothesis because this is related to prime numbers.
Wanting to get all the course work out of the way I have started TMA07. The first question was a bit of a tease which surprised me a bit, but I saw the light in the end.
I have started reading a few books now that I have more time. One is "Einstein, A Life in Science" by John Gribbin and Michael White and the other is "The Millennium Problems - the seven greatest unsolved mathematical puzzles of our time" by Kevin Devlin. The Einstein book is a biography and I enjoy these type of books. It is clear that the young Einstein didn't like authority, tended to avoid lectures at University and only wanted to study things that interested him. It is fortunate for us that this didn't ultimately affect his career!
The Millennium Problems interest me. In 2000 the Clay Mathematics Institute decided to offer seven $1 million prizes for those who could solve seven of the most currently difficult outstanding problems of current mathematical research. This was a bit like the 23 problems outlined by David Hilbert in 1900. One of the Millennium Problems, the Poincare Conjecture, has already been solved by Grigori Perelman but he rejected the prize! The problem that interests me the most is the Riemann Hypothesis because this is related to prime numbers.
Thursday, 10 May 2012
The End
I have reached the end of the text for M208, so that's quite a milestone reached, and I won't have to tackle any new material from now on. I started working on M208 back in mid February 2011 and so it has taken me a year and three months to read through what should really take eight months, so I have been going at roughly half speed. I haven't done the further exercises yet, but I have read and worked through nearly every proof and, believe me, that was quite a chore. On the last book I gave up with reading the very last optional proof as I just couldn't be bothered!
I enjoyed AB4 on Power Series. It was a nice amble through Taylor polynomials, Taylor's Theorem, Taylor Series and manipulating power series. Nothing too difficult and all fairly straightforward, so it maybe a topic to choose in the exam.
So what now? Well, there is TMA06 and 07 to do. That will be my first priority. Then I will be keeping things ticking over for a while by doing the further exercises. I plan to do these at random, so that I have to practise working from different parts of the course at the same time. I will also just try and work from the Handbook and see how I get on. I suspect that at this stage I will be adding a few extra notes to this where I think there isn't enough information to get me going on a question. Then sometime around late August I will start turning my attention to past exam papers and practise getting questions answered quickly and honing those skills ready for the exam in October.
I have already started think about what I might do next and this probably won't involve the OU for now. I intend to start another blog about my own explorations into prime numbers. I have also thought that I might begin trying to understand some chapters from 'An Introduction to the Theory of Numbers' by Hardy and Wright. Then another avenue for me is, perhaps, to get to grips with Special Relativity which I felt I never really did when I was a physics undergraduate. The thing is there are so many choices of things to do that I will probably not know where to start! I still have all my undergraduate text books and it is tempting to delve into Quantum Mechanics again, or Electromagnetism, or perhaps finally sit down to 'Gravitation' by Misner, Thorne and Wheeler!
I enjoyed AB4 on Power Series. It was a nice amble through Taylor polynomials, Taylor's Theorem, Taylor Series and manipulating power series. Nothing too difficult and all fairly straightforward, so it maybe a topic to choose in the exam.
So what now? Well, there is TMA06 and 07 to do. That will be my first priority. Then I will be keeping things ticking over for a while by doing the further exercises. I plan to do these at random, so that I have to practise working from different parts of the course at the same time. I will also just try and work from the Handbook and see how I get on. I suspect that at this stage I will be adding a few extra notes to this where I think there isn't enough information to get me going on a question. Then sometime around late August I will start turning my attention to past exam papers and practise getting questions answered quickly and honing those skills ready for the exam in October.
I have already started think about what I might do next and this probably won't involve the OU for now. I intend to start another blog about my own explorations into prime numbers. I have also thought that I might begin trying to understand some chapters from 'An Introduction to the Theory of Numbers' by Hardy and Wright. Then another avenue for me is, perhaps, to get to grips with Special Relativity which I felt I never really did when I was a physics undergraduate. The thing is there are so many choices of things to do that I will probably not know where to start! I still have all my undergraduate text books and it is tempting to delve into Quantum Mechanics again, or Electromagnetism, or perhaps finally sit down to 'Gravitation' by Misner, Thorne and Wheeler!
Sunday, 29 April 2012
Last book
Well, I am finally on the last book of M208, AB4, which is on power series and I am excited by the prospect of nearly completing my studies of this course. Once I have finished this book, I just have TMA06 and 7 to do and the exam in October. I have made a start on TMA06 and 7 is based on the whole course.
AB3 on integration didn't represent too much of a problem. There was some discussion of integration techniques, reduction formulae, inequalities, Wallis' formula and Stirling's formula. I am glad to see that finally in M208 for a substitution of u=x2 they don't shy away from writing du=2xdx as a way of rewriting an integral. It makes me laugh that this should appear in the 'rigorous' realms of M208 but scrupulously avoided in the 'less rigorous' earlier courses of MST121 and MS221.
In the last couple of weeks I have been asking other people if they read the proofs in M208 and it seems that they don't (see my previous post). This supports my opinion that M208 could have been written differently and perhaps it would have been better to have put the proofs at the back in an appendix. So, unless you are of the conscientious type or particularly keen then the most important thing is to get an idea of what the theorems are and to try and use them.
I have also been agitating on the forum about the lack of interest in errata. Here is what I said:
------------------------------------------------------------------
I am sure I read somewhere in the blurb when I first started doing these maths courses that the OU liked students to report any errata that they found in the text and this was what the OU regarded as being a 'model student'.
Yes, I am correct. Here is a quote from the back of the pink pages for MST121:
"Some handy hints on how to be a model student!"
"Think you've found a mistake? Check the Stop Press and the course website to see if it's mentioned there. If not give your tutor a ring. You may save other students a great deal of heartache!"
I have always taken this advice seriously and I am a keen nitpicker. One of the reasons for this is that if I find something in the text that jars it could mean one of two things - either I haven't understood the text properly or there is a genuine mistake. So I am always keen on these sort of issues. I often find that by pursuing them I get a much better understanding of what is being said and there is always the 'prize' of finding a mistake that no-one else has yet reported.
I also think that it is important in maths to be pedantic. It is in the very nature of the subject to make absolutely sure that the text is 100% accurate and I agree with the sentiment that inaccurate text leads to confusion and heartache.
When I was doing MST121 I did find a reasonably significant error that had to be corrected in both the book and the handbook. I have also managed to get a couple of mistakes from book I1 of this course recognised as errata. However, I do feel that it is an uphill struggle and it isn't easy getting these things recognised! Tutors are busy people and there is no obvious direct channel for managing this kind of thing.
This I think is a pity. What better way to refine the text and at the same time get students really understanding what they are reading. However, if there is no easy way to report potential issues or it seems an uphill struggle, then the motivation for students to be active diminishes.
Personally, I am motivated to do this (I am a natural pedant!) but over the course of M208, I have become less inclined to report things because I am not really sure that the OU is that interested. Personally, I think the OU should be giving out real prizes to students who find mistakes in their material - it would be a great way to get students to really understand what they were reading and to focus on it with the intensity of a laser beam.
Another problem is that every time I find something that is an error it undermines my confidence in the material. After all, I am just learning this stuff. If I can find a mistake then just how good is it? What would someone find if they were a real expert? It's another reason why all mistakes (including printing errors) should really be rectified and new editions of the material published.
But, hey ho, who am I to tell the OU what to do!
-------------------------------------------------------------
I am pleased to say that since I have agitated about this there has been a good response from the course module team and they do now seem to be taking notice of any new errata and will be issuing a new errata pdf in the next couple of weeks (rather than postponing this until the beginning of the next course). However, I wish there was a more direct channel for this sort of thing and more encouragement for students.
AB3 on integration didn't represent too much of a problem. There was some discussion of integration techniques, reduction formulae, inequalities, Wallis' formula and Stirling's formula. I am glad to see that finally in M208 for a substitution of u=x2 they don't shy away from writing du=2xdx as a way of rewriting an integral. It makes me laugh that this should appear in the 'rigorous' realms of M208 but scrupulously avoided in the 'less rigorous' earlier courses of MST121 and MS221.
In the last couple of weeks I have been asking other people if they read the proofs in M208 and it seems that they don't (see my previous post). This supports my opinion that M208 could have been written differently and perhaps it would have been better to have put the proofs at the back in an appendix. So, unless you are of the conscientious type or particularly keen then the most important thing is to get an idea of what the theorems are and to try and use them.
I have also been agitating on the forum about the lack of interest in errata. Here is what I said:
------------------------------------------------------------------
I am sure I read somewhere in the blurb when I first started doing these maths courses that the OU liked students to report any errata that they found in the text and this was what the OU regarded as being a 'model student'.
Yes, I am correct. Here is a quote from the back of the pink pages for MST121:
"Some handy hints on how to be a model student!"
"Think you've found a mistake? Check the Stop Press and the course website to see if it's mentioned there. If not give your tutor a ring. You may save other students a great deal of heartache!"
I have always taken this advice seriously and I am a keen nitpicker. One of the reasons for this is that if I find something in the text that jars it could mean one of two things - either I haven't understood the text properly or there is a genuine mistake. So I am always keen on these sort of issues. I often find that by pursuing them I get a much better understanding of what is being said and there is always the 'prize' of finding a mistake that no-one else has yet reported.
I also think that it is important in maths to be pedantic. It is in the very nature of the subject to make absolutely sure that the text is 100% accurate and I agree with the sentiment that inaccurate text leads to confusion and heartache.
When I was doing MST121 I did find a reasonably significant error that had to be corrected in both the book and the handbook. I have also managed to get a couple of mistakes from book I1 of this course recognised as errata. However, I do feel that it is an uphill struggle and it isn't easy getting these things recognised! Tutors are busy people and there is no obvious direct channel for managing this kind of thing.
This I think is a pity. What better way to refine the text and at the same time get students really understanding what they are reading. However, if there is no easy way to report potential issues or it seems an uphill struggle, then the motivation for students to be active diminishes.
Personally, I am motivated to do this (I am a natural pedant!) but over the course of M208, I have become less inclined to report things because I am not really sure that the OU is that interested. Personally, I think the OU should be giving out real prizes to students who find mistakes in their material - it would be a great way to get students to really understand what they were reading and to focus on it with the intensity of a laser beam.
Another problem is that every time I find something that is an error it undermines my confidence in the material. After all, I am just learning this stuff. If I can find a mistake then just how good is it? What would someone find if they were a real expert? It's another reason why all mistakes (including printing errors) should really be rectified and new editions of the material published.
But, hey ho, who am I to tell the OU what to do!
-------------------------------------------------------------
I am pleased to say that since I have agitated about this there has been a good response from the course module team and they do now seem to be taking notice of any new errata and will be issuing a new errata pdf in the next couple of weeks (rather than postponing this until the beginning of the next course). However, I wish there was a more direct channel for this sort of thing and more encouragement for students.
Sunday, 15 April 2012
Happy
Well, I think things are going ok at the moment and I am happy with how things are turning out. I had TMA02 back a couple of days ago and I managed to score another 100%. Given that I am completing the TMA's ahead of the tutorials I feel pretty pleased with myself. However, TMA02 didn't have anything in it which I thought was particularly tricky and so I must expect a reality check at some point.
I have now completed TMA05. I did a couple of questions whilst I was away at Easter. I seem now to have a good grasp of the counting theorem and can see better how it works. This means I have now nearly caught up with myself as TMA06 is on the final block of the course which I am now working on.
AB2 on differentiation is done and I am into AB3 on integration. I quite like this business about upper and lower Riemann sums and how you can still determine whether a function is integrable even though it has discontinuities (though the function has to be bounded). It is hard to get your head round initially because of using infima and suprema instead of maxima and minima, but I can see that it is more sophisticated.
One thing I still dread are the proofs. I think the only reason I still manage to get through these is because I have a conscientious nature and I like to complete things. However, having worked through a proof and understood how one step leads to another I am often left at the end feeling that things could have been explained in a much better way.
I think the trouble is that M208 is possibly trying to do too much by proving most of the theorems that it uses. This means that perhaps not enough time is devoted to the proofs and evidence of this is that they are often labelled as 'optional reading'. Sometimes I absolutely pull my hair out trying to follow where the proof is going and I expect this is because it has been compressed into a page or so. Further explanation and post proof discussion would be a great help here. Perhaps it would have been better to include fewer proofs but explain those that were presented in more detail. It is very off-putting.
My belief is that maths should be understandable by everyone and often the only reason it is not is because of poor explanation and leaving too much to the reader. What is more useful? A short block of hieroglyphics that is a dense as a piece of iron and only readable by those who have been initiated into the rights of the temple or a longer, well described proof that everyone can follow. I know what I favour!
I have now completed TMA05. I did a couple of questions whilst I was away at Easter. I seem now to have a good grasp of the counting theorem and can see better how it works. This means I have now nearly caught up with myself as TMA06 is on the final block of the course which I am now working on.
AB2 on differentiation is done and I am into AB3 on integration. I quite like this business about upper and lower Riemann sums and how you can still determine whether a function is integrable even though it has discontinuities (though the function has to be bounded). It is hard to get your head round initially because of using infima and suprema instead of maxima and minima, but I can see that it is more sophisticated.
One thing I still dread are the proofs. I think the only reason I still manage to get through these is because I have a conscientious nature and I like to complete things. However, having worked through a proof and understood how one step leads to another I am often left at the end feeling that things could have been explained in a much better way.
I think the trouble is that M208 is possibly trying to do too much by proving most of the theorems that it uses. This means that perhaps not enough time is devoted to the proofs and evidence of this is that they are often labelled as 'optional reading'. Sometimes I absolutely pull my hair out trying to follow where the proof is going and I expect this is because it has been compressed into a page or so. Further explanation and post proof discussion would be a great help here. Perhaps it would have been better to include fewer proofs but explain those that were presented in more detail. It is very off-putting.
My belief is that maths should be understandable by everyone and often the only reason it is not is because of poor explanation and leaving too much to the reader. What is more useful? A short block of hieroglyphics that is a dense as a piece of iron and only readable by those who have been initiated into the rights of the temple or a longer, well described proof that everyone can follow. I know what I favour!
Wednesday, 4 April 2012
More of a challenge
I have been tackling TMA05 on and off over the last week and it definitely seems more of a challenge. Actually, I quite like the situation where I am faced with a question which, at first glance, I have no idea how to start. I have got to the part of TMA05 that asks about homomorphisms, kernels and images (GTB2). One part seemed very straight forward but the other half was a bit of a devil (but worth the same marks, strangely enough). I wrestled with it for an hour or so and then I had to leave it. The next day I was out shopping and suddenly I had an idea about how to go about it. This is always such a thrill and why I like questions that are a challenge. Then comes the delicious joy of nailing it completely and seeing all the arguments and theories stack up in one neat pile. Ahhh...It is the reason why I love maths.
Unbelievably I am still finishing off AB2 - just a couple of pages to go. This has been about l'Hopital's rule for finding limits of functions of the form f(x)/g(x) where the limit is required at x=c but f(c)=g(c)=0. I watched the dvd about this topic and was pleased to see David Brannan appear on the screen - the David Brannan who wrote the book on analysis. The dvd must have been a video at one time as it is all looking a bit dated now - not quite kipper ties but verging towards that.
I reckon that at this rate I will have completed the course by about June. That will give me plenty of time for consolidation and, almost certainly, a bit of a much needed rest. The exam has now been pencilled in for Wednesday 17th October, so it will just be a case of getting through this and then I will be a free agent again. Yippee!
Or will I....
Unbelievably I am still finishing off AB2 - just a couple of pages to go. This has been about l'Hopital's rule for finding limits of functions of the form f(x)/g(x) where the limit is required at x=c but f(c)=g(c)=0. I watched the dvd about this topic and was pleased to see David Brannan appear on the screen - the David Brannan who wrote the book on analysis. The dvd must have been a video at one time as it is all looking a bit dated now - not quite kipper ties but verging towards that.
I reckon that at this rate I will have completed the course by about June. That will give me plenty of time for consolidation and, almost certainly, a bit of a much needed rest. The exam has now been pencilled in for Wednesday 17th October, so it will just be a case of getting through this and then I will be a free agent again. Yippee!
Or will I....
Thursday, 29 March 2012
Bumbling along
I have been bumbling along for the last two and a half weeks making slow progress with book AB2 on differentiation. I have got past the hard part of trying to understand the proof that the Blancmange function is nowhere differentiable. I did actually get stuck and resorted to asking for help from my tutor, Alan, but by the next morning (having slept on it) I realised it was all staring me in the face. Since then I have been learning about Rolle's Theorem and the Mean Value Theorem which I have come across before (but not in so much detail). It seems that as I inch closer and closer to the end of this course, so I seem to take longer and longer to finish a book.
I had a tutorial last Saturday and Alan managed to cover the whole of the first group theory block in an hour and a half (half an hour to say what was covered and an hour to go through some old TMA questions). Impressive! I keep thinking I will be able to sit back and relax and enjoy the ride, but I keep finding that there are bits that I think I don't know. I find myself thinking "how the hell do you do that again?" and a surge of panic rushes through me. It keeps me on my toes.
I am still making progress with the TMA's. TMA04 is done and handed over and I have done the first question of TMA05 which I quite enjoyed. I love the challenge of an interesting question.
I am disappointed that the OU is removing the Diploma qualification that I am working towards. Usually I would have had quite a few years to complete this. Now that I have to start this in a year or so, it is almost certainly going to put the nail in the coffin for my future study with the OU. I saw the diploma as a stepping stone, something to achieve and an encouragement for me to continue with my studies. It would have been a useful qualification to get, but now that I have to pass it by the end of 2014, I can't see myself having the energy to do the other course I need, MST209. M208 has nearly finished me off as it is. The dividing line between enjoying the course and finding it a burden has worn very thin and now I am being pressured into the next step it is pushing me into the 'no' mode. There are, after all, plenty of other avenues for my interests in maths which do not have strict timescales and exams and I suspect that when this course finishes in October, I will be off to explore these instead. It is the OU's loss!
One of the avenues I would like to get back to is my study of prime numbers. Before I started work at the OU I had done what I think now is some good work at understanding how to compute pi(n) - the number of primes less than n. One of the first things I think I will do is to try and explain what I did in a blog like this. It was all very interesting. Nothing new to anyone else I am sure, but it was an interesting exercise for someone who knows little about the subject and who enjoyed working it out for himself!
I had a tutorial last Saturday and Alan managed to cover the whole of the first group theory block in an hour and a half (half an hour to say what was covered and an hour to go through some old TMA questions). Impressive! I keep thinking I will be able to sit back and relax and enjoy the ride, but I keep finding that there are bits that I think I don't know. I find myself thinking "how the hell do you do that again?" and a surge of panic rushes through me. It keeps me on my toes.
I am still making progress with the TMA's. TMA04 is done and handed over and I have done the first question of TMA05 which I quite enjoyed. I love the challenge of an interesting question.
I am disappointed that the OU is removing the Diploma qualification that I am working towards. Usually I would have had quite a few years to complete this. Now that I have to start this in a year or so, it is almost certainly going to put the nail in the coffin for my future study with the OU. I saw the diploma as a stepping stone, something to achieve and an encouragement for me to continue with my studies. It would have been a useful qualification to get, but now that I have to pass it by the end of 2014, I can't see myself having the energy to do the other course I need, MST209. M208 has nearly finished me off as it is. The dividing line between enjoying the course and finding it a burden has worn very thin and now I am being pressured into the next step it is pushing me into the 'no' mode. There are, after all, plenty of other avenues for my interests in maths which do not have strict timescales and exams and I suspect that when this course finishes in October, I will be off to explore these instead. It is the OU's loss!
One of the avenues I would like to get back to is my study of prime numbers. Before I started work at the OU I had done what I think now is some good work at understanding how to compute pi(n) - the number of primes less than n. One of the first things I think I will do is to try and explain what I did in a blog like this. It was all very interesting. Nothing new to anyone else I am sure, but it was an interesting exercise for someone who knows little about the subject and who enjoyed working it out for himself!
Monday, 26 March 2012
Interesting stuff
I have learnt a couple of interesting things in the last few days. The first is an answer to my question "Can we argue somehow that the Blancmange function is continuous without using the epsilon-delta definition of continuity" (see my previous post). The answer is yes and I am very pleased that my hunch was correct!
One of the tutors on the OU forum (Steve Meyer) has kindly answered this question for me. Basically, as B(x) is constructed from an infinite sum of continuous functions of the form (1/2n)s(2nx) and |(1/2n)s(2nx)|≤1/2n+1 then, as the infinite sum of 1/2n+1converges, the M-test shows that B is continuous without using epsilon-delta. There is a paper by John Kennedy which describes these ideas.
The second thing that I have learnt is quite amusing. I was trying to answer a question about the symmetries of a 3d object and got very stuck. Most of the symmetries were obvious but there were a few that weren't. I remembered how to algebraically find the difficult ones but I needed to be able to describe them geometrically and I couldn't. I made a model out of cardboard to help me and asked my wife and her brother if they could see what the difficult symmetries were. After an evening of trying we had to admit defeat and give up. I later found out that these difficult symmetries do not have a simple geometric description (such as a reflection in a plane). It was just as well I didn't spend any more time banging my head against a brick wall! Lesson learnt.
One of the tutors on the OU forum (Steve Meyer) has kindly answered this question for me. Basically, as B(x) is constructed from an infinite sum of continuous functions of the form (1/2n)s(2nx) and |(1/2n)s(2nx)|≤1/2n+1 then, as the infinite sum of 1/2n+1converges, the M-test shows that B is continuous without using epsilon-delta. There is a paper by John Kennedy which describes these ideas.
The second thing that I have learnt is quite amusing. I was trying to answer a question about the symmetries of a 3d object and got very stuck. Most of the symmetries were obvious but there were a few that weren't. I remembered how to algebraically find the difficult ones but I needed to be able to describe them geometrically and I couldn't. I made a model out of cardboard to help me and asked my wife and her brother if they could see what the difficult symmetries were. After an evening of trying we had to admit defeat and give up. I later found out that these difficult symmetries do not have a simple geometric description (such as a reflection in a plane). It was just as well I didn't spend any more time banging my head against a brick wall! Lesson learnt.
Saturday, 17 March 2012
Bother!
In the last few days I have learned that the OU is doing away with one of the qualifications I was working towards. This is the Diploma in Mathematics D23 and consists of the two second year pure and applied courses M208 and MST209. I am doing M208 this year and I thought I might do MST209 at some point, but probably later rather than sooner.
Well now I will have to pass MST209 by 31st December 2014 which means I will have to start it by October 2013 at the latest. I know this is year and a half away but this is still too soon for my liking. I intended to take a big break and then contemplate if I really have the motivation to complete the second course. Now I have no choice if I want the diploma. Botheration!!
More on this later.
Well now I will have to pass MST209 by 31st December 2014 which means I will have to start it by October 2013 at the latest. I know this is year and a half away but this is still too soon for my liking. I intended to take a big break and then contemplate if I really have the motivation to complete the second course. Now I have no choice if I want the diploma. Botheration!!
Sunday, 11 March 2012
All downhill from now on?
I have just completed book AB1 from the final analysis block and I am 3/4 the way through TMA04. I feel that the clouds are beginning to lift and some way off, but now visible, is the finishing line! Perhaps this is an odd thing to say when the course is just 6 weeks old but after going through a difficult patch after working on M208 for nearly a year, it is a nice feeling when you begin to feel that things may be downhill from now on.
I didn't find the last part of GTB3 on the counting theorem too bad. The video that goes with the course was a big help and the examples that they discussed were interesting.
Well AB1 - yuk. The first couple of sections are ok on limits and asymptotic behaviour of functions, but then came the big elephant in the room, the epsilon-delta definition of continuity and the continuity of strange functions. I can't say that I really understand the epsilon-delta definition of continuity at all well yet. I managed the exercises and worked through the proofs, but I think a lot more practise is going to be required before I can master this stuff.
The strange functions are just a p in the a. I did wonder why it was necessary to prove that the Blancmange function B(x) was continuous when it is constructed from a sum of continuous functions. They showed that B(x) is convergent for each x in R by the Comparison Test, so why isn't this and the Sum Rule for continuous functions enough to say that B(x) is continuous? I don't know.
This may also sound odd but light relief has been to work through TMA04 on the first analysis block. Read a bit of AB1, feel totally baffled, and then for light entertainment find out if a sequence or series in TMA04 converges. Bliss in comparison.
It seems that I made the right decision when it comes to the TMAs. I decided not to agonise too much over my mathematical language and to trust my own instincts. This seems to have been justified as I have had the remainder of TM01 back from my tutor and he seems happy enough with what I have done. Although I argued successfully enough to score 100% on this TMA, there were one or two places where I didn't quite get to grips with the argument and overcomplicated things. I think this accurately reflects the topics that I will need to work on in revision. At least I didn't waste lots of time wondering whether I should be using the word 'hence' rather than 'it follows' or whether an implication should be an equivalence! Trust the gut!
I didn't find the last part of GTB3 on the counting theorem too bad. The video that goes with the course was a big help and the examples that they discussed were interesting.
Well AB1 - yuk. The first couple of sections are ok on limits and asymptotic behaviour of functions, but then came the big elephant in the room, the epsilon-delta definition of continuity and the continuity of strange functions. I can't say that I really understand the epsilon-delta definition of continuity at all well yet. I managed the exercises and worked through the proofs, but I think a lot more practise is going to be required before I can master this stuff.
The strange functions are just a p in the a. I did wonder why it was necessary to prove that the Blancmange function B(x) was continuous when it is constructed from a sum of continuous functions. They showed that B(x) is convergent for each x in R by the Comparison Test, so why isn't this and the Sum Rule for continuous functions enough to say that B(x) is continuous? I don't know.
This may also sound odd but light relief has been to work through TMA04 on the first analysis block. Read a bit of AB1, feel totally baffled, and then for light entertainment find out if a sequence or series in TMA04 converges. Bliss in comparison.
It seems that I made the right decision when it comes to the TMAs. I decided not to agonise too much over my mathematical language and to trust my own instincts. This seems to have been justified as I have had the remainder of TM01 back from my tutor and he seems happy enough with what I have done. Although I argued successfully enough to score 100% on this TMA, there were one or two places where I didn't quite get to grips with the argument and overcomplicated things. I think this accurately reflects the topics that I will need to work on in revision. At least I didn't waste lots of time wondering whether I should be using the word 'hence' rather than 'it follows' or whether an implication should be an equivalence! Trust the gut!
Thursday, 23 February 2012
Linear Algebra
I have just completed TMA03 on the linear algebra section of the course and I am just in the process of writing up the last question so that I can post it off in the next day or two. I worked on questions 5 and 6 on the train whilst travelling down to see my family in Norfolk. I always book the quiet coach but it isn't always that quiet. I am sometimes confused as to why parents with young children book this coach when they must know that their children are hardly going to be able to keep quiet!
I have enjoyed linear algebra. I wish that they had included another block of it in the course as they have done for group theory and analysis. As such, this was the first time in a few months that I have delved back into it and I seem to be able to manage the questions ok.
The first three questions were straight forward but the latter three required much more thought and were a nice challenge. One in particular on subspaces and dimensions really made me think about the material and I felt that it pushed the boundaries a bit more than some of the other questions. The question on quadrics was just a slog and it is one of those where a simple slip can mess up the whole answer.
I wonder how many students do this, but part of my process for answering the questions is to look for self-consistency in my answers. For example, if I diagonalise a symmetric matrix A, I make sure that PTAP really does lead to a diagonal matrix! It is a good way of making sure that my answers are likely to be correct.
Now that I have done a good chunk of the TMA's and I have had a bit of a break, I feel ready to go back to the books and start reading again. First off finish the last section of GTB3 on the counting theorem!
I have enjoyed linear algebra. I wish that they had included another block of it in the course as they have done for group theory and analysis. As such, this was the first time in a few months that I have delved back into it and I seem to be able to manage the questions ok.
The first three questions were straight forward but the latter three required much more thought and were a nice challenge. One in particular on subspaces and dimensions really made me think about the material and I felt that it pushed the boundaries a bit more than some of the other questions. The question on quadrics was just a slog and it is one of those where a simple slip can mess up the whole answer.
I wonder how many students do this, but part of my process for answering the questions is to look for self-consistency in my answers. For example, if I diagonalise a symmetric matrix A, I make sure that PTAP really does lead to a diagonal matrix! It is a good way of making sure that my answers are likely to be correct.
Now that I have done a good chunk of the TMA's and I have had a bit of a break, I feel ready to go back to the books and start reading again. First off finish the last section of GTB3 on the counting theorem!
Monday, 13 February 2012
TMA addiction
I am currently making good progress with the TMA's because I can't stop doing the questions. I keep thinking that I'll put the question paper away for a bit and get on with some more reading but I can't help having a little look at the next unanswered question. I tinker around with it and before I know it I am fleshing out the whole answer. So TMA02 is done and I will post it off today and I have already completed a couple of questions from TMA03.
I had the first part of TMA01 back today and I was pleased to get 35/35 but I am slightly worried that I might have messed up something in the equivalence relation question in part 2. I have been learning a bit more about equivalence relations from the discussions on the forum and there was some discussion about whether you needed to have the reflexive condition or not. I tried to think of examples where a relation is symmetric and transitive, but not reflexive, but I found it hard to do. The trick, apparently, is to have an element of a set that is not related to any other element, including itself. I think equivalence relations are whole topic in itself and I could spend hours getting bogged down in it (which I don't intend to do!).
I had the first part of TMA01 back today and I was pleased to get 35/35 but I am slightly worried that I might have messed up something in the equivalence relation question in part 2. I have been learning a bit more about equivalence relations from the discussions on the forum and there was some discussion about whether you needed to have the reflexive condition or not. I tried to think of examples where a relation is symmetric and transitive, but not reflexive, but I found it hard to do. The trick, apparently, is to have an element of a set that is not related to any other element, including itself. I think equivalence relations are whole topic in itself and I could spend hours getting bogged down in it (which I don't intend to do!).
Thursday, 9 February 2012
Sense of humour failure
I have had a slight sense of humour failure over M208 over the last week but I think I am past it now. Instead of working on the books at the end of the course I have been working through the TMAs and I have completed TMA01 and I have nearly finished TMA02.
The sense of humour failure occurred because I was getting frustrated with the language of the questions. The OU marks are very formalised and you have to tick all the boxes to get all of the marks but often it is a guessing game to decide how much to put in and how much to leave out of an answer. I want to be concise but on the other hand I don't want to miss marks for not showing enough working or not supporting an argument. It was doing my head in a bit.
In the end I have decided to say "stuff it"; I am going to answer the questions in a way which I think is best and most natural to me and I don't care if I don't tick all the boxes. Enough of this agonising!
Actually, I think the TMAs are very straight forward (unless I am missing something). I suppose that's because I have already worked to near the end of the course and I have a lot of familiarity with it, so some of the early stuff seems a doddle. Perhaps I am going to be in for a shock when I get my first TMA back! TMAs are also addictive. I like solving the puzzles and I will probably end up doing most of them before I knuckle down to the last four books of the course (I have just one more section in GTB3 to finish before I get onto the last four analysis books).
The sense of humour failure occurred because I was getting frustrated with the language of the questions. The OU marks are very formalised and you have to tick all the boxes to get all of the marks but often it is a guessing game to decide how much to put in and how much to leave out of an answer. I want to be concise but on the other hand I don't want to miss marks for not showing enough working or not supporting an argument. It was doing my head in a bit.
In the end I have decided to say "stuff it"; I am going to answer the questions in a way which I think is best and most natural to me and I don't care if I don't tick all the boxes. Enough of this agonising!
Actually, I think the TMAs are very straight forward (unless I am missing something). I suppose that's because I have already worked to near the end of the course and I have a lot of familiarity with it, so some of the early stuff seems a doddle. Perhaps I am going to be in for a shock when I get my first TMA back! TMAs are also addictive. I like solving the puzzles and I will probably end up doing most of them before I knuckle down to the last four books of the course (I have just one more section in GTB3 to finish before I get onto the last four analysis books).
Tuesday, 24 January 2012
We're off!
The course hasn't officially started yet, but it feels like it. The course website opened last Tuesday and I was finally able to get my hands on the first TMA. Since then, I feel like things have stepped up a gear and I am already having to devote more hours to my study. For starters, there is TMA01 part 1 to do and it was good revision. I did get myself in a bit of a twist to start with but things worked out ok in the end. It is amazing how one tiny slip can lead you down a blind alley. Then there is the sudden burst of activity on the forums to follow; a bit more revision of I1 to do; talking to my tutor about one of the problems I found in one of the exercises (that was far more interesting than I realised) and trying to keep up with my work with the books at the end of the course. Phew! I won't be able to keep this up at this rate. I may have to scale back to just doing the TMA's and the end of course work.
Other than that I have finished the chapter on Homomorphisms (GTB2) and have begun the chapter on Group Actions (GTB3). This is my final group theory book. I don't mind group theory too much and I find it ok to work with. In the chapter on Homomorphisms (I wish that word wasn't such a mouthful!) we find that they are a bit like Isomorphisms but with the strict one-one and onto condition relaxed. Homomorphisms are basically functions that map one group to another and in the mapping process some of the domain group properties are preserved. For example, the identity in the domain is mapped to the identity in the codomain, as are inverses and powers of elements. Also elements that are conjugate in the domain are also conjugate in the codomain.
The meat of the chapter comes with the discussion of Kernels and Images of a homomorphism. This is a bit like the discussion of Kernels and Images of a linear transformation in the Linear Algebra blocks. The Kernel of a homomorphism is the set of elements of the domain that map to the identity element in the codomain. The Image is the usual notion of an image of a function. It turns out that the Kernel is a normal subgroup of the domain group and the Image is a subgroup of the codomain group. The fact that the Kernel is a normal subgroup of the domain means, of course, that its cosets partition the domain and this leads on to the Correspondence Theorem, a return to Quotient Groups and finally the Isomorphism Theorem (I ain't going to discuss all that!). It's all a bit of a handful to remember. Reasonably straight forward at the time but instantly forgettable!
Other than that I have finished the chapter on Homomorphisms (GTB2) and have begun the chapter on Group Actions (GTB3). This is my final group theory book. I don't mind group theory too much and I find it ok to work with. In the chapter on Homomorphisms (I wish that word wasn't such a mouthful!) we find that they are a bit like Isomorphisms but with the strict one-one and onto condition relaxed. Homomorphisms are basically functions that map one group to another and in the mapping process some of the domain group properties are preserved. For example, the identity in the domain is mapped to the identity in the codomain, as are inverses and powers of elements. Also elements that are conjugate in the domain are also conjugate in the codomain.
The meat of the chapter comes with the discussion of Kernels and Images of a homomorphism. This is a bit like the discussion of Kernels and Images of a linear transformation in the Linear Algebra blocks. The Kernel of a homomorphism is the set of elements of the domain that map to the identity element in the codomain. The Image is the usual notion of an image of a function. It turns out that the Kernel is a normal subgroup of the domain group and the Image is a subgroup of the codomain group. The fact that the Kernel is a normal subgroup of the domain means, of course, that its cosets partition the domain and this leads on to the Correspondence Theorem, a return to Quotient Groups and finally the Isomorphism Theorem (I ain't going to discuss all that!). It's all a bit of a handful to remember. Reasonably straight forward at the time but instantly forgettable!
Monday, 16 January 2012
Starting to get course fatigue
I was starting to get course fatigue this week. I have been working on M208 since mid February last year and it is hard to sustain the momentum over that length of time. Each day I attempt to get through a page or two, but this week I found myself doing even less than that. The thought crept into mind that I just wanted to just get the last 5 books over with, so I could start consolidating what I have already learnt.
I think part of the problem with studying is that you are being led by the nose through a lot of material not all of which is going to be exciting. The tendency after a while is to think, "oh no, not another complex idea to grapple with" or "groan, not another proof to understand". I am a firm believer that you learn the most from exploring ideas on your own and there isn't much room for this on this course. It is all very much spoon feeding.
To entertain myself I was thinking about groups in general and one question that I came up with was what if you had the situation where all elements of a set were self-inverse under composition; could that set form a group or not? I had been thinking about finite groups of low order and imagining Cayley tables where the identity element is always along the leading diagonal.
I posed this question on the OUSA M208 forum but I quickly realised that it was not a question for the novice. It was also not easy to pose the question logically, anyway. A couple of theorems occurred to me. One was a corollary to Lagrange's theorem that if G is a group of prime order p, then G is a cyclic group. This is because the only numbers that can divide p are 1 and p and so the subgroups of G can only have order 1 or order p. These correspond to the subgroups {e} and G (e is the identity element of G). Moreover, as the only element with order 1 is e, the other elements in G must have order n, so the group G is cyclic.
So if the order of a finite group is prime then the group is cyclic. If we now consider these prime order groups where the order is greater than 2, then we can show that the elements of these groups cannot all be self-inverse. Why? Because to be a cyclic group we require that there is g element G of order n but the orders of g are all 2 (because they are self-inverse).
Hence, if a set contains p self-inverse elements and p is a prime number bigger than 2, then this set cannot form a group!
Interestingly, the sets with either one and two self-inverse elements can form groups under composition. {e} is a group and {e, g} can be a cyclic group since g can generate the group.
The other theorem which tackles this problem head on is Theorem 3.2 of GTA4. Let G be a group, with order greater than 2, in which each element except the identity has order 2. Then the order of G is a multiple of 4. So this means that groups of order 3 or more in which all the elements are self-inverse have to have an order of 4, 8, 12, 16...This agrees with what I deduced from the corollary to Lagrange's theorem, but is more stringent.
I think part of the problem with studying is that you are being led by the nose through a lot of material not all of which is going to be exciting. The tendency after a while is to think, "oh no, not another complex idea to grapple with" or "groan, not another proof to understand". I am a firm believer that you learn the most from exploring ideas on your own and there isn't much room for this on this course. It is all very much spoon feeding.
To entertain myself I was thinking about groups in general and one question that I came up with was what if you had the situation where all elements of a set were self-inverse under composition; could that set form a group or not? I had been thinking about finite groups of low order and imagining Cayley tables where the identity element is always along the leading diagonal.
I posed this question on the OUSA M208 forum but I quickly realised that it was not a question for the novice. It was also not easy to pose the question logically, anyway. A couple of theorems occurred to me. One was a corollary to Lagrange's theorem that if G is a group of prime order p, then G is a cyclic group. This is because the only numbers that can divide p are 1 and p and so the subgroups of G can only have order 1 or order p. These correspond to the subgroups {e} and G (e is the identity element of G). Moreover, as the only element with order 1 is e, the other elements in G must have order n, so the group G is cyclic.
So if the order of a finite group is prime then the group is cyclic. If we now consider these prime order groups where the order is greater than 2, then we can show that the elements of these groups cannot all be self-inverse. Why? Because to be a cyclic group we require that there is g element G of order n but the orders of g are all 2 (because they are self-inverse).
Hence, if a set contains p self-inverse elements and p is a prime number bigger than 2, then this set cannot form a group!
Interestingly, the sets with either one and two self-inverse elements can form groups under composition. {e} is a group and {e, g} can be a cyclic group since g can generate the group.
The other theorem which tackles this problem head on is Theorem 3.2 of GTA4. Let G be a group, with order greater than 2, in which each element except the identity has order 2. Then the order of G is a multiple of 4. So this means that groups of order 3 or more in which all the elements are self-inverse have to have an order of 4, 8, 12, 16...This agrees with what I deduced from the corollary to Lagrange's theorem, but is more stringent.
Subscribe to:
Posts (Atom)