(a) Find an inverse of a modulo m for the following pair of relatively prime int
ID: 3758946 • Letter: #
Question
(a) Find an inverse of a modulo m for the following pair of relatively prime integers, a=2, m=17. Show each step as you follow the method given in Rosen 7th edition page 276 example 2 and also given in Example 3.7.1 p. 167 of the Course Notes.
(b) Use the inverse of 2 modulo 17 that you found in part a) to solve the following congruence: 2x 8(mod 17)
Show the steps used to determine your solution.
(c) Determine if the congruence 2x 17(mod 8) has a solution for x. If there is no solution, explain why not and if there is a solution, find a solution.
Explanation / Answer
a) a=2, m=17
1. 17=28+1
2. 2=12+0
1=1782
From your equation 1=178×21=178×2, the coefficient in front of the 2 is its inverse; in other words, this is 88. Check: 2×8=161(mod17)2×8=161(mod17).
If you prefer to express the inverse within the range from 00 to 1717, note that 89(mod17)89(mod17).
Finally, another way to find the inverse: we're looking for a number aa for which 2a1(mod17)2a1(mod17). Observing that 181(mod17)181(mod17) and that 18 is a multiple of 22, we can see that 2×9=181(mod17)2×9=181(mod17). This worked out nicely by observation because the numbers are small enough.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.