Homework Help: Proof again: Show that a mod m = b mod m if a = b (mod m)

VinnyCee · Apr 5, 2007

1. The problem statement, all variables and given/known data

Let m be a positive integer. Show that a mod m = b mod m if [itex]a\,\equiv\,b\left(mod\,m\right)[/itex].

2. Relevant equations

Congruency - [tex]a\,\equiv\,b\left(mod\,m\right)[/tex]

a is congruent to b modulo m.

3. The attempt at a solution

I really, really, really suck at proofs. But here is what I tried.

[tex]a\,\equiv\,b\left(mod\,m\right)\,\longrightarrow\,a\,mod\,m\,\equiv\,\left[b\left(mod\,m\right)\right]\,\left(mod\,m\right)[/tex]

I have no idea how to prove anything about this stuff. Please help!!!

matt grime · Apr 5, 2007

Why are you trying to prove it using symbols?

Q. What does it mean in words for a to be congruent to b mod m?

Q. What is a mod m, and what is b mod m?

The definitions of these things mean there is *nothing* here that needs to be proved.

VinnyCee · Apr 5, 2007

a is congruent to b mod m if m divides (a - b).

a mod m is the remainder of the division operation of [itex]\frac{a}{m}[/itex].

b mod m is the remainder of the division operation of [itex]\frac{b}{m}[/itex].

VinnyCee · Apr 5, 2007

Does this count as "showing" a mod m [itex]\equiv[/itex] b mod m?

[tex]a\,\equiv\,b\left(mod\,m\right)\,\longrightarrow\,a\,mod\,m\,\equiv\,\left[b\left(mod\,m\right)\right]\,\left(mod\,m\right)[/tex]

By definition of mod m and congruence mod m,

[tex]b(mod\,m)(mod\,m)\,\equiv\,b[/tex]

So,

[tex]a(mod\,m)\,\equiv\,b[/tex]

Then,

[tex]a\,\equiv\,\left[a(mod\,m)\right](mod\,m)\,\equiv\,a[/tex]

Q.E.D.

matt grime · Apr 5, 2007

Put it *simple* words. Phrases that involve the words: remainder on division by m. a=b mod m if and only if a and b have the same remainder on division by m. That's what modulo arithmetic. So, as you see, there is nothing to prove. a mod m is the remainder on division by m.

So all it is asking is: show that if a and b have the same remainder on division by m, then the remainder of a on division by m is the same as the remainder of b on division by m. So there isn nothing to prove beyond writing out the definitions.

VinnyCee · Apr 5, 2007

a mod m is the remainder after a is divided by m.

a mod m and b mod m are equal if and only if their remainders are the same.

m divides (a - b) <---- What do I do with this?

Is that really it?

matt grime · Apr 5, 2007

VinnyCee said: ↑

m divides (a - b) <---- What do I do with this?

nothing

Is that really it?

yes.

Edgardo · Apr 5, 2007

Review the definitions.

What is the mathematical definition of [itex]a \equiv b \mbox{ (mod m)}[/itex]?