Notes: Suppose (a, n) = 1, then there is an integer s such that as = 1 (mod n).

Question

Notes: Suppose (a, n) = 1, then there is an integer s such that as = 1 (mod n). This s is called the inverse of a, i.e., a-1 (mod n). The way to find the inverse is as follows:
1) Use the extended Euclidean algorithm to find s and t such that as + nt = 1;
2) Then a-1(mod n) = s.
In the lecture, we gave an example to find 37-1(mod 121) in three steps.
Step-1: use Euclidean algorithm to get the gcd(121, 37) although we knew it’s one.
Step-2: use extended Euclidean algorithm, which is reverse of Euclidean algorithm, to get s and t, such that 37s + 121t = 1. We got s = 36, t = -11, therefore 37-1(mod 121) = 36.
Step-3: verify that 37s = 1 (mod 121). 37×36 = 1332 = 11×121 + 1 = 1 (mod 121), so the congruence 37s = 1 (mod 121) is verified.

Here are the questions for you to solve:

A. Follow the steps described above, find 21-1 (mod 80).

B. Solve the congruence: 13x = 4 (mod 99).

Explanation / Answer

A) to find 21-1 in (mod 80) start off with the gcd( 80, 21 ) 80 = 3(21) + 17 21 = 1(17) + 4 17 = 4(4) + 1 ? gcd(21, 80) = 1. ? 1 = 1(17) - 4(4) 1= 1( 1(80) - 3(21 ) ) - 4( 1(21) - 1(17) ) 1 = 1(80) - 3(21) - 4(21) + 4(17) 1 = 1(80) -7(21) + 4( 1(80) - 3(21) ) 1 = 5(80) -7(21) -12(21) 1 = 5(80) - 19(21) Then to find the inverse, do (mod 80) on the entire equation: 1(mod80) = ( 5(80) - 19(21) )(mod 80) which ends up giving 1 = -19(21) (mod80) giving your value of s. To find the proper value of s, you find out what -19 is within (mod 80) [[ 80-19 ]] Which you can then verify. B) To Solve the congruence 13x (is congruent to) 4 (mod 99) First off solve for the inverse of 13, so then you end up with (13*13-1)x = 4(13-1) (mod99) Which results in x = 4(13-1) (mod99) Given that, simplify 4(13-1) within mod 99, (ie] if its over 99, bring it to its appropriate number within mod 99 ) From that, the equation x = a (mod n) --> x = nm + a where n e Z Using that you find that x = 99n + (4*13-1). Use the same steps in A to solve for 13 inverse.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.