Ask Question
8 June, 15:08

Using the extended Euclidean algorithm, find the multiplicative inverse of a. 1234 mod 4321 b. 24140 mod 40902

+2
Answers (1)
  1. 8 June, 15:40
    0
    (a) The inverse of 1234 (mod 4321) is x such that 1234*x ≡ 1 (mod 4321). Apply Euclid's algorithm:

    4321 = 1234 * 3 + 619

    1234 = 619 * 1 + 615

    619 = 615 * 1 + 4

    615 = 4 * 153 + 3

    4 = 3 * 1 + 1

    Now write 1 as a linear combination of 4321 and 1234:

    1 = 4 - 3

    1 = 4 - (615 - 4 * 153) = 4 * 154 - 615

    1 = 619 * 154 - 155 * (1234 - 619) = 619 * 309 - 155 * 1234

    1 = (4321 - 1234 * 3) * 309 - 155 * 1234 = 4321 * 309 - 1082 * 1234

    Reducing this leaves us with

    1 ≡ - 1082 * 1234 (mod 4321)

    and so the inverse is

    -1082 ≡ 3239 (mod 4321)

    (b) Both 24140 and 40902 are even, so there GCD can't possibly be 1 and there is no inverse.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Using the extended Euclidean algorithm, find the multiplicative inverse of a. 1234 mod 4321 b. 24140 mod 40902 ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers