How do I use the Euclidean Algorithm for determining the greatest common divisor of two integers?© BrainMass Inc. brainmass.com October 15, 2018, 3:44 pm ad1c9bdddf - https://brainmass.com/computer-science/algorithms/greatest-common-divisor-2588
The Euclidean Algorithm, as defined, is the following:
Let a = bq + r, where a, b, q, and r are integers. Then gcd (a, b) = gcd(b, r)
What exactly does this mean? It means that if we are given two numbers, we have an efficient way to calculate the largest number that will divide into both integers evenly.
How does it work? It can be shown by example. We start with a simple one to describe the process.
ex.1) Find the greatest common divisor ...
The greatest common divisor is determined.