Ask Question
1 November, 01:35

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)
  1. 1 November, 01:43
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers