Hi,
I want to solve this question using mod arithmetic:

7/3 mod 8.

Somebody told me to do it using multiplicative inverse:

7 (Multiplicative inverse of 3) mod 8

I can't find any example related to the above method. Somebody please guide me.

Zulfi.

 

You can't find a single thing by Googling "modular multiplicative inverse"????

 

Hi,
They have examples like this:

63x congruent to (1 (mod 17))

I am looking for a division example. But I have solved this one:
7/3(Multiplicative Inverse of 3) mod 8
7 * 3 mod 8
21 mod 8
=5.
But now I have problem with this:

9/6 mod 11, that would be 9 * (MI of 6) mod 11; 9 * 6 mod 11; 54 mod 11 i.e. 9 or it should be 3/2 mod 11, that would be 3 * (MI of 2) mod 11; 6 mod 11= 6

Which answer is correct? somebody please guide me.

Zulfi.

 

Do you understand what a multiplicative inverse is?

Do you understand WHY 3 is the multiplicative inverse of 3 (mod 8)?

What is the multiplicative inverse of 6 in a mod 11 world? it is NOT 6.

 

mod operator is not distributive.

(A + B) mod M ≠(A mod M) + (B mod M)

(A * B) mod M ≠ (A mod M) * (B mod M)

(A / B) mod M ≠ (A mod M) * (1/B mod M)

Perform the operation in the braces first before performing the mod operation.

 

mod operator is not distributive.

(A + B) mod M ≠(A mod M) + (B mod M)

(A * B) mod M ≠ (A mod M) * (B mod M)

(A / B) mod M ≠ (A mod M) * (1/B mod M)

Perform the operation in the braces first before performing the mod operation.

So are you saying that in order to perform

(A^B) mod N

we have to calculate A^B before we perform the mod operation?

If so, then how many digits would we need to allow for A^B if both are 4096 bit numbers (i.e. have about 1200 digits)?

The number that describes the number of bits we would have to have has about 4096 bits in it while the number that describes the number of atoms in the known universe only has about 266 bits. So it would be physically impossible, astronomically so, to perform the exponentiation and then the mod operation. Yet we evaluate expressions like this all the time using very modest hardware (such as smartcards). How do we do it -- we distribute the modular reductions!

Again, the distributive rule for modular reduction retains the final modular reduction.

(A + B) mod M = [(A mod M) + (B mod M)] mod M

(A * B) mod M = [(A mod M) * (B mod M)] mod M

(A / B) mod M = [(A mod M) * (1/B mod M)] mod M

keeping in mind that division is not defined the way that it is in the integer world, but instead is a shorthand for multiplication by the multiplicative inverse of the denominator -- which may not exist.

 

Hi MrChips- God bless you. <mod operator is not distributive>: I am not sure . But I am using a little bit different formula from the formula which you showed. This is a problem related to Number theory. We have to solve it without calculator. However my formula is same which was later on told to me by WBahn.
<Do you understand what a multiplicative inverse is? >
Yes:

A number only has a multiplicative inverse mod n when that number is relatively prime with n.

Now GCD of (11, 6) is not '1'. So what I have to do now?

Somebody please guide me.

Zulfi.

 

Hi MrChips- God bless you. You are right. But I am using a little bit different formula. The formula is same which was later on told to me by WBahn.
<Do you understand what a multiplicative inverse is? >
Yes:


Now GCD of (11, 6) is not '1'. So what I have to do now?

Zulfi.

So if the GCD of (11, 6) isn't 1, what is it?

 

@WBahn Of course you are correct. However, if I have to determine (A/B) mod M I am going to calculate (A/B) first regardless of what you say.

 

Hi,
<So if the GCD of (11, 6) isn't 1, what is it? >

Sorry I am wrong. Its '1'. I don't know how I said that thing.

<Do you understand WHY 3 is the multiplicative inverse of 3 (mod 8)? >
I can't understand. I thought its something related to relative prime. Please guide me.

Zulfi.

 

@WBahn Of course you are correct. However, if I have to determine (A/B) mod M I am going to calculate (A/B) first regardless of what you say.

What is (48/6) mod 9?
What is (30/6) mod 9?
What is (12/6) mod 9?

 

Hi,
<So if the GCD of (11, 6) isn't 1, what is it? >

Sorry I am wrong. Its '1'. I don't know how I said that thing.

<Do you understand WHY 3 is the multiplicative inverse of 3 (mod 8)? >
I can't understand. I thought its something related to relative prime. Please guide me.

Zulfi.

Forget about modular arithmetic for a bit and let's just work with normal numbers.

What is the additive inverse of a number? It's that value that, when added to the original number, yields zero (since zero is the additive identity).

What is the multiplicative inverse of a number? It's that value that, when multiplied by the original number, yields one (since one is the multiplicative identity).

The same definitions carry over to modular arithmetic.

If you have a number, say A, in a (mod N) world, then the additive inverse is any value of B that

(A+B) ≡ 0 (mod N)

So the (principal) additive inverse of 7 (mod 15) is 8 because 7+8 = 15 which is congruent to 0 (mod 15). So B can be any integer of the form B+kN where k is any integer, or in this specific example,

B = 8 + k·15

Notice that if k=-1, the B = -7, which is what we would expect (namely that -7 is one of the infinitely many additive inverses of 7 in a mod 15 world).

If you have a number, say A, in a (mod N) world, then the multiplicative inverse is any value of B such that

(A·B) ≡ 1 (mod N)

If A=7 and N=15, then what we are looking for is a value of B such that

7·B = 1 + k·N for some value of k.

So let's make of list of the possible values for the right hand side for the first several values of k: {1,16,31,46,61,76,91,106,121,136,151,166,181,196,211,226}

Are any of those numbers divisible by 7? Yes, 91 which is k = 6. So now we can solve for B:

7·B = 1 + k·N
7·B = 1 + 6·15
B = (1 + 6·15) / 7 = 13

So 13 is the multiplicative inverse of 7 in a mod 15 world because

Now, this trial and error method works fine for small numbers, but it get impractical pretty fast. Fortunately, the Extended Euclidean Algorithm is an extremely efficient way to find multiplicative inverses (and whether or not they exist) even for gargantuan numbers like the kind that are used in cryptography containing over a thousand digits.

So do you now see why 3 is the multiplicative inverse of 3 in a mod 8 world?

So what is the multiplicative inverse of 6 in a mod 11 world?

 

Hi,
Thanks for your great work. But really speaking, its too hard for me to understand. I have followed a simple technique given at:


https://www.rookieslab.com/posts/ho...ve-inverse-of-a-number-modulo-m-in-python-cpp

Modular Multiplicative Inverse of a number A in the range M is defined as a number B such that (A x B) % M = 1.

A= 6

B= ?

M=11

(6 * B) % M = 1

B= 2 B/c: 12%11 = 1



(6*2) %11 ==1

Is MI of 6 be 2, fine?

Zulfi.

 

Hi,
For the first case:
A=3

B=?

M = 8

(A* B) % M = 1

(3 * B) % 8 =1: B =3

Thanks for your cooperation.
Zulfi.

 

Which technique did you use? They described several techniques on that webpage.

If you are just doing trial and error to find a value for B such that (A·B) mod N is 1, then that's the same technique. As I said, it works nice for small numbers, but what if you were asked to find the multiplicative inverse of

A mod N

where A = 143 and N = 210

or where A = 46410 and N = 84323

The amount of work literally increases exponentially as you increase the number of digits. You can sense how much harder it is going from 1 and 2 digit numbers to 3 and 5 digit numbers. Now imagine that the numbers you have to deal with have 1200 digits in them.

 

Will your technique solve my problem for large values also?

Zulfi.

 

Which technique? I talked about two of them -- trial and error and the Extended Euclidean algorithm.

What can I say about them beyond what I said above? Namely: "Now, this trial and error method works fine for small numbers, but it get impractical pretty fast. Fortunately, the Extended Euclidean Algorithm is an extremely efficient way to find multiplicative inverses (and whether or not they exist) even for gargantuan numbers like the kind that are used in cryptography containing over a thousand digits. "