Math Is Fun Forum

Identity

Member

Registered: 2007-04-18

Posts: 934

Questions on congruences

How many normal integer operations work in modular arithmetic... i.e.:
If a

b (mod m)

, then does a - b

0 (mod m) ?
In general, does a

b

b

b (mod m)
And does an

bn (mod m), for some integer n?

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Questions on congruences

a = b (mod n) means that n divides (a - b).  Try them out for yourself, can you prove those statements?  Can you disprove them with examples?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

HallsofIvy

Guest

Re: Questions on congruences

We can also define "mod m" by x= y mod n if and only if dividing both x and y by m gives the same remainder.  Of course, that is exactly the same as saying (x-y)/m has remainder 0 since that is equal to x/m- y/m and the remainders cancel.

  Either one of those immediately gives the result that "If x= y mod m, then x-y= 0 mod m"
Using the "x-  y is divisible by m" definition, (x-y)- 0 is divisible by m if and only if x-y is.
Using the "remainder" definition, x-y has the same remainder a 0 when divided by m (0 of course) if and only if x and y have the same remainder.

  Obviously, then a= b mod m is the same as a-b= b-b= 0 mod m.  a+ b= b+ b= 2b mod , because
("x-y divisible by m" definition) a+b- 2b= a- b.
("same remainder" definition) If the remainder of both a and b divided by m is r, then the  remainder of a+ b divided by m: (a+b)/m= a/m+ b/m is 2r and the remainder of 2b divided by m is 2r.

  I'm not sure what you mean by "na= nb mod m for some number n"

  If you are still assuming a= b mod m, then that is true for ANY integer n: a-b is divisible by m so na- nb= n(a-b) has remainder 0 when divide by m.
  If a is not equal to b mod m,  then na= nb mod m only if n is a multiple of m: that is if n= 0 mod m.  In that case, na = nb mod m is the same as 0a= 0b= 0 mod m.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Questions on congruences

We can also define "mod m" by x= y mod n if and only if dividing both x and y by m gives the same remainder.  Of course, that is exactly the same as saying (x-y)/m has remainder 0 since that is equal to x/m- y/m and the remainders cancel.

You can, but you shouldn't.  Number theory is the study of the integers.  Division doesn't exist in the integers because numbers such as 2/3 are not integers.  So when trying to study integers, you should never use an operation which can take you out of the integers.

But multiplication is closed with respect to the integers.  a*b is always an integer when a and b are.  So we like to think of every thing in terms of multiplication.  So a divides b does not mean b/a = k where k is some integer.  Rather, it means there exists a k where b = ka.  You may say that those are the same thing.  But here, it is important not what you think, but how you think of it.  Phrasing things in terms of multiplication avoids many common pitfalls that would occur through the use of division.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: Questions on congruences

(mod m)

Proof
⇒ m | a ± b - (b ± b)
⇒ m | a - b

If

(mod m), then

(mod m)

Proof

⇒ m | an - bn
⇒ m | n(a - b)
⇒ m | (a - b)

Does that work?