SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
William Stallings
Chapter:
Introduction To Number Theory
Exercise:
Problems
Question:12 | ISBN:9781292158587 | Edition: 7

Question

a) Determine gcd(72345, 43215)

b) Determine gcd(3486, 10292)

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

a)

To determine the greatest common divisor (gcd) of 72345 and 43215 by using the Euclidean algorithm:

Step 1: Divide 72345 by 43215, and obtain the remainder.
        72345 ÷ 43215 = 1 remainder 29130

Step 2: Divide 43215 by 29130, and obtain the remainder.
        43215 ÷ 29130 = 1 remainder 14085

Step 3: Divide 29130 by 14085, and obtain the remainder.
        29130 ÷ 14085 = 2 remainder 945

Step 4: Divide 14085 by 945, and obtain the remainder.
        14085 ÷ 945 = 14 remainder 615

Step 5: Divide 945 by 615, and obtain the remainder.
        945 ÷ 615 = 1 remainder 330

Step 6: Divide 615 by 330, and obtain the remainder.
        615 ÷ 330 = 1 remainder 285

Step 7: Divide 330 by 285, and obtain the remainder.
        330 ÷ 285 = 1 remainder 45

Step 8: Divide 285 by 45, and obtain the remainder.
        285 ÷ 45 = 6 remainder 15

Step 9: Divide 45 by 15, and obtain the remainder.
        45 ÷ 15 = 3 remainder 0

Step 10: Since the remainder is now 0, we stop.

The gcd(72345, 43215) is the last non-zero remainder, which is 15.

Therefore, gcd(72345, 43215) = 15.

b)

 To determine the gcd of 3486 and 10292 by using  the Euclidean algorithm:

Step 1: Divide 10292 by 3486, and obtain the remainder.
        10292 ÷ 3486 = 2 remainder 3320

Step 2: Divide 3486 by 3320, and obtain the remainder.
        3486 ÷ 3320 = 1 remainder 166

Step 3: Divide 3320 by 166, and obtain the remainder.
        3320 ÷ 166 = 20 remainder 120

Step 4: Divide 166 by 120, and obtain the remainder.
        166 ÷ 120 = 1 remainder 46

Step 5: Divide 120 by 46, and obtain the remainder.
        120 ÷ 46 = 2 remainder 28

Step 6: Divide 46 by 28, and obtain the remainder.
        46 ÷ 28 = 1 remainder 18

Step 7: Divide 28 by 18, and obtain the remainder.
        28 ÷ 18 = 1 remainder 10

Step 8: Divide 18 by 10, and obtain the remainder.
        18 ÷ 10 = 1 remainder 8

Step 9: Divide 10 by 8, and obtain the remainder.
        10 ÷ 8 = 1 remainder 2

Step 10: Divide 8 by 2, and obtain the remainder.
        8 ÷ 2 = 4 remainder 0

Since the remainder is now 0, we stop.

The gcd(3486, 10292) is the last non-zero remainder, which is 2.

Therefore, gcd(3486, 10292) = 2.

0 0

Discussions

Post the discussion to improve the above solution.