Math For Elementary Teachers

Part 3v: Euclid’s Algorithm/Assorted Number Theory Problems

Video Preparation:

Please read the following before watching this clip!

Euclid’s Algorithm

Given positive integers a and b (without loss of generality, assume a > b), Euclid’s algorithm is a procedure for computing the greatest common factor of a and b (denoted GCF(a,b)). The procedure is based on the following fact:

if a=bq+r, then GCF(a,b)=GCF(b,r) (*)

This is useful, because the Quotient-Remainder Theorem (aka the Division Algorithm) tells us that if we divide a by b, there exists unique whole numbers q and r such that a=bq+r and, moreover, 0 \leq r < b. So the starred fact replaces the given problem GCF(a,b) with the equivalent, easier problem GCF(b,r) (this new problem is easier because the numbers are smaller, can you see why?). Euclid’s algorithm essentially tells us to use division and the starred fact over and over again until we obtain either a problem that is easy enough to solve by inspection (for example, one involving very small numbers), or a problem of the form GCF(x.0), as the answer to this problem is always x. We are guaranteed to eventually return a problem of this form, as each successive use of the starred fact will produce a smaller value of r, therefore after finitely many steps the remainder r must eventually become 0.
Let’s try an example.

Example: Compute GCF(238,153)

Solution: We use the Division Algorithm to write 238=153 \times 1 + 85, thus the starred fact tells us that GCF(238,153)=GCF(153,85). We now repeat the process with our equivalent, easier problem. Again by the Division Algorithm, we may write 153=85 \times 1+68, and the starred fact now tells us that GCF(153,85)=GCF(85,68). Repeating the process again yields 85+68 \times 1+17, and soGCF(85,68)=GCF(68,17). Finally, 68=17 \times 4 + 0, therefore GCF(68,17) = GCF(17,0). Putting it all together, we have the following chain of equalities:

GCF(238,153)=GCF(152,85)=GCF(85,68)=GCF(68,17)=GCF(17,0)=17

In the following clip we begin a problem involving much larger numbers; see if you can finish it! The answer is given at the bottom of the next section that lists all of the problems solved in the clip.

*For those of you interested in a formal proof of the starred fact, keep reading!

THEOREM: Given whole numbers a, b, q, r if a=bq+r, then GCF(a,b)=GCF(b,r).

PROOF: Try to imagine writing out two lists of numbers; the first list contains all common factors of a and b, and the second contains all common factors of b and r. The largest number in the first list is GCF(a,b), while the largest number in the second list is GCF(b,r). Now if we can somehow show that the two lists are identical, i.e. that they contain exactly the same numbers, then the largest number in the first list must be the same as the largest number in the second list, and hence it must be the case that GCF(a,b)=GCF(b,r).

Now to prove that the lists are identical, we must do two things. We must show that every number that appears on the first list also appears on the second list, and we must also show that every number that appears on the second list also appears on the first list. Furthermore, since our given numbers are arbitrary, we must do this in general.

So suppose that x appears on the first list, that is suppose x is a common factor of a and b. So both a and b are multiples of x, thus we may write a=xm and b=xn for some whole numbers m and n. Now we may write our given equation a=bq+r in the equivalent form r=a-bq=xm=xnq=x(m-nq). This equation shows that x is a factor of r. We are given that x is a factor of b, therefore x is a common factor of b and r, meaning it appears on the second list. Since x was an arbitrary member of the first list, we have successfully shown that every number that appears on the first list also appears on the second list.

We still have to prove the ‘other direction’, that is, that every number that appears on the second list also appears on the first list. The proof is very similar, and if you have read this far then perhaps you’d like to take a crack at it yourself! Have fun!

Exercises from the Clip:

The following exercises are discussed and solved in the next clip. Try to solve them yourself before watching!  (All exercises are taken from Elementary Mathematics for Teachers (EMT) by Thomas Parker and Scott Baldridge)

  1. Use Euclid’s Algorithm to reduce the fraction \frac {5829}{18879}. (EMT p. 143, #9a) *Note: I didn’t solve this problem completely in the clip; the answer is given at the bottom of the page.
  2. How many zeros are at the end of the decimal form of 10!? (EMT p. 121, #6a)
  3. Prove that the sum of any three consecutive numbers is divisible by three. (EMT p. 124, #4)
  4. Use the idea of instructional counterexamples to answer the questions below. (EMT p. 124 #3)
    1. A student claims that all odd numbers are prime. How do you convince her that it is not true?
    2. An algebra student claims that (a+b)^2=a^2+b^2 is true for all numbers a and b.  Show his claim is false by counterexample.
    3. Tiana conjectures that for each whole number nn^2+n+11 always produces a prime. Is she right?
  5. Notice that the number 6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 is divisible by 2, 3, 4, 5 and 6. Prove that the numbers 6!+2, 6!+3, 6!+4, 6!+5 and 6!+6 are all composite by giving a factor of each. (EMT p. 124 #5a)

*Here is the rest of the solution to #1:
18879=5829 \cdot 3+1392
5829 = 1392 \cdot 4 + 261
1392 = 261 \cdot 5 + 87
261 = 87 \cdot 3 + 0
So,
GCF(18879,5829) = GCF(5829,1392) = GCF(1392,261) = GCF(261,87) = GCF(87,0) = 87

© Copyright 2012 Math for Elementary Teachers.
All rights reserved.

Singapore Math is a registered trademark of Singapore Math Inc.