Part 3v: Euclid’s Algorithm/Assorted Number Theory Problems
Please read the following before watching this clip!
Given positive integers and (without loss of generality, assume ), Euclid’s algorithm is a procedure for computing the greatest common factor of and (denoted ). The procedure is based on the following fact:
if , then (*)
This is useful, because the Quotient-Remainder Theorem (aka the Division Algorithm) tells us that if we divide by , there exists unique whole numbers and such that and, moreover, . So the starred fact replaces the given problem with the equivalent, easier problem (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 , as the answer to this problem is always . 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 , therefore after finitely many steps the remainder must eventually become .
Let’s try an example.
Solution: We use the Division Algorithm to write , thus the starred fact tells us that . We now repeat the process with our equivalent, easier problem. Again by the Division Algorithm, we may write , and the starred fact now tells us that . Repeating the process again yields , and so. Finally, , therefore . Putting it all together, we have the following chain of equalities:
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 , , , if , then .
PROOF: Try to imagine writing out two lists of numbers; the first list contains all common factors of and , and the second contains all common factors of and . The largest number in the first list is , while the largest number in the second list is . 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 .
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 appears on the first list, that is suppose is a common factor of and . So both and are multiples of , thus we may write and for some whole numbers and . Now we may write our given equation in the equivalent form . This equation shows that is a factor of . We are given that is a factor of , therefore is a common factor of and , meaning it appears on the second list. Since 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)
- Use Euclid’s Algorithm to reduce the fraction . (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.
- How many zeros are at the end of the decimal form of ? (EMT p. 121, #6a)
- Prove that the sum of any three consecutive numbers is divisible by three. (EMT p. 124, #4)
- Use the idea of instructional counterexamples to answer the questions below. (EMT p. 124 #3)
- A student claims that all odd numbers are prime. How do you convince her that it is not true?
- An algebra student claims that is true for all numbers and . Show his claim is false by counterexample.
- Tiana conjectures that for each whole number , always produces a prime. Is she right?
- Notice that the number is divisible by , , , and . Prove that the numbers , , , and are all composite by giving a factor of each. (EMT p. 124 #5a)
*Here is the rest of the solution to #1: