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.

Question

Mathematics

Amina

30 March, 09:14

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.

+2

Answers (1)

Know the Answer?

Fernando Fernandez · Answer 1

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