Euclidean Algorithm for GCD Calculation 🧮

The Euclidean Algorithm, or Euclid's Algorithm, is used to quickly find the Greatest Common Divisor (gcd). It's much quicker than using prime factorization, and it's very easy to do. Just mod (modulo) the larger number by the smaller number, and then recursively use the result as the next modulo divisor. The number right before you reach 0 is your gcd. For example, for gcd(42, 51), we get 51 42 9 6 3 0. So 3 would be our answer.

The Euclidean Algorithm's big brother is the Extended Euclidean Algorithm, and that has many uses in cryptography and mathematics, including usage in both the AES symmetric cipher and the RSA public key encryption algorithm.

Our homepage: https://plaincipher.org