×
×

# a) Define the greatest common divisor of two ISBN: 9780073383095 37

## Solution for problem 9RQ Chapter 4.R

Discrete Mathematics and Its Applications | 7th Edition

• Textbook Solutions
• 2901 Step-by-step solutions solved by professors and subject experts
• Get 24/7 help from StudySoup virtual teaching assistants Discrete Mathematics and Its Applications | 7th Edition

4 5 1 399 Reviews
20
0
Problem 9RQ

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. When does each method work best?

c)  Find the greatest common divisor of 1,234,567 and 7,654.32 1.

d)  Find the greatest common divisor of 2335577911 and 2937557313.

Step-by-Step Solution:
Step 1 of 3

Step1

a) Define the greatest common divisor of two integers.

Definition of  the greatest common divisor of two integers is

The greatest common divisor (gcd) of two  integers, which are not all zero, is the largest positive integer that divides. each of the integers. For example, the gcd of 9 and 18 is 9.

Step2

b)  Describe at least three different ways to find the greatest common divisor of two integers. When does each method work best?

Three different ways to find the greatest common divisor of two integers are:-

1. Prime Factorization Method :- The initial step is to break each number into its prime factorization, then recognise all the factors the two numbers have in common. Multiply these together. The result is the greatest common divisor.

2.The Euclidean Algorithm :- This technique requests that you perform progressive division, first of the smaller of the two numbers into the larger, followed by the resulting remainder divided into the divisor of each division until the remainder is equal to zero. At that moment, see the remainder of the last division – that will be the greatest common divisor.

3.Binary method:-An alternative method of computing the gcd is the binary gcd method which uses only subtraction and division by 2.

Step3

c)  Find the greatest common divisor...

Step 2 of 3

Step 3 of 3

##### ISBN: 9780073383095

Unlock Textbook Solution