Explore BrainMass

greatest common divisor

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

Solution Preview

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 ...

Solution Summary

The greatest common divisor is determined.