Euclidean Algorithm Explained for Elementary School
In number theory, the Euclidean algorithm is a method for getting the greatest common factor (GCF) or highest common factor (HCF) of two positive integers. It is usually used for larger numbers since prime factorization can be used to get the greatest common factor of small numbers. Many students are confused with this method, but if you look at it closely, even elementary students can actually do it.
Let us start with an example. Note that in the discussion below, we will use the terms dividend and divisor. In the division a ÷ b, a is the dividend and b is the divisor.
Problem: Find the greatest common factor of 15 and 40 using the Euclidean Algorithm.
In Step 1, we divided 40 by 15, got a quotient of 2 and a remainder of 10.
In Step 2, the divisor 15 in the previous step (Step 1) became the dividend. The remainder 10 in the previous step became the divisor. In the calculation, we got a quotient of 1 and a remainder of 5.
In Step 3, the divisor 10 in the previous step (Step 2) became the dividend. The remainder 5 in the previous step became the divisor. We got a quotient of 2 and a remainder of 0.
Once the remainder in the algorithm becomes 0, the remainder in the previous step is the greatest common factor of the two numbers. In this case, the remainder is the previous step is 5, so the greatest common factor of 15 and 40 is 5.
As we can see from above, the Euclidean algorithm is repeated division such that in each step, the divisor is the remainder from the previous step and the dividend is the divisor from the previous step.
Geometric Interpretation
We can think about 15 and 40 as lengths of two ropes in meters. If we want to cut the ropes into shorter pieces with equal lengths, we want to maximize such that no part of the ropes will be wasted. With this condition, the longest possible length of each cut piece is the greatest common factor of 15 and 40.
Problem: Find the longest possible length that a 15m and a 40m rope cut into shorter pieces with equal lengths such that no part of the rope will be wasted.
The equivalent of the algorithm above can also be represented geometrically as shown in the preceding figure. In Step 1, two 15-meter ropes were used to fit the 40 meter rope, and then the remainder which was 10 meters was used as measuring rope in the next step. In Step 2, a 10-meter rope was used to fit the 15-meter rope, but this time, gave a remainder of 5 meters. Finally, in Step 3, two 5-m ropes exactly fit the 10-meter rope.
Therefore,we can cut both the ropes into 5 meters and get eleven 5-meter ropes combined.
Euclidean Algorithm Elementary Number Theory
In advanced high school mathematics and university textbooks, you will see the method above written differently. For those who majored in mathematics will probably remember the algorithm below. That is, the repeated
where 
40 = 15(2) + 10
15 = 10(1) + 5
10 = 5(2) + 0
So, the remainder before