a) Determine gcd(72345, 43215)
b) Determine gcd(3486, 10292)
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.