# Modular Arithmetic

• May 22nd 2013, 07:41 AM
Hartlw
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
• May 22nd 2013, 12:06 PM
Hartlw
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.
• May 24th 2013, 10:37 AM
Hartlw
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.
• May 24th 2013, 11:48 AM
HallsofIvy
Re: Modular Arithmetic
Quote:

Originally Posted by Hartlw
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).

Quote:

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)
• May 25th 2013, 08:00 AM
Hartlw
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
Theorem: If a≡b(modm) and c≡d(modm) then a+b≡c+d(modm), WRONG

Wish I had caught the edit.
• May 27th 2013, 09:21 AM
Hartlw
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).