Sections 11.3-11.4, Due on Wed Mar 26

Here I will analyze and give my thoughts on Sections 11.3 and 11.4 of Mathematical Proofs: A transition to advanced mathematics.

11.3 - Greatest Common Divisor
An integer c \ne 0 is a common divisor of two integers a and b if c | a and c | b.

The greatest common divisor of two integers a and b, not both 0, is the greatest positive integer that is a common divisor of a and b.

The whole concept of common divisor and greatest common divisor is something that is not too difficult for me to understand.  I remember learning this as a younger child.  It makes sense - to find the biggest number that nicely divides into two numbers.  That is the GCD.  I kind of like the thought of this.

I believe I will have difficult in proving this - at first.  I can see myself learning and understanding this better.

Here are a couple theorems from the section (typing them up helps me remember them):

• Let a and b be integers that are not both 0.  Then gcd (a,b) is the least positive integer that is a linear combination of a and b.  

• Let a and b be two integers, not both 0.  Then d = gcd(a,b) IFF d  is that positive integer which satisfies the following two conditions:
• 1) d is a common divisor of a and b;
• 2) if c is any common divisor of a and b, then c | d.

I enjoy learning about GCD.  It kind of makes sense to me, which would be why I like it.  I enjoy taking a look at linear combinations - those have always made sense to me.

11.4 The Euclidean Algorithm
This is the algorithm for determining d=gcd(a,b).  It "makes use of repeated applications of the Division Algorithm and the following:

• Let a and b be positive integers.  If b = aq + r  for some integers q and r, then gcd(a,b) = gcd(r,a).

This was difficult to understand at first, but I can see the usefulness of it and the thought process of it by looking at the example.  For example, we want to find the following:  d = gcd(374,946).

We go down the line using the Euclidean Algorithm, and first divide 946 by 374.  374 goes into 946 2 times with a remainder of 198.  We then divide 374 by 198.  This goes in once with a remainder of 176.  We then divide 198 by 176.  This gives us a remainder of 22.  We then divide 176 by 22, which goes in 8 times.  Thus, gcd(374,976) = 22.

I find this whole process fascinating and I look forward to learning more about it.  I did have trouble understanding the last example in the book.  With more practice, I should be able to understand more.

-nap