GCD (24,20) IS 4. sINCE gcd(4,12 ) is 4 then GCD (24,2012 IS 4
USE Euclidem LGERITHM TO FIND THE gcd 722, 2413,209
To find the greatest common divisor (GCD) using the Euclidean Algorithm, you need to follow these steps:
Step 1: Start with two numbers, let's say 722 and 2413.
Step 2: Divide the larger number by the smaller number.
- 2413 ÷ 722 = 3 remainder 347
Step 3: Replace the larger number with the remainder and repeat Step 2.
- New pair: 722, 347
- 722 ÷ 347 = 2 remainder 28
Step 4: Repeat Step 3 until you get a remainder of 0.
- New pair: 347, 28
- 347 ÷ 28 = 12 remainder 11
- New pair: 28, 11
- 28 ÷ 11 = 2 remainder 6
- New pair: 11, 6
- 11 ÷ 6 = 1 remainder 5
- New pair: 6, 5
- 6 ÷ 5 = 1 remainder 1
- New pair: 5, 1
- 5 ÷ 1 = 5 remainder 0
Step 5: The GCD is the last nonzero remainder.
- GCD(722, 2413) = 1
Now, let's find the GCD of three numbers, 722, 2413, and 209, using the Euclidean Algorithm:
Step 1: Start with three numbers, 722, 2413, and 209.
Step 2: Apply the Euclidean Algorithm to the first two numbers (722, 2413).
- GCD(722, 2413) = 1 (as calculated above)
Step 3: Replace the third number with the calculated GCD.
- New pair: 1, 209
- GCD(1, 209) = 1 (as both numbers are relatively prime)
Step 4: The GCD is the last nonzero remainder.
- GCD(722, 2413, 209) = 1
Therefore, the GCD of 722, 2413, and 209 is 1.