Explore BrainMass

Explore BrainMass

    greatest common divisor

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED 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 November 24, 2022, 11:30 am ad1c9bdddf

    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.