*"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)

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

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.

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

## No comments:

## Post a Comment

Thank you for visiting the Math Playground blog. We will read and publish your comment shortly.