# modular inverse arithmetic

• Sep 24th 2012, 11:14 AM
nitin1
modular inverse arithmetic
Can anyone explain me with example that what exactly it is ? can i have multilpcative modular inverse of a number mod m ? please celarify.
• Sep 24th 2012, 11:27 AM
johnsomeone
Re: modular inverse arithmetic
Q: What is a "normal" multiplicative inverse? A: it's the thing you multiply by to get 1.
That's why the multiplicative inverse of 3 is 1/3 - because 3(1/3) = 1.
It's the same thing in modular arithmetic, except now it works like this:
Q: What do you have to multiply 3 by to get 1, MODULO 7? A: 5
That's because (3)(5) = 15 = 1 + 14 = 1 MODULO 7.
Thus the multiplicative inverse of 3 is 5, when working mod 7.

0 never has a multiplicative inverse. In modular arithmetic as well as regular arithmetic, you can never divide by 0.

Other examples:
(1)(1) = 1 mod 5
(2)(3) = 1 mod 5
(4)(4) = 1 mod 5

(1)(1) = 1 mod 6
(5)(5) = 1 mod 6
2, 3, and 4 have no multiplicative inverse mod 6.

(1)(1) = 1 mod 7
(2)(4) = 1 mod 7
(3)(5) = 1 mod 7
(6)(6) = 1 mod 7

(1)(1) = 1 mod 8
(3)(3) = 1 mod 8
(5)(5) = 1 mod 8
(7)(7) = 1 mod 8
2, 4, and 6 have no multiplicative inverse mod 8.

(1)(1) = 1 mod 9
(2)(5) = 1 mod 9
(4)(7) = 1 mod 9
(8)(8) = 1 mod 9
3 and 6 have no multiplicative inverse mod 9.
• Sep 24th 2012, 11:37 AM
nitin1
Re: modular inverse arithmetic
sir, but there are many numbers which will give 1 after multiplying with it . then ? what is the answer ?
• Sep 24th 2012, 11:47 AM
johnsomeone
Re: modular inverse arithmetic
In modular arithmetic, all those numbers are equal.
(3)(5) = 1 mod 7, so the mod 7 inverse of 3 is 5.
But also (3)(-2) = -6 = 1 mod 7. And (3)(26) = 78 = 77 + 1 = 1 mod 7, and so forth.
Your concern, if I understand it, is that the "mod 7 inverse of 3" isn't a single unique value. It includes 5, and -2, and 26, and many many more.
But ALL those numbers it includes, 5, -2, 26, and the others, will all be "EQUAL mod 7". So, WITHIN the numbers mod 7, there is only ONE inverse of 3.
• Sep 24th 2012, 11:56 AM
nitin1
Re: modular inverse arithmetic
how to tell you that i still didn't get that how there is only one inverse of 3 ? i am feeling bad while asking this thing again :( secondly, if they are equal, then how to decide what is the answer ? please clearify it. (Worried)
• Sep 24th 2012, 12:58 PM
johnsomeone
Re: modular inverse arithmetic
There are two ways to look at this.
The easiest way, but less insightful, is to simply DEFINE "a = b mod n" to mean "n divides (a - b)". Then there will be multiple inverses to 3 mod 7, but it will be true that any two of them are "equal mod 7", which here means "7 will divide the difference between any two of them".

(what follows might confuse the hell out of you, but here it goes - besides, it seems you're already confused)
The better way to view mod 7 is to say that it's not doing arithmetic on *numbers*, but rather on particular sets of numbers. The numbers we write are called representatives of that set. The fact that "representative from set A" + "representative from set B" = "representative from set C" works out to be consistent means that we often pretend where looking at numbers rather than sets.
On this view the "numbers mod 7" comprise just 7 DISJOINT sets, each of which is infinite:
Set0 = {..., -14, -7, 0, 7, 14, 21, ...} = integers having remainder 0 when divided by 7
Set1 = {..., -13, -6, 1, 8, 15, 22, ...} = integers having remainder 1 when divided by 7
Set2 = {..., -12, -5, 2, 9, 16, 23, ...} = integers having remainder 2 when divided by 7
Set3 = {..., -11, -4, 3, 10, 17, 24, ...} = integers having remainder 3 when divided by 7
Set4 = {..., -10, -3, 4, 11, 18, 25, ...} = integers having remainder 4 when divided by 7
Set5 = {..., -9, -2, 5, 12, 19, 26, ...} = integers having remainder 5 when divided by 7
Set6 = {..., -8, -1, 6, 13, 20, 27, ...} = integers having remainder 6 when divided by 7

A better, and common, way to name these sets is to pick an element from each set, and put square brackets around it. Note that the sets are disjoint, so doing this will always uniquely identify which set is being named. Under this convension, we have:
[0] = Set0, [1] = Set1, ... [6] = Set6.

But under this convension we also have that [0] = [7] = [-70] = [28] = ... etc.
What those equal signs mean is that the SAME SET is being named by [0], [7], [-70], etc..

Then arithmetic mod 7 is actually a pair of binary operations on the set of these 6 sets.
+ : {[0], [1], [2], [3], [4], [5], [6]} x {[0], [1], [2], [3], [4], [5], [6]} --> {[0], [1], [2], [3], [4], [5], [6]}
x : {[0], [1], [2], [3], [4], [5], [6]} x {[0], [1], [2], [3], [4], [5], [6]} --> {[0], [1], [2], [3], [4], [5], [6]}
where, for example +([2], [3]) = [5] (treating + as the name of a function!) and x([2], [3]) = [6] (treating x as the name of a function!).
(By the way, no one ever uses such function-notation for + and x. I'm just trying to make it clear that they are functions.)
But we then lapse into the ordinary notation of [2] + [3] = [5] and [2] x [3] = [6] (or just written as [2][3] = [6], like ordinary multiplication).

In this light, the statement 1 + 2 = 3 mod 7 is understood to mean [1] + [2] = [3] (or +([1], [2]) = [3])

Now, it just so happens that [a]+[b] = [(a+b)] and [a][b] = [ab]. (Note here that (a+b) and ab are addition and mulitplication in the integers.)
And that remains so no matter which "representatives" we choose for the sets [a] and [b].
(A "representative" of one of these sets is just an element in it. 1 is a representative of [1], but so is 8.)
If we'd chosen crazier sets, that wouldn't be the case. But these 7 sets were very nicely and carefully chosen, and so everything works out "naturally" with them. It works out so naturally, in fact, that we often ignore all these complications and "pretend" that everything in sight are just numbers, with a mod 7 written, and a rule that we can add any multiple of 7 to any integer in sight whenever we want.

Anyhow, the point is that, on this view, [3][5] = [1], so the multiplicative inverse of [3] is [5]. [5] is now just one element - it's unique - it's the single set of those 7 sets that has the property that x([3], [5]) = [1].
However, this single set has an infinite number of representatives, and so an infinite number of names. But they're all naming the same thing - they're all naming the same set. So there's really only one thing there; it's just being given different names.
Thus it's true that [3][5] = [1], [3][-2] = [1], [3][26] = [1], but
those "different" things, [5], [-2], [26], are just different NAMES for the SAME thing, the set {..., -9, -2, 5, 12, 19, 26, ...}.

As an aside, this approach is so common in math that it has its own common techniques, terminology, and issues (equivalence relations, equalence classes, representatives, partitions, well-defined).
• Sep 24th 2012, 04:15 PM
Deveno
Re: modular inverse arithmetic
here's the deal:

when we say: "3 mod 7", or "the residue class of 3 mod 7" (residue class is a fancy-schmancy way of saying "remainder upon division by 7"), or "the equivalence class of 3 in the integers modulo 7"

what we mean is NOT THREE. 3 is an integer, integers behave the way they always have, and nothing strange is going on there.

what we mean (and what is no doubt confusing to most people) is something that is "almost like the integers" (so close that we often use the same numerical symbols). we start off the same way:

0, and we proceed the same way we define regular natural numbers:
1 = 0+1 and then:
2 = 1+1
3 = 1+1+1
4 = 1+1+1+1
5 = 1+1+1+1+1
6 = 1+1+1+1+1+1

and now...we do something...different:

7 = 1+1+1+1+1+1+1 = 0. hmmm.

well, what could we possibly MEAN by such a thing?

one way, is to imagine the integers placed in a circle (like the numbers on a clock (so "hours" are kind of like integers mod 12), but we only have 7 numerals instead of 12).

so 9, let's say, winds up "in the same place on the circle (or CYCLE, as mathematicians like to call it)" as 2, since 9 = 7 (full circle) + 2.

so what does multiplication mean in this "new system"?

well here is what we do:

first we multiply a and b "like normal", and then we figure out "where in the circle (cycle)" that would turn out to BE. here is a complete list:

0*0 = 0 (well THAT was easy).
0*1 = 0
0*2 = 0
0*3 = 0
0*4 = 0
0*5 = 0
0*6 = 0

1*1 = 1 (so far, so good...no "big numbers" (something more than 6) yet).
1*2 = 2
1*3 = 3
1*4 = 4
1*5 = 5
1*6 = 6

2*2 = 4 (still going strong, nothing "unusual" yet)
2*3 = 6
2*4 = 8 = ...(ok, this we have to do something about. 8 > 6, so what do we do? we "turn back a full turn", since 1+7 = 8, we have 1 = 8 (mod 7) so 2*4 = 1)...1
2*5 = 3 (same logic here: 2*5 = 10, and we "knock 10 back by 7's" until we get something between 0 and 6).
2*6 = 5

3*3 = 2 (hopefully i can just write these out, now, and not explain every single one)
3*4 = 5 (note that this is just 3*(3+1) = 3*3 + 3...the distributive law still works! amazing! so i can continue the "3's" by just adding 3 each time if i want to)
3*5 = 1 (because...8 is...remember? also 15 = 8, since 15 - 8 is..yep, 7)
3*6 = 4

4*4 = 2
4*5 = 6
4*6 = 3

5*5 = 4
5*6 = 2

6*6 = 1

( i only listed a*b, since b*a is always the same. try it! you'll see!).

now, we can ask ourselves if there is always SOME b with a*b = 1 (mod 7). well, almost. if a = 0, we're only going to get more 0's, so a = 0 doesn't work. but, for everything else...YES! why is this?

well imagine "skipping the circle of 7" by 1's. it's pretty clear you'll go through all the numbers. how about "skipping by 2's"? well, if we were to "land on 7 (back to 0)" after skipping k times

(which is what a*k = 0 would MEAN)

it would mean ak is a multiple of 7. but guess what? 7 is a prime number. now 7 doesn't go into 1,2,3,4,5, OR 6, which means that if 7 goes into ak evenly, it has to go into k.

so "skipping by 2's" we wind up on 7 only after 7 "jumps" (of 2). so let's see what numbers we land on after our "jumps":

0-->2-->4-->6-->1-->3-->5-->0 (= 7)

we land on 1 after the 4th jump: 2*4 = 1.

perhaps that's "too easy". let's try something more ambitious: "skipping by 5's"

0-->5-->3-->1-->6-->4-->2-->0

here, we landed on 1 after jump #3.

in fact, since every 7th jump we land back at 0 (no matter what our "jump size"), and since every jump takes us "to a different number than we're on" (since our jump size is 6 at most), we cycle through all 7 numbers before landing back at 0 (but in a different ORDER). and that means one of our "stops" is "landing on 1".