Mastering Euclid's Algorithm to Find the GCD Easily 🧮

The Euclid's algorithm is widely used to find the GCD, short for Greatest Common Factor, of numbers. It uses interesting mathematical properties of division and remainders to find the answer.

Here we prove the GCD algorithm once again to bring clarity to Euclid's method of dividing the larger number by the smaller one and setting the new parameters to the smaller and remaining number.

Check out these videos on the code for the algorithm (https://youtu.be/80pOI0_BXyk) and an exciting question (https://youtu.be/D-DYtUmRMa4)!

Code:
https://github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/GCD.java
Codechef Problem:
https://www.codechef.com/problems/GCDQ
References:
https://brilliant.org/wiki/greatest-common-divisor/
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap04.pdf