What is the Euclidean algorithm?
With the Euclidean algorithm, we can easily find a Greatest Common Divisor of some two integers.
How?
The Euclidean algorithm uses 3 properties below. Don’t worry, I’m here to prove them lol.
Properties the Euclidean algorithm uses
- GCD(A, 0) = A
- GCD(0, B) = B
- GCD(A,B) = GCD(B, R)
Extra info you gotta know
- In the Euclidean algorithm, ‘A’ is considered as ‘B⋅Q + R’, which is the expression for dividing ‘A’ by ‘B’.
- As I mentioned above, GCD(A, B) equals GCD(B, R). So the Euclidean algorithm finds the Greatest Common Divisor of ‘A‘ and ‘B‘ with GCD(B, R) instead of figuring out GCD(A, B) directly.
- Because it’s an easier way to find GCD(A, B).
With the properties No. 1 and 2, we can find the Greatest Common Divisor when ‘A’ or ‘B’ is 0. With the No. 3 property, we can ease some large and complex problems into smaller and simpler ones.
Example
Let’s find the GCD(270, 192).
- A = 270, B = 192
- Quotient and Remainder for ‘270(A) / 192(B)’ are 1(Q) and 78(R).
- So, the next task will be to find GCD(192, 78) in the same way.
- A = 192, B = 78
- Quotient and Remainder for ‘192(A) / 78(B)’ are 2(Q) and 36(R).
- So we gotta find GCD(78, 36).
- A = 78, B = 36
- Quotient and Remainder for ‘78(A) / 36(B)’ are 2(Q) and 6(R).
- Repeatedly, we have to find the GCD(36, 6).
- A = 36, B = 6
- Quotient and Remainder for 36(A) / 6(B) are 6(Q) and 0(R).
- Finally, we need to find the GCD(6, 0)
- But, according to Property No. 1, GCD(6, 0) is just 6. That’s it!
Okay, let’s prove 3 properties. After that, you might understand the process above properly and what the actual Euclidean algorithm is.
Hold my beer.
Prove No. 1 and 2!
As you know guys… GCD is the Greatest Common Divisor. So GCD(A, 0) means the Greatest Common Divisor of ‘A’ and ‘0’. Guess the number that is the biggest and can divide ‘A’ cleanly. It’s an ‘A’, boring…
And Imagine any number ‘C’, and divide ‘0’ using ‘C’. The result will be always ‘0’, which means any number can divide ‘0' cleanly. So ‘C’ can be any number that includes ‘A’, you feel me?
So, GCD(A, 0) is the ‘A’! Pretty easy, isn’t it?
GCD(0, B) will be a ‘B’ in the same way.
GCD(A, B) = GCD(B, A-B)
Before we prove No. 3, we need to prove ‘GCD(A, B) = GCD(B, A-B)’ first.
And to prove that, we need to prove something first. Sorry lol.
Can GCD(A, B) divide ‘C’ cleanly? Imagine ‘A - B = C’!
According to the definition of GCD, the GCD(A, B) can divide A without any remainder. So, ‘A’ can be the multiples of GCD(A, B). I will consider it as ‘X⋅GCD(A, B) = A’.
In the same way, ‘B’ can be the multiples of GCD(A, B), which means ‘Y⋅GCD(A,B) = B’.
Let’s substitute them into the equation ‘A - B = C’!
It will be ‘X⋅GCD(A, B) - Y⋅GCD(A, B) = C’, and finally ‘(X - Y)⋅GCD(A, B) = C’.
So, we can now say that the GCD(A, B) can divide ‘C’ cleanly!
Can GCD(B, C) divide ‘A’ cleanly too? Same with the above!
The GCD(B, C) can divide ‘B’ without any remainder. So, ‘B’ can be the multiples of GCD(B, C). And I will say it as ‘M⋅GCD(B, C) = B’.
In the same way, ‘C’ can be ‘N⋅GCD(B, C)’.
Recall the equation ‘A - B = C’!
And ‘A - B = C’ can be ‘B + C = A’.
So, if I substitute B and C into that equation, it will be ‘(M + N)⋅GCD(B, C) = A’.
Now we can say that the GCD(B, C) can divide ‘A’ without any remainder!
Okay! now GCD(A, B) = GCD(B, A - B)
Repeatedly, GCD(A, B) divides ‘B’ cleanly, and we proved that GCD(A, B) can divide ‘C’ cleanly. So we can think of the GCD(A, B) as a common divisor of ‘B’ and ‘C’.
But GCD(B, C) is the Greatest Common Divisor of ‘B’ and ‘C’. In this situation, you can say GCD(B, C) is greater than or equal to GCD(A, B). Like —
GCD(B, C) ≥ GCD(A, B)
But, listen.
By the definition, GCD(B, C) can divide ‘B’ with no remainder, and we also proved that GCD(B, C) can cleanly divide ‘A’ too.
In other words, GCD(B, C) is the common divisor of ‘A’ and ‘B’, which means GCD(B, C) must be smaller than or equal to GCD(A, B).
Now, we know GCD(B, C) and GCD(A, B) are the same. Like —
GCD(A, B) = GCD(B, C)
At this point, you should recall the ‘A - B = C’ equation again to understand.
Then, you can see that ‘GCD(A, B) = GCD(B, C) = GCD(B, A - B)’ holds true!
So, we proved ‘GCD(A, B) = GCD(B, A - B)’! Way to go!
Now, we can prove the No. 3 property, which is ‘GCD(A, B) = GCD(B, R)’.
Prove No. 3!
We proved that GCD(A, B) equals GCD(B, A - B) right before. It doesn’t matter if we change the location of ‘B’ and ‘A - B’. So, it’s possible to say ‘GCD(B, A - B)’ as a ‘GCD(A - B, B)’.
If we repeat the ‘GCD(A, B) = GCD(A - B, B)’, the whole equation will be —
GCD(A, B) = GCD(A - B, B) = GCD(A - 2B, B) = GCD(A - 3B, B) … GCD(A - QB, B)
But, because ‘A’ is considered as ‘B⋅Q + R’ in the Euclidean algorithm, the final form will be ‘GCD((B⋅Q + R) - QB, B)’.
We all know that ‘B⋅Q + R - QB’ can be just ‘R’.
So, now we can prove that ‘GCD(A, B)’ equals ‘GCD(R, B)’.
Thank you!
