Answer:
Greatest common divisor of 313,626 and 152,346 is 6
s = -3581 and t = 7373
Step-by-step explanation:
- gcd(313626, 152346) = gcd(152346, 8934) since 313626 = (2 × 152346) + 8934
- gcd(152346, 8934) = gcd(8934, 468) since 152346 = (17 × 8934) + 468
- gcd(8934, 468) = gcd(468, 42) since 8934 = (19 × 468) + 42
- gcd(468, 42) = gcd(42, 6) since 468 = (11 × 42) + 6
- gcd(42, 6) = gcd(6, 0) since 42 = 7 × 6 + 0
- gcd(6, 0) = 6
Working backwards from the third-to-last line,
6 = 468 - (11 × 42) (line 4)
42 = 8934 - (19 × 468) (line 3)
Substituting this for 42 in the previous,
6 = 468 - 11(8934 - (19 × 468))
6 = (210 × 468) - (11 × 8934)
Still working backwards,
468 = 152346 - 17 × 8934 (line 2)
Substituting this for 468 in the previous,
6 = (210 × (152346 - 17 × 8934)) - (11 × 8934)
6 = (210 × 152346) - (8934 × 3581)
On line 1,
8934 = 313626 - 2 × 152346
Substituting this for 8934 in the previous,
6 = (210 × 152346) - ((313626 - 2 × 152346) × 3581)
6 = (7372 × 152346) - (313626 × 3581)
Hence, s = -3581 and t = 7373
