In the topic of Number Theory and Discrete Mathematics, you will run onto a topic called "The Greatest Common Factor" (also known as the greatest common divisor). The greatest common factor (abbreviated as GCF) is when you take two numbers and find the highest number that divides into both of them. It basically explains itself.
In school, you learn that to find the GCF of two numbers, make a T-chart with the two numbers on the top, and list out all of their factors below. Then, find the two greatest ones that are the same. However, you don't have to do that according to Euclid, a famous greek mathematician.
Euclid's Theorem is a way to use modular arithmetic to solve the GCF of two numbers. All you do is divide the smaller number into the larger number. Then, take your remainder from that division problem and divide that into the other number. Keep up that process until there is no remainder, and you have your GCF. For instance, what is the GCF of 88 and 33? Well, 88 ÷ 33 = 2 R22, so you now have 22 and 33. 33 ÷ 22 = 1 R11. Since 22 ÷ 11 has no remainder, you have finished, and your GCF is eleven.
Although the how is always cool (it's going to be here), I like to see why these things work. To prove it, I think of how the greeks used to do division without modern day arithmetic: by repeated subtraction. To divide 25 by 4, they would say okay, 25 - 4 = 21, still positive, 21 - 4 = 17, still positive, and keep going until they can't subtract anymore. Since proofs always use variables, we will say we are dividing a by b and the quotient is x, or we subtracted it x times.
Euclid's Theorem is like that, we are looking for the GCF of a and b and when we divide, x is the quotient and (a - bx) is the remainder. Then, you would have b and a - bx. However, we just subtracted a multiple of b. If we added or subtracted more b's, we would end up with the same remainder. So, we can add a multiple of b back, bx, to get what we were looking for: a.
The proof and theorem itself are pretty cool, but it gets better. I'd like you to guess which two numbers between 1 and 100 would take the longest to figure out. A lot of people would immediately say 99 and 98. Well, 99 ÷ 98 = 1 R1, and 1 goes into 98 with no remainder, making 1 the GCF. That would have taken Euclid one step. Then, people might throw 99 and 50 at him, as they are reasonably far apart. Euclid can tackle that one in two steps. 99 ÷ 50 = 1 R49. 50 ÷ 49 = 1 R1. Since 1 goes into 49, one is the GCF of this one as well.
It turns out the answer is 55 and 89. 89 ÷ 55 = 1 R34. 55 ÷ 34 = 1 R21. 34 ÷ 21 = 1 R13. 21 ÷ 13 = 1 R8. 13 ÷ 8 = 1 R5. 8 ÷ 5 = 1 R3. 5 ÷ 3 = 1 R2. 3 ÷ 2 = 1 R1. Since 1 goes into two, we have completed the problem, and found that one is the GCF.
What's so special about 55 and 89 you may ask. They are Fibonacci Numbers, a famous sequence because of its beautiful patterns and attributions to nature. Basically, they start with 1 and 1. Then, Fibonacci added those together to get 2. Then, he added 1 and 2 together to get 3. He continued adding the previous two numbers together going 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc. The Fibonacci numbers are so cool that every Saturday that's date is a Fibonacci Number, I will share another pattern within these numbers.
No comments:
Post a Comment