Results 1 to 15 of 15

Math Help - Modulo question

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    Angry Modulo question

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by sjenkins View Post
    Show that 937 is an inverse of 13 modulo 2436
    Show that (937)(13) - 1 is divisible by 2436.


    Find an inverse of 2 modulo 17
    Find an integer x so that 2x - 1 is divisible by 17.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hi =)

    Quote Originally Posted by sjenkins View Post
    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!
    Continuing TPH's explanation, the inverse x of 13 modulo 2436 is such that :

    13x \equiv 1 (2436), 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

    2436=\textbf{13}*187+\textbf{5} \quad \implies \quad 5=a-187b

    13=2*\textbf{5}+\textbf{3} \quad \implies \quad 3=13-5*2=b-2(a-187b)=-2a+375b

    5=\textbf{3}+\textbf{2} \quad \implies \quad 2=5-3=(a-187b)-(-2a+375b)=3a-562b

    3=2+1 \quad \implies \quad 1=3-2=(-2a+375b)-(3a-562b)=-5a+937b


    1=-5*2436+937*13 \quad \implies \quad 937*13=1+5*2436=1 \mod 2436

    Yay !

    [tex]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11

    proving that addition modulo n is associative

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    There is not much to show honestly, it is just because regular addition is associative.
    (a+b)+c=a+b+c=a+(b+c) \Rightarrow (a+b)+c =a+(b+c) (mod n)

    It basically just comes down to the fact that reduction of integers modulo n is well-defined, that is if a=b then a (mod n) = b (mod n)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11
    Gamma thank-you very much for taking the time to answer my question. As ever the proof comes down to something I have not yet covered.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    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 \phi:\mathbb{Z} \Rightarrow \mathbb{Z}_n,\phi(x)=x (mod n).

    Now what you need to show is that it doesn't make a difference if you add two integers before you apply \phi or after you apply \phi to them separately. In symbols I mean:

    \phi(x)+\phi(y)=\phi(x+y)
    Simply apply the division algorithm to x and y to see that

    \phi(x)+\phi(y)=\phi(r+nk)+\phi(s+nl)=r+s (mod n)
    \phi(x+y)=\phi\left((r+nk)+(s+nl)\right)=\phi\left  ((r+s) + n(k+l)\right)=r+s (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 \mathbb{Z} and since this reduction mod n preserves addition, the associativity is inherited from \mathbb{Z}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11
    Quote Originally Posted by Gamma View Post
    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 \phi:\mathbb{Z} \Rightarrow \mathbb{Z}_n,\phi(x)=x (mod n).

    Now what you need to show is that it doesn't make a difference if you add two integers before you apply \phi or after you apply \phi to them separately. In symbols I mean:

    \phi(x)+\phi(y)=\phi(x+y)
    Simply apply the division algorithm to x and y to see that

    \phi(x)+\phi(y)=\phi(r+nk)+\phi(s+nl)=r+s (mod n)
    \phi(x+y)=\phi\left((r+nk)+(s+nl)\right)=\phi\left  ((r+s) + n(k+l)\right)=r+s (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 \mathbb{Z} and since this reduction mod n preserves addition, the associativity is inherited from \mathbb{Z}
    Hi Gamma

    Many thanks for your continued interest, I very much appreciate it.

    I understand your proof that x(mod n) + y(mod n) = (x + y)(mod n), the equivalent for addition I am assuming is (x+0) + (y+0) = (x + y)+0 ?

    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 x(mod n) = r +nk 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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    Good old fashioned algebra

    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 [a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\}. So what we really need to do is check that the following sets are the same.

    ([a]+[b])+[c]=[a]+([b]+[c])

    [(a+nk) + (b + nl)]+(c+nj)=[(a+b)+n(k+l)]+(c+nj)= (a+b+c)+n(k+l+j)=a+nk+[(b+c)+n(l+j)]=a+nk+[(b+nl) + (c+nj)]=

    The above quantity shows fwhen read from left to right that ([a]+[b])+[c]\subset [a]+([b]+[c])
    And from right to left we get ([a]+[b])+[c]\supset [a]+([b]+[c])
    so
    ([a]+[b])+[c]=[a]+([b]+[c])


    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11

    thanks

    Thanks again Gamma

    I do not have the time to go through this now but I will soon. It is all starting to clear in my head a little.

    I will post again soon in reply.

    cheers
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11

    equivalence class containing a Vs class just containg a

    Hi there Gamma

    May I thank-you once again for your help, I appreciate it very much.

    I see your point that using [a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\} to denote the congruence class containing a, 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 a, b and c 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 a=r+nf say, to get
    (a+b)+c (mod n)= (r+nf + s + ng)+(t+nh) (mod n)=??= a+(b+c) (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
    [a]=\{x\in \mathbb{Z}|n|(x-a),x-a=a\}= a?

    Any help as ever will be welcomed.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by leinad View Post
    Hi there Gamma

    For example can I modify your proof somehow by using your previous definition of an interger using the division algorithm a=r+nf say, to get
    (a+b)+c (mod n)= (r+nf + s + ng)+(t+nh) (mod n)=??= a+(b+c) (mod n).
    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 n|(a-a) \Leftrightarrow a \equiv a (mod n).

    (a+b)+c (mod n)= (r+nf + s + ng)+(t+nh) (mod n)= r+nf + s + ng+t+nh (mod n)= r+nf + (s + ng+t+nh) (mod n)= a+(b+c) (mod n)
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11
    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
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jul 2009
    From
    Oxford
    Posts
    11

    problems with notation for modulo n

    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
    (a + b) + c (mod n) = a + (b + c) (mod n).

    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 \phi(x)=x(mod n) then in words this means obviously to divide x by n and take the remainder. The expression \phi(x+y) then means to add x and y and to then divide by n and take the remainder. So my question is can I write
    (a + b) + c (mod n) = a + (b + c) (mod n)
    as
    \phi( \phi(a+b) + c)=\phi( a + \phi(b+c))
    or should it be
    \phi((a+b) +c)=\phi(a + (b+c))
    ??
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by sjenkins View Post
    ...
    I am ... confused with the concept of modulo.
    Can someone please explain exactly what it is?
    ...
    simply put modulo is the REMAINDER after division.

    Do the long division on this:

     \dfrac{2536}{2436}

    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:

     5 \times \dfrac{1}{5} = 1

     13 \times \dfrac{1}{13} = 1

    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)

     \dfrac{13 \times B}{2436} \equiv SomeQuotient w/remainder of 1

    you want a remainder of 1 AFTER the division

    13 x 937 = 2436 x 5 + 1

     \dfrac{13 \times 937}{2436} = 5 w/REMAINDER OF 1

    In this case 937 is the equivalent of 1/13.

    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 3rd 2011, 01:11 PM
  2. modulo question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 3rd 2011, 01:04 PM
  3. modulo question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 2nd 2010, 03:54 AM
  4. Modulo Question: Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 20th 2010, 07:14 PM
  5. question on inverse modulo m
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2009, 02:38 PM

Search Tags


/mathhelpforum @mathhelpforum