Find the greatest common divisor for 102 and 66, (102, 66), and the values of m and n such that (102, 66) = 102m + 66n
You may have been surprised to read (in Thm. 2.12) that for any two integers there is going to be a greatest common divisor which can be written as a linear combination of the two values. In essence, what this says is that since the divisor divides both numbers, there is going to be some combination of multiples of the two that adds up to the divisor.
For example, for the numbers 6 and 8, the greatest common divisor is 2 AND 2 = 3(6) + -2(8).
Now, I could find that by looking at multiples until a find a combo that would add to 2. That would look like the following.
6 … 12, 18, 24, …
8 … 16, 24
What I would notice is that the 18 and 16 are 2 apart, which means I only need to use some positives and negatives for the coefficients. (This reminds me a lot of the hunt and peck form of factoring we sometimes teach students.)
The power of this linear combination is that it gives us a way to write the divisor in terms of the original values we were given. That’s helpful.
Which brings us to the Euclidean Algorithm. What Euclid did was develop a process that would allow us to find this linear combination without doing hunt and peck, which is REALLY helpful if you have to do it for “ugly” numbers. (Confession: as helpful as this algorithm is, it can make me a bit nuts when I’m trying to use it.)
Find the greatest common divisor for 102 and 66, (102, 66), and the values of m and n such that (102, 66) = 102m + 66n.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
