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.

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

s = -3581 and t = 7373

Step-by-step explanation:

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

whats the question?

step-by-step explanation: