Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By HallsofIvy

Math Help - Modular Arithmetic

  1. #1
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Modular Arithmetic

    Modular Arithmetic in Z:

    Definition: a(modm) stands for the remainder when a is divided by m.
    Definition: a(modm) + b(modm) is (a+b)(modm).
    Definition: a(modm)xb(modm) is axb(modm).
    Definition: a≡b(modm): a and b leave same remainder when divided by m

    Theorem: If a≡b(modm) and c≡d(modm) then a+b≡c+d(modm)

    Example: 3mod4 + 2mod4 ≡ 5mod4 ≡ 1mod4
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Modular Arithmetic

    By popular demand, I’ll prove the theorem (and correct a typo).

    a≡b(modm) → a=q1m+r, b=q2m+r → (a-b)=qm
    c≡d(modm) → (c-d)=q’m
    (a+c)-(b+d)=q’’m
    (a+c)≡(b+d)(modm)*

    * So I don’t leave with a guilty conscience,
    a-b=qm, a=q1m+r1, b=q2m+r2 → r1=r2→ a≡b(modm).


    Notes
    The point of the theorem was to show it is not a definiton of addition.

    Now that you understand congruences and modular arithmetic (definitions and operations), don’t look back at any problems- remember Lot's wife.

    EDIT: For a rainy day, if m is prime there is a cancellation law. Didn't want to clutter up the structure.
    Last edited by Hartlw; May 22nd 2013 at 11:22 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Modular Arithmetic

    The OP says (intentionally) that a(modm) STANDS for the remainder. Then a(modm)+b(modm) becomes the addition of symbols, which is a little unsettling.

    If a(modm) IS the remainder, ie 0,1,2, m-1, then you can keep the arithmetic of remainders in Z if you define +’ as:
    a(modm)+’(bmodm) = [a(modm)+(bmodm)](modm)
    Similarly for multiplication.

    Then, Theorem:
    a(modm)+’b(modm) = (a+b)(modm)
    Proof: a(modm)=r1 and b(modm)=r2, then (a+b)modm=(r1+r2)(modm).

    In effect, you have replaced a relation (≡) among symbols with a different definition of + (+') among integers, in the manner of + for complex integers.

    (This is the Math (free discussion) forum, right?)

    Still getting the initial MHF screen which says “Install Flash Player HD required,” but now with “required” in italian (to thwart anti-virus software I assume). Be nice to have a separate forum for this type of thing.
    Last edited by Hartlw; May 24th 2013 at 09:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,974
    Thanks
    1121

    Re: Modular Arithmetic

    Quote Originally Posted by Hartlw View Post
    Modular Arithmetic in Z:

    Definition: a(modm) stands for the remainder when a is divided by m.
    Definition: a(modm) + b(modm) is (a+b)(modm).
    I'm not sure why you would call that a "definition". if a (mod m)= x and b (mod m)= y then a= x+ mp for some integer p and b= y+ mq for some integer q. Then a+ b= x+ mp+ y+ mq= (a+ b)+ m(p+ q).

    Definition: a(modm)xb(modm) is axb(modm).
    Definition: a≡b(modm): a and b leave same remainder when divided by m

    Theorem: If a≡b(modm) and c≡d(modm) then a+b≡c+d(modm)

    Example: 3mod4 + 2mod4 ≡ 5mod4 ≡ 1mod4
    What is your question? Are you trying to prove the theorem? The way you have stated it, it is NOT true. For example, 1= 5 (mod 4) and 2= 6 (mod 4) but 1+ 5 is NOT equal to 2+ 6 (mod 4). The first is equal to 2 (mod 4) and the second is equal to 0 (mod 4).
    But that is probably typo. What is true if "If a≡b(modm) and c≡d(modm) then a+c≡b+d(modm)"
    If a≡ b (mod m) then a= b+ pm for some integer p and if c≡ d (mod m) then c= d+ qm for some integer q. Then a+ c= (b+ pm)+ (d+ qm)= b+ d+ (p+ q)m which says that a+ c≡ b+ d (mod m)
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Re: Modular Arithmetic

    You are correct, there is a typo in the theorem in post 1, noted in first line of post 2 (noticed it too late), where the corrected theorem was stated and proved.

    If 3mod4=3, and 2mod4=2, then 3mod4+2mod4 = 5, which is why you need a definition: (≡ instead of =): 2mod4 + 3mod4 ≡ 5mod4.

    I started this thread to clarify a situation, nameley, that nowhere could I find a definition of addition in modular arithmetic other than descriptive. What I was looking for was something that said the elements X form a ring with addition and multiplication defined by ---. Something like the definition of addition of two matrices: A+B=C where cij=aij+bij.

    In my search it appeared that additon in modular arithmetic was simply assumed to be a description (construction), without spelling out exactly what was being added, and how you write down the addition, a+b=c. I answered this in my first post.

    In retrospect, post 3 was a little pedantic and unnecessary. Stick with OP, which is clear, concise, and easily remembered, but has a typo (noted in post 2) in the Theorem. It should be, as stated in post 2,:
    Theorem: If a≡b(modm) and c≡d(modm) then a+c≡b+d(modm), RIGHT
    Instead of
    Theorem: If a≡b(modm) and c≡d(modm) then a+b≡c+d(modm), WRONG

    Wish I had caught the edit.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2010
    Posts
    887
    Thanks
    91

    Congruence Rings in Modular Arithmetic

    Revised Thinking

    Definition: a≡b modm if m|(b-a), or, if b and a leave same remainder when divided by m. a,b,m integers.

    c is called the modular sum of a & b if (a+b)≡c modm.
    c is called the product of a & b if ab≡c modm.

    For a fixed m=n, and ≡ replacing =:
    The above defines a ring Zn for the integers 0,1,2,..n-1,
    Or a ring of residue classes if the integers are divided into classes with same remainder 0,1,2,..n-1.

    Ring: Addition, multiplication, associativity, commutativity, 0, 1, and distributivity.
    Domain: Ring plus cancellation law (m prime).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 12th 2010, 08:53 PM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: June 29th 2010, 07:51 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  4. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 08:44 AM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum