60.1k views
5 votes
Given 12345 and 677, the extended Euclidean algorithm returns (1, 132, -2407). What is 677⁻¹ mod 12345?

1 Answer

5 votes

Final answer:

The modular inverse of 677 modulo 12345 is found using the extended Euclidean algorithm, which in this case gives -2407. To get a positive inverse, add 12345 to -2407 until it is positive, resulting in 10,938.

Step-by-step explanation:

The student has asked how to find the modular inverse of 677 modulo 12345, using the extended Euclidean algorithm. The extended Euclidean algorithm returns a tuple of three values (g, x, y) such that g = ax + by, where g is the greatest common divisor of a and b, and x and y are the coefficients such that ax + by = g. In this case, since the algorithm returns (1, 132, -2407), it means 12345*132 + 677*(-2407) = 1. Looking at this equation modulo 12345, we can notice that 677*(-2407) is congruent to 1 modulo 12345, so -2407 is the modular inverse of 677 modulo 12345. However, we conventionally represent the modular inverse as a positive integer, so we add 12345 to -2407 until we get a positive value. The result is 10,938, which is the inverse of 677 modulo 12345.

User Lovable
by
7.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.