Share
Explore BrainMass

greatest common divisor

How do I use the Euclidean Algorithm for determining the greatest common divisor of two integers?

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.

$2.19