Solve Modular Inverses Homework

[Gale]

Homework Statement

3.) For each of the following a mod n, find a≡1 mod n, i.e. find an integer
x with ax≡1 mod n, or explain why such an integer does not exist:
5' mod 11; (21)' mod 28; 2' mod 101; 4' mod 101:

4.) Let n = 2k+1 be an odd number. What is 2'≡1 mod n? What happens
when n = 2k is even? Now find the multiplicative inverse of 3 mod n:
First suppose n = 3k + 2 for some k. What is 3' mod n? (It looks a
lot like the answer for 2'.) If n = 3k + 1, find 3' mod n as follows.
First find a number x such that 3x≡-1 mod n, and then note that
3(-x)≡1 mod n; finally, write -x as a number between 0 and n - 1.
What if n = 3k?

Homework Equations

ax+by=c, has a solution if gcd(a,b)|c

Euclidean Algorithm

The Attempt at a Solution

So I'm just not sure I've done these problems the right way, or the most efficient way. My answers are often negative, but I figured since its congruence classes, when my answers are -x, it really means [-x] which should be okay? But is that a cop-out? Should I be trying to find representatives between zero and n? Question 4 seems to imply that, but I didn't exactly do the problem the way my teacher suggested, I did it how it made sense to me. So could someone check my work?

Also, in Algebra in general I feel like I write my answers in a weird way or in an odd order. If it seems I've done that, please let me know how you would write your answers in a more elegant or simple to understand way.

3) ax≡1 mod n → ax+kn=1
gcd(5,11)= 1 = 11-2(5) → 5' mod 11= -k

gcd(21,28)= 7 = 28-21. 7 does not dive 1, therefore no solution exists.

gcd(2,101)= 1 = 101-50(2) → 2' mod 101= -50

gcd(4,101)= 1 = 101-25(4) → 4' mod 101= -25

4)n=2k +1, n is odd,
2': gcd(2,2k+1)=1= (2k+1)+ (-k)(2) → 2' mod (2k+1)= -k

n=2k
2': gcd(2,2k)= 2. 2 does not divide 1→ solution does not exist.

n=3k+2
3': gcd(3,3k+2)= 1= 2(3k+2)+ (-2k-1)(3) → 3' mod (3k+2)= -2k-1

n=3k+1
3': gcd(3,3k+1)=1 = (3k+1)+ (-k)(3) → 3' mod (3k+1)= -k

n=3k
3': gcd(3,3k)= 3. 3 does not divide 1 → solution does not exist.

 

[Dick]

I didn't check every part but it looks generally ok to me. Take the first one. You wrote 5' mod 11= -k, I think you meant 5' mod 11= -2, i.e. that the multiplicative inverse of 5 is -2. That works fine. (-2)*5=(-10)=1 mod 11. You could also express that as a nonnegative value if you want. [-2]=[9] mod 11. So 9*5=45=1 mod 11. Both work fine.

 

[HallsofIvy]

Homework Statement

3.) For each of the following a mod n, find a≡1 mod n, i.e. find an integer
x with ax≡1 mod n, or explain why such an integer does not exist:
5' mod 11; (21)' mod 28; 2' mod 101; 4' mod 101:

A very simple minded way to find the inverse of 5, mod 11:
There is no integer x such that 5x= 1 so look at 11+ 1= 12.
There is no integer x such that 5x= 12 so look at 12+ 11= 23.
There is no integer x such that 5x= 23 so look at 23+ 11= 34.
There is no integer x such that 5x= 34 so look at 34+ 11= 45.
5(9)= 45 so x= 9 (mod 11).

4.) Let n = 2k+1 be an odd number. What is 2'≡1 mod n?

Do you mean "show that 2^{-1}= 1 mod n" rather than "What is"?

What happens
when n = 2k is even? Now find the multiplicative inverse of 3 mod n:
First suppose n = 3k + 2 for some k. What is 3' mod n? (It looks a
lot like the answer for 2'.) If n = 3k + 1, find 3' mod n as follows.
First find a number x such that 3x≡-1 mod n, and then note that
3(-x)≡1 mod n; finally, write -x as a number between 0 and n - 1.
What if n = 3k?

Homework Equations

ax+by=c, has a solution if gcd(a,b)|c

Euclidean Algorithm

The Attempt at a Solution

So I'm just not sure I've done these problems the right way, or the most efficient way. My answers are often negative, but I figured since its congruence classes, when my answers are -x, it really means [-x] which should be okay? But is that a cop-out? Should I be trying to find representatives between zero and n? Question 4 seems to imply that, but I didn't exactly do the problem the way my teacher suggested, I did it how it made sense to me. So could someone check my work?

[-x] mod n is the same as [n- x].

Also, in Algebra in general I feel like I write my answers in a weird way or in an odd order. If it seems I've done that, please let me know how you would write your answers in a more elegant or simple to understand way.

3) ax≡1 mod n → ax+kn=1
gcd(5,11)= 1 = 11-2(5) → 5' mod 11= -k

Okay so what is k? Did you mean k= 2? Then saying that the inverse is -2 means it is in the same congruence class as 11- 2= 9.

gcd(21,28)= 7 = 28-21. 7 does not dive 1, therefore no solution exists.

Yes, that is correct. If 21x= 1 (mod 28) then 21x= 1+ 28n. That is the same as 21x- 28n= 7(3x- 4n) cannot be equal to 1 because 1 is not divisible by 7.

gcd(2,101)= 1 = 101-50(2) → 2' mod 101= -50

Yes, this is correct. And -50 is in the same congrunce class as 101- 50= 51. 2(51)= 102= 1 (mod 101).

gcd(4,101)= 1 = 101-25(4) → 4' mod 101= -25

Yes, this is correct. And -25 is in the same congruence class as 101- 25= 76. 4(76)= 304= 3(101)+ 1.

4)n=2k +1, n is odd,
2': gcd(2,2k+1)=1= (2k+1)+ (-k)(2) → 2' mod (2k+1)= -k

And, of course, -k= (2k- 1)- k= k+ 1 mod 2k+ 1. (k+1)(2)= 2k+ 2= (2k+ 1)+ 1.

n=2k
2': gcd(2,2k)= 2. 2 does not divide 1→ solution does not exist.

Yes, for any integer, i, 2i+ m(2k)= 2(i+ mk) is even while 2k+ 1 is odd.

n=3k+2
3': gcd(3,3k+2)= 1= 2(3k+2)+ (-2k-1)(3) → 3' mod (3k+2)= -2k-1

And -2k- 1= 3k+2- 2k- 1= k+ 1 mod 3k+2. 3(k+ 1)= 3k+ 3= (3k+ 2)+ 1.

n=3k+1
3': gcd(3,3k+1)=1 = (3k+1)+ (-k)(3) → 3' mod (3k+1)= -k

And ;-k= 3k+1- k= 2k+ 1 mod 3k+1. 3(2k+1)= 6k+ 3= 6k+ 2+ 1= 2(3k+ 1)+ 1.

n=3k
3': gcd(3,3k)= 3. 3 does not divide 1 → solution does not exist.

Yes. If 3x= 1 (mod 3k) then 3x= 1+ 3k so that 3x- 3k= 3(x- k)= 1 which is not possible.