I am working with the least helpful textbook in the world and am confused with the concept of modulo. Can someone please explain exactly what it is? I have never heard this word before this particular class. How can I find inverse of modulo? Such as...
Show that 937 is an inverse of 13 modulo 2436
and
Find an inverse of 2 modulo 17
Please, I can't go on in this course until I get a firm grasp of modulo!
Hi =)
Continuing TPH's explanation, the inverse x of 13 modulo 2436 is such that :
, that's equivalent to what TPH said.
If you weren't given 937, first check that 13 is coprime with 2436.
Then, use the Euclidian algorithm. You'll get 1 at a moment because it's the gcd.
Let 2436=a and 13=b. We'll find u (and v) such that av+bu=1 <=> bu=1+a(-v) <=> 13u=1 mod a
that is to say u is the inverse of 13
Yay !
[tex]
Hello math helpers, I hope that I do not get accused of hijacking this thread but I think my question is relevant.
I am just starting to learn some elementary group theory and I am puzzled as to how one goes about proving that addition modulo n is associative. Strangely I have found a proof that shows the addition of congruence classes modulo n is associative and I understand that but I cannot seem to apply it to addition modulo n for integers.
Any help would be most appreciated.
I was thinking a little more about this question you have asked, and I was thinking it is probably more useful for you to prove essentially that this modulo reduction operation is a homomorphism under addition.
You probably have not gotten to this yet in your book, but the concept of a homomorphism will be important, so you might as well start to think about it now.
Consider the function (mod n).
Now what you need to show is that it doesn't make a difference if you add two integers before you apply or after you apply to them separately. In symbols I mean:
Simply apply the division algorithm to x and y to see that
(mod n)
(mod n)
So now if you think about your question, associativity of addition under modular addition follows from the fact that addition is associative in and since this reduction mod n preserves addition, the associativity is inherited from
Hi Gamma
Many thanks for your continued interest, I very much appreciate it.
I understand your proof that (mod n) (mod n) (mod n), the equivalent for addition I am assuming is ?
If this is the case than I can see that addition modulo n mimics addition in this way. It is then tempting to say that addition modulo n inherits other properties of addition like associativity. However I cannot see how the associativity can be directly proved using the (mod n) = expressions that you have used or the above result. Is there much more to this inheritence than you have outlined or can we not directly prove the associativity of addition modulo n (i.e using good old fashioned algebra)?
many thanks
See the thing we need to remember that when dealing with modular arithmetic is that they are equivalence classes.
a~b (mod n) iff n|(a-b).
So you usually denote the equivalence class containing a as . So what we really need to do is check that the following sets are the same.
The above quantity shows fwhen read from left to right that
And from right to left we get
so
I think this is the proof you are looking for, but you notice the proof still comes down to the fact that addition in the integers is associative, this is because we have simply imposed an equivalence relation on the integers.
Hi there Gamma
May I thank-you once again for your help, I appreciate it very much.
I see your point that using to denote the congruence class containing , you have shown, using the associativity property of addition, that addition of congruence classes is also associative. Forgive my ignorance but do we not need to show this for the sets containg just , and or is this somehow automatically proved?
For example can I modify your proof somehow by using your previous definition of an interger using the division algorithm say, to get
(mod n)= (mod n)=??= (mod n).
Or do we just now somehow limit the set notation for the congruence class containing a to be the set just containing a, for example something like
?
Any help as ever will be welcomed.
This comes back to my point of modular arithmetic being well defined. If you have the same number in the integers and reduce it mod n, it is still equal. It is an equivalence relation and in particular it is reflexive.
If a=a for an integer a. then certainly (mod n).
(mod n)= (mod n)= (mod n)= (mod n)= (mod n)
Hi Gamma
Thanks again for your efforts. It seems I am having an all too familiar evaporation of understanding! I think this whole modular arithmetic thing is too unfamiliar right now. I am going to take a little time and mull over the things you have shown me and I will get back to you soon.
cheers
Hi there math helpers.
As you can see I have been trying to follow this thread for a while now and am still struggling despite huge amounts of help from Gamma. I am reasonably familiar now I think with the concept of modulo n, addition modulo n, congruence classes etc.
I am trying to show that addition modulo n is associative, the usual way to write this is
.
Now I think this notation is confusing. For example if I use some notation that Gamma used in one of his previous replies, that is then in words this means obviously to divide x by n and take the remainder. The expression then means to add x and y and to then divide by n and take the remainder. So my question is can I write
as
or should it be
??
If the last expression is correct then I can see that the proof of associativity is easy, if the first expression is the correct one then I am still struggling with this proof!
Any help would be greatly appreciated.
simply put modulo is the REMAINDER after division.
Do the long division on this:
Quotient equals 1 w/Remainder of 100
2536 mod 2436 = 100 (mod is short for modulo)
now long divide the following but discard the quotients, keeping the remainder
2536 modulo 2436 = 100
12181 modulo 2436 = 1 (12181/2436 = 5 w/remainder of 1)
12182 modulo 2436 = 2 (12182/2436 = 5 w/remainder of 2)
85274 modulo 2436 = 14 )85274/2436 = 35 w/remainder of 14)
Inverses (without too much overkill)
What is the inverse of 5
You should say 1/5
What is the inverse of 13?
How about 1/13.
So:
A number times its inverse equals 1.
Show that 937 is an inverse of 13 modulo 2436.
What you are searching for is some number (say B) such that
13 x B is equivalent to 13 x 1/13 = 1 [modulo the modulus]
or
13 x B = 1 + 2436 x (SomeQuotient)
SomeQuotient w/remainder of 1
you want a remainder of 1 AFTER the division
13 x 937 = 2436 x 5 + 1
= 5 w/REMAINDER OF 1
In this case 937 is the equivalent of 1/13.
.