Euclid Comes To Programming Class

A student in my middle level programming course brought in a word problem from school.

"The Billy Bonkers candy factory is having a contest. The candy makers placed a silver ticket in every 600th chocolate bar and a golden ticket in every 720th chocolate bar. Anyone who purchases a chocolate bar containing both tickets wins the grand prize. If 10,000 chocolate bars are sold, how many grand prize winners will there be?"

Once we determined this was a Least Common Multiple problem, we talked about various ways to solve it. One student suggested writing out the first few multiples of each number and looking for common numbers. Another student had learned about factor trees and knew how to use prime factors to find the LCM. Yet another student showed us how to use a Venn diagram to organize the prime factors.

While discussing the relative efficiency of each method, one student declared, "It would take forever to do this if we had a lot of numbers."

"It sure would seem that way," I thought to myself, relishing the near perfect segue this statement introduced. And before I could get the words out, another student asked if we could write a program.

"We certainly could try," I said aloud.

We began by attempting a simpler problem: finding a common multiple of two numbers; not necessarily the smallest one. Everyone agreed that the easiest method was to multiply the numbers together. We then compiled a list of products and LCMs for various pairs of numbers. I wanted the students to find a connection between the product and the LCM. How do the divisors relate to the original number pairs?

2 and 5: Product = 10; LCM = 10 (divide the LCM by 1)
3 and 6: Product = 18; LCM = 6 (divide the LCM by 3)

4 and 6: Product = 24; LCM = 12 (divide the LCM by 2)

8 and 12: Product = 96; LCM is 24 (divide by LCM by 4)

The connection eluded the students and it took quite a few hints to help them see that the product of two numbers is related to their LCM by the greatest common factor. We had the beginnings of an efficient algorithm.

LCM = (number1 x number2)/GCF

Or did we? Had we just shifted the difficulty in finding the LCM to the similarly difficult task of finding the GCF? Is there a quick way to find the GCF of two numbers?

We talked through some known methods (listing the factors of each number, using prime factorization, applying the venn diagram) and opted to look for a better way.

We uncovered some interesting facts about the GCF. It's never larger than the smaller number or the difference between the two numbers. Consecutive numbers always have a GCF of 1 making them relatively prime. One student suggests an algorithm that tests if each number, from the smaller of the pair down to 1, evenly divides both numbers. The first number that worked would be the GCF. We look at the numbers 6 and 20. The program would test 6, 5, 4, 3, 2, 1. The number 2 evenly divides 6 and 20 and would be the GCF. I asked what would happen if the two numbers were as large as the numbers in the word problem - 600 and 720. Is it really necessary to test all the numbers from 600 to the GCF? Someone suggests testing only the factors of 600. Nice! But how do we find all the factors of 600? And even if we had an algorithm for this, we'd have to test several factors before hitting upon the GCF.

Time to introduce Euclid's algorithm. We divide the larger number by the smaller number and find the remainder. If the remainder is zero, the smaller number is the GCF. If not, we continue the process. During each iteration, the original smaller number becomes the dividend and the remainder becomes the divisor. When we finally get a remainder of zero, the last divisor is the GCF.

Finding the GCF of 600 and 720 became an astonishingly easy task.

720/600 = 1 r 120

600/120 = 5 r 0
GCF = 120

The students were amazed! Two steps. That was all. After trying a few more number pairs, the class was satisfied that the procedure was foolproof. Back to the original problem; finding the LCM of a group of numbers. The equation we had discovered earlier was:

LCM = (number1 x number2)/GCF

The plan was to take the first two numbers in the set, apply Euclid's algorithm to find the GCF, then use the GCF to divide the product of the two numbers. We would repeat the procedure with the current LCM and the next number in the set until we reached the final number and, therefore, the final LCM.

Naturally, this begs the question, "What can we do with this?", which I will ask the class at our next meeting.