Question

Use the Euclidean algorithm to find the greatest common divisor d of 313,626 and 152,346. Then use this algorithm to find integers s and t to write d as 313,626 s 152,346 t. Solving these types of equations, for much larger integers, is central to encryption schemes such as RSA (public key) encryption.

Answer 1

313,626 = 2 * 152,346 + 8934

152,346 = 17 * 8,934 + 468

8,934 = 19 * 468 + 42

468 = 11 * 42 + 6

6 divides 42, so the GCD of 313,626 and 152,346 is 6.