Find an inverse of o modulo m for the following pair of relatively prime integer

Question

Find an inverse of o 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 7^th edition page 276 example 2 and also given in Example 3.7.1 p. 167 of the Course Notes. Use the inverse of 2 modulo 17 that you found in part a) to solve the following congruence: 2x 8(mod17). Show the steps used to determine your solution. 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)

We know 2 and 17 are coprime

2*9=18=17+1

So, 2*9=1 mod 17

Hence, 9 is inverse of 2 modulo 17

b)

2x=8 mod 17

Multiplying both sides by inverse of 2 modulo 17 ie 9 gives

We can multiply because 9 and 17 are coprime

9*2x=9*8 mod 17

18x=72 mod 17

x=68+4=4 mod 17

x=4 mod 17

c)

17=16+1=1 mod 8

So given equation becomes:

2x=1 mod 8

But, 2x is even for any integer x

HEnce, 2x can be:0,2,4,6 mod 8

SO no solution is possible

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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