Purchase Solution

greatest common divisor

Not what you're looking for?

Ask Custom Question

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

Purchase this Solution
Solution Summary

The greatest common divisor is determined.

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

Purchase this Solution
Free BrainMass Quizzes
Basic Networking Questions

This quiz consists of some basic networking questions.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

View More Free Quizzes
Related BrainMass Solutions

  • Ring Theory : Associate of a Greatest Common Divisor and Euclidean Rings

    In a Euclidean ring , any associate of a greatest common divisor is a greatest common divisor.

  • Ring Theory: Greatest Common Divisor (GCD)

    111047 Ring Theory: Greatest Common Divisor (GCD) Please respond to the following question: Find the greatest common divisor of the following polynomials over F, the field of rational numbers: x^3 - 6x^2 + x + 4 and x^5 - 6x + 1 Please see the attached

  • Greatest Common Divisor in Java

    239119 Greatest Common Divisor in Java I have to write an interactive program that will find the Greatest common divisor between two inputted integers.

  • Euclidean Rings and GCD

    , where is the greatest common divisor of and .

  • Discrete Mathematics and its Applications : Greatest Common Divisors

    56004 Discrete Mathematics and its Applications : Greatest Common Divisors A) Define the greatest common divisor of two integers. b) Describe at least three different ways to find the greatest common divisor of two integers.

  • Euclidean algorithm

    49616 Greatest common divisor Find the greatest common divisor of a) 705 and 1962 b) 5339 and 2565 Please see the attached file. This shows how to find the greatest common divisor using the Euclidean algorithm.

  • divisibility

    34168 Finding the Greatest Common Divisor Find the greatest common divisor of the following pairs: a)527, 765 (use technique like 527=341*1+186) b)361, 1178 (use technique like 527=341*1+186) c) -find the gcd (d) of 299, 481 (use technique like

  • principal ideal domain

    So d is a common divisor of a and b. Now I claim that d is the greatest common divisor. Suppose d' is any common divisor of a and b and we consider the ideal I' = Since d'|a and d'|b, then a,b are in I' = .

  • Euclidean Algorithm : Finding the Greatest Common Divisor

    11579 Euclidean Algorithm : Finding the Greatest Common Divisor Use the euclidean algorithm to find the greatest common divisor of 981 and 1234. Please see the attached file for the complete solution. Thanks for using BrainMass.

  • Let G be a group.

    Show that O(a^n) = O(a)/(O(a),n) for all a belongs to G, where n is an integer and (O(a), n) = greatest common divisor of O(a) and n. Let G be a group.

View More Related Solutions