Question

4) 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

Answer:

Greatest common divisor of 313,626 and 152,346 is 6

s = -3581 and t = 7373

Step-by-step explanation:

1. gcd(313626, 152346) = gcd(152346, 8934)   since 313626 = (2 × 152346) + 8934
2. gcd(152346, 8934) = gcd(8934, 468)   since 152346 = (17 × 8934) + 468
3. gcd(8934, 468)  = gcd(468, 42)            since 8934 = (19 × 468) + 42
4. gcd(468, 42)  = gcd(42, 6)                     since 468 = (11 × 42) + 6
5. gcd(42, 6) = gcd(6, 0)                            since 42 = 7 × 6 + 0
6. 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