a) Find an inverse of a modulo m for the following pair of relatively prime inte

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 Example 3.7.1 p. 167 of the Course Notes (also given in Rosen 7th edition page 276 example 2).

b) Beside your solution in part a), identify two other inverses of 2 mod 17.  

Hint: All of these inverses are congruent to each other mod 17

c) One of your answers for part a) or part b) may be a non-negative integer <17; if so, use that inverse for this problem. If not, identify a non-negative inverse of 2 modulo 17 that is <17 and use it for this problem.  

Use the non-negative inverse of 2 modulo 17 that is <17 to solve the following congruence: 2x congruent to 8(mod 17) Show the steps used to determine your solution.

d) Determine if the congruence 2x congruent to 17(mod 8) has a solution for x. If there is a solution, determine a solution. If there is no solution, explain why not.

Explanation / Answer

(a)

Suppose phi(n) = n - 1. Then the set of every number less than n that is coprime to n has n - 1elements. This is a subset of the set of every number less than n, but it has the same finite cardinality,so thus they are equal (i.e. every number less than n is coprime to n). Suppose n has a divisor d that'snot 1 or n. Then 1 < d < n. But then, since d|n, we should have gcd(d, n) = d > 1, which contradictsthe fact that every number less than n is coprime to n. Thus d does not exist; n is prime

Applying the Euclidean algorithm

we get 17=(8)(2)+(1)

(2)(1)=2

gcd(2,17)=1 and it does have an inverse

Reversing the Euclidean expansion, I get

Working backwards we had

1=(1)(17) +(-8)(2)

so an inverse of 2 modulo 17 is -8.

(b) and other mod inverse of 2 mod 17 is

2*9=18

and 18 mod 17=1

so 9 is the inverse of 2 mod 17

The simplest (although maybe not the fastest) way to find the inverse of 2 modulo 17 is to just runthrough all the numbers between 1 and 16 until you find it. For example 2*1 = 2 shows that 1 is notan inverse of 2, 2*2 = 4 shows that 2 isn't, and similarly the calculations 2*3 = 6, 2*4 = 8, 2*5 = 10,2*6 = 12, 2*7 = 14, and 2*8 = 16 show that 3, 4, 5, 6, and 7 aren't inverses of 2 either. The key hereis that we know none of the numbers 6, 8, 10, 12, 14, 16 are = 1 (mod 17), so we aren't getting whatwe would get if we had an inverse. With 9, on the other hand, we have.

We note that 9 is an inverse of 2 modulo 17 ( 9*2 =18=1(mod 17)) thus (9)(2x)=(9)(7) mod 17

Using the associative rule and doing a bit of arithmetic, (9 · 2)x 12 mod 17,

so 1x 12 mod 17,

and so x 12 mod 17.

(c)

2x congruent to 8(mod 17)

gcd (2,17) is 1so there is a solution 1 is a factor of 8

Solving the congruence 2x 8(mod 17) is equivalent to solving the equation 2x = 8+ 17q for integers x and q.

We next use trial and error to look for the multiplicative inverse of 2 modulo 17. The numbers congruent to 1 modulo 17 are  6, 8, 10, 12, 14, 16 are = 1 (mod 17)

(d)  congruence 2x congruent to 17(mod 8)

2x 17(mod 8)

gcd of 2,8 is 2

but 2 is not a divisor of 17

so 2x 17(mod 8) has no solution.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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