Q: I want to know how can you show if a number has an inverse or not. Example: show the number 6 does not have a multiplication inverse modulo 15.

For: A mod C A only has an inverse mod C, if A and C are coprime i.e. gcd(A,C)=1 gcd(6,15)=3 thus 6 has no inverse mod 15

Q: how can i proof that if: k =a*b mod n then k^-1 = a^-1 * b^-1 mod n

Here's a big hint: Start from this congruence K * K^-1 ≡ 1 (mod N) Then try to reach this congruence: K^-1 ≡ A^-1 * B^-1 (mod N) You will need to use this: K ≡ A * B (mod N) and the property that: X * X^-1 ≡ 1 (mod N) Good Luck

Q: if ab≡1 mod n, and b<n, how do I prove that b is unique.

Typically, when you have some thing with some property and you want to prove it is unique, you do the following: Suppose that both b and c have that property. Show that b = c. This shows that everything that has that property is b, i.e. there isn't anything with that property that is not b. This case is similar: - we would assume that both b and c have the same property i.e. both b and c are inverses of a (mod n) - we need to show that b ≡ c (mod n) Proof: Suppose b and c are inverses of a (mod n) Since b is an inverse of a (mod n): a * b ≡ 1 (mod n) Since c is an inverse of a (mod n): a * c ≡ 1 (mod n) a * b ≡ 1 (mod n) subsitute (a * c) into right hand side a * b ≡ a * c (mod n) multiply both sides by a^-1 a * a^-1 * b ≡ a * a^-1 * c (mod n) 1 * b ≡ 1 * c (mod n) b ≡ c (mod n) Hope this makes sense

Question 1

Did the Extended Euclidean Algorithm articles ever get published? These modular arithmetic articles have been fantastic, and I'm really looking forward to the next articles!

Accepted Answer

Sorry for the delay, we've been meaning to update them. I will try to do this in the next week or two. I promise!

Question 2

Wait, I thought you could divide by any number in modular arithmetic as long as the number inside the modulus was relatively prime to the number you were dividing by. Do you always have to use modular inverses?

I will find the faster method before Brit Cruise posts it up...
EDIT: 
a mod b
a^2 mod b
a^3 mod b
...
Eventually, one of these expressdions will get to 1. If b is prime, then a^(b-1) mod b will be congruent to 1.
a^n mod b=1
a^(n-1)*a mod b=1
a^(n-1) mod b is the modular inverse of a mod b and if b is prime, a^(b-2) is the modular inverse of a mod b.

That's as close as I got.

This was edited just before the Extended Euclidean Algorithm was posted.

Accepted Answer

Division doesn't exist in modular arithmetic. However, many of the things we can do with modular inverses act the same as or similar to division.

e.g. 
if we have a * k ≡ b * k (mod C) where k is coprime to C we can eliminate the k from each side and say:
a  ≡ b (mod C)

How did we eliminate k ?
We know that k has an inverse mod C since k is coprime to C. (We don't need to know what the value of the inverse is. We just need to know an inverse exists.)
So when we have a * k ≡ b * k (mod C) , we multiply both sides by k^-1
a * k * k^-1 ≡ b * k * k^-1 (mod C)
but since k * k^-1 = 1 we have
a * 1  ≡  b * 1 (mod C)
a  ≡  b  (mod C)

So as you can see, we are not dividing, but instead using modular inverses. The end result looks like we are dividing and intuitively what we are doing is similar, but is important to note that we don't have division in modular arithmetic, but in some cases we do have inverses.

Hope this makes sense

Question 3

Cameron said there is no division in modular arithmetic. But  my problem sais:
Solve:  11x ≡ 11 mod33
Now the only way I can think of it is to devide by 11 both sides plus the mod
So we get  x ≡ 1 mod3
And its correct! But if theres no division how would I solve it?? 
Please clarify to me, thanks in advance

Accepted Answer

There is no division in modular arithmetic.

Suppose we had an equation like:
A * x ≡ B mod C

***If A was coprime to C***
i.e. gcd(A,C)=1 
To solve for x we would multiply both sides by the modular inverse of A mod C

A * A^-1 * x ≡ B * A^-1 mod C
But A * A^-1 mod C = 1
1 * x ≡ B * A^-1 mod C
And 1 * x mod C = x
x ≡ B * A^-1 mod C

e.g. 
5 * x ≡ 2 mod 14
5 is coprime with 14, so 5 has an inverse mod 14
5 * 5^-1 * x ≡ 2 * 5^-1 mod 14
1 * x ≡ 2 * 5^-1 mod 14
x ≡ 2 * 5^-1 mod 14
5^-1 mod 14 is 3, since 3 * 5 mod 14 = 15 mod 14 = 1
x ≡ 2 * 3 mod 14
x ≡ 6 mod 14

***But what do we do if A is NOT coprime to C***
i.e. gcd(A,C) != 1 ?
To solve for x, we need to convert the expression to an equivalent form
A * x ≡ B mod C
is equivalent to:
A * x = K * C + B where K is an integer
This is just a regular equation, so we can use divide here.
If A,B and C are ALL divisible by D then we can divide both sides of the equation to get:
(A/D) * x = K * (C/D) + (B/D) where K is an integer
Note that:(A/D) , (C/D), and (B/D) will all be integers
We can then convert this new equation into a congruence to get:
(A/D) * x ≡ (B/D) mod (C/D)

So, it only seems like we can divide by D when A,B and C are ALL divisible by D
(but it isn't really division, it only looks similar to division)

But you need to be careful !! If you solve for x now, you will have an answer mod (C/D)
You will need to find all the possible values where 0 <= x < C to be able to express your answer mod C

e.g.
12 * x ≡ 15 mod 45 
is equivalent to:
12 * x = K * 45 + 15
Divide both sides by 3
4 * x = K * 15 + 5
is equivalent to:
4 * x ≡ 5 mod 15
This new expression can then be solved using the method for A coprime to C
4 * x ≡ 5 mod 15
4 * 4^-1 * x ≡ 5 * 4^-1 mod 15
4^-1 mod 15 is 4 since 4 * 4 mod 15 = 16 mod 15 = 1 
x ≡ 5 * 4 mod 15
x ≡ 20 mod 15
x ≡ 5 mod 15
(But this answer is mod 15, we need our answer to be mod 45)
our expression is equivalent to x = K * 15 + 5 where K is an integer
So the possible values of 0 <= x < 45 are:
5,20,35
So our answer is:
x ≡ 5, 20, or 35 mod 45

So, as far as 11 * x ≡ 11 mod 33 goes, you can obtain x ≡ 1 mod 3 from it.
This only works because all of the terms are divisible by 11. Again, what's happening is not really division (it only seems similar).
Additionally, the solution needs to be converted to mod 33.
i.e. x ≡ 1,4,7,10,13,16,19,22,25,28, or 31 mod 33

Hope this makes sense

Question 4

I want to know how can you show if a number has an inverse or not.
Example: show the number 6 does not have a multiplication inverse modulo 15.

Accepted Answer

For: A mod C
A only has an inverse mod C, if A and C are coprime i.e. gcd(A,C)=1
gcd(6,15)=3 thus 6 has no inverse mod 15

Question 5

how can i proof that if: k =a*b mod n
then 
k^-1 = a^-1 * b^-1 mod n

Accepted Answer

Here's a big hint:

Start from this congruence
K * K^-1 ≡ 1 (mod N)
Then try to reach this congruence:
K^-1 ≡ A^-1 * B^-1 (mod N)

You will need to use this: K ≡ A * B (mod N)
and the property that: X * X^-1 ≡ 1 (mod N)

Good Luck

Question 6

if ab≡1 mod n, and b<n, how do I prove that b is unique.

Accepted Answer

Typically, when you have some thing with some property and you want to prove it is unique, you do the following:
Suppose that both b and c have that property.
Show that b = c.
This shows that everything that has that property is b, i.e. there isn't anything with that property that is not b.

This case is similar: 
- we would assume that both b and c have the same property i.e. both b and c are inverses of a (mod n)
- we need to show that b ≡ c (mod n)

Proof:
Suppose b and c are inverses of a (mod n)
Since b is an inverse of a (mod n):
a * b ≡ 1 (mod n)
Since c is an inverse of a (mod n):
a * c ≡ 1 (mod n)

a * b ≡ 1 (mod n)
subsitute (a * c) into right hand side
a * b ≡ a * c (mod n)
multiply both sides by a^-1
a * a^-1 * b ≡ a * a^-1 * c (mod n)
1 * b ≡ 1 * c (mod n)
b ≡ c (mod n)

Hope this makes sense

Computer science

Course: Computer science > Unit 2

Modular inverses

What is an inverse?

What is a modular inverse?

How to find a modular inverse

Example: A=3, C=7

Step 1. Calculate A * B mod C for B values 0 through C-1

**Step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1**

Example: A=2 C=6

**Step 1. Calculate A * B mod C for B values 0 through C-1**

**Step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1**

This method seems slow...

Want to join the conversation?