Greatest Common Factor Made Easy: It's Euclid to the Rescue!!!

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.

The Problem of the Week Day 5: Week 6/19 - 6/25

Today is the last portion of our problems! For variables, the easy problem requires them all while the hard one only requires a, b, and q. I would recommend looking over Monday's work for the hard problem if you are doing the hard one because you will require some trigonometry.

Easy Problem: This problem uses some experimental probability. All you do is put the number of what you want over the total amount of objects. For instance, if there was a bag with 1 red jolly rancher and 2 blue jolly ranchers and you wanted to pull out the red one, put 1 red jolly rancher over 3 total jolly ranchers to get 1/3 = 33.3%.

I have a bag with c green marbles and n/z red ones. If I pull out y marble(s), what are the odds that the marble will be green? Express your answer in a percentage.

Hard Problem: To determine the area of a trapezoid, take the two bases and add them together. Then, multiply that sum by the height, and divide that answer by two. This will give you the trapezoid's area.

Hint: To convert inches to centimeters, divide the measurement by 2.54.

1) Convert measurements a and b from Monday to centimeters. On Monday, there were in inches, but we are measuring in centimeters!

Our centimeter conversion for a will be equal to z.
Our centimeter conversion for b will be equal to p.

2) Calculate the height of this trapezoid using sines and trigonometry.

This is the trapezoid you will use to solve the problem.

h = ____

3) Determine the area of this trapezoid. Your answer should be expressed in square centimeters.

If you completed one or both equations, send me your answer. I will tell you if you are correct and list you as one of the people who completed it.

Problem of the Week Day 4: Week of 6/19 - 6/25

Last week, the easy problem only required the previous day's variables while the hard problem required every variable in that week's history. Today, we are doing it in reverse. For the hard problem, you only need m and n while the hard problem requires c, n and z.

Easy Problem: Today, we will be computing lots of fractions. In order to add fractions, you need a common denominator (the denominator is the bottom number/term). In order to do that, multiply one or both denominator(s) and numerator(s) (top number/term) by a number in order to make the denominators equal. Then, add the numerators and use the common denominator as the denominator of your sum. To multiply fractions, simply multiply the numerators and multiply the denominators.

Plug c, n, and z into this equation and solve for y: [(c + n/z) / 2n] + (1/n + 1/z) c/n = y

y = ____

Hard Problem: When given a negative exponent, all you do is make the exponent positive and find the term's reciprocal (divide the term into 1) For instance, 2^-2 = 1/2^2 = 1/4.

Hint: The graph x^2 + y^2 = r^2 is a circle around the origin (0, 0) with r being the radius of the circle. If you had a less than symbol (<) instead of the equal symbol, shade inside of the circle. For a greater than symbol (>), shade outside of the circle.

1) Solve for g: g = 5(m^-1)(n^-1)

g = ____

2) Graph the following on graph paper: x^2 + y^2 < g

3) Using the formula A = πr^2, find the area of the shaded portion. Since we already used a in our trigonometry, we will make the area = q.

q = ____

The Problem of the Week Day 3: Week 6/19 - 6/25

Here is Day 3's problem. For the easy problem, you will only need yesterday's answers (keep Monday's for later though). For the hard problem, you will need Monday's and yesterday's answers. Good luck!

Easy Problem: If you have a number right next to an expression in parentheses, that also means multiplication. It's kind of like with a variable!

Plug z in from yesterday's work, and solve for n. [z(4 + z) + 5z]/(3z - 3) = n

Hard Problem: If you have two points on a linear graph, you can figure out it's slope (rate of change) by using the formula y2 - y1 / x2 - x1. So, if you had points (3, 0) and (4, 2), you would do 2 - 0 / 4 - 3 = 2 / 1 = 2. Therefore, 2 is your slope. Then, plug that into y = mx + b as m, and make b your y-intercept (where your line crosses the y axis). If you plug any point from the graph into that equation, it should be correct.

1) If yesterday's x = the x intercept of your graph (x , 0) and y = the y intercept of your graph (0 , y), find the slope (m) of this graph. What is this graph's equation?

m = ____
y = ____x + ____

2) Solve for r in the following equation: 1 + 8r^3 + 4^8 = (2b - a)^3 - 30 • 70 - 4 • 15

3) Plug r in for y in the graph's equation and find x. Since we already used x yesterday, we will call this value n.

n = ____


By the way, if you want to check in and see how you're doing, by all means, contact me at ethan@ethanmath.com. I will get back as soon as possible and tell you if you are correct.

The Problem of the Week Day 2: Week 6/19 - 6/25

Here is the second part of our first problem of the week! Make sure you remember your answers from yesterday to plug into today's equations!

Easy Problem: To do this problem, you need to do some simple Algebra. Remember to do the opposite operation of what is there. For instance, if you see multiplication, you would do division to both sides to get rid of it. For example, if you had 6 = 2k (a letter with a number to its left without a symbol means multiplication), you would divide both sides of the equation by two to get 3 = k.

Step 1: Plug c into this equation: (2 x c^2) + 1 = ?
Step 2: Make the answer to that equal 17z
In other words, solve (2 x c^2) + 1 = 17z

z = ___

Hard Problem: Since the easy people get one equation to solve, we can handle two! This is a system of linear equations, where you have to solve for two variables, requiring a second equation. In order to solve it, you will multiply through one or both equations by a number that will make two coefficients the same number, but one negative and one positive. Then, you add both equations together, which eliminates a variable and allows you to use simple Algebra to determine the other. After finding that variable, plug its answer into the easiest of the original equations and solve for the other variable. Since the math will be difficult, you may use a calculator for today's work. You will be plugging yesterday's answers into this equation where you see the letter a or b.

-3ax + 156y = 519 - 6b
3bx + 48.2y = 6^3 + .9

x = ____
y = ____


Also, the problem of the week is only going to occur once every month. Yesterday, I said it would be weekly. My mistake. On the first day of the next problem of the week, I will inform you of who got the answer right.