A proof for modular arithmetic theorem

[r0bHadz]

Homework Statement

Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only
if a mod m = b mod m.

Homework Equations

The Attempt at a Solution

By definition a ≡ b (mod m) => m| (a-b)

mx = a -b => mx + b = a => b = a mod m

b = a - mx => b = m(-x) + a => a = b mod m

a = (a mod m) mod m = a mod m => a=b => a mod m = b mod m

does this seem right?

 

[PeroK]

Homework Statement

Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only
if a mod m = b mod m.

Homework Equations

The Attempt at a Solution

By definition a ≡ b (mod m) => m| (a-b)

mx = a -b => mx + b = a => b = a mod m

b = a - mx => b = m(-x) + a => a = b mod m

a = (a mod m) mod m = a mod m => a=b => a mod m = b mod m

does this seem right?

I'm sorry to say this is not a valid proof. First, note the difference between ##\equiv## and ##=## in this context. Note also that ##a \ mod \ m## is a non-negative integer in the range ##0## to ##m-1##.

In your proof, you have:

b = a mod m

But, ##b## could be any integer and we could have ##b > m##, hence equality with ##a \ mod \ m## is impossible. Also, ##b## could be negative etc.

Also, a proof of an "if and only if" needs to be structured something like:

Let ##a \equiv b \ mod \ m \ \dots##.

Finally, you must be precise. You introduced ##x## without saying what ##x## was. Is it a real number, an integer, a positive integer?

In general, pure mathematics isn't about putting a few calculations together, it's about a precise, logical flow. This is something you need to try to develop.

 

[PeroK]

Homework Statement

Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only
if a mod m = b mod m.

I suggest you do the following implication first. Show that:

if a mod m = b mod m then a ≡ b (mod m)

Post that and then once you have done this, you can try the converse.

 

[r0bHadz]

Pero what you wrote made a lot of sense, I've started the proof over again and this is what I got.

Let a ≡ b(mod m ) => m| (a-b) => a-b = mx for x ∈ ℤ

=> a = mx + b

*** if m|a and m|b => a = mp and b = mo for p,o∈ℤ then m| a-b so from m|(a-b) we know m|b

so b = mo + r
a = mx + b can be written as a = mx + (mo + r) => a = m(x+o) + r so

r = a mod m

Now I need to show that r = b mod m correct? Also is my proof starting to look at least a little better

 

[PeroK]

Pero what you wrote made a lot of sense, I've started the proof over again and this is what I got.

Let a ≡ b(mod m ) => m| (a-b) => a-b = mx for x ∈ ℤ

=> a = mx + b

*** if m|a and m|b => a = mp and b = mo for p,o∈ℤ then m| a-b so from m|(a-b) we know m|b

so b = mo + r
a = mx + b can be written as a = mx + (mo + r) => a = m(x+o) + r so

r = a mod m

Now I need to show that r = b mod m correct? Also is my proof starting to look at least a little better

Yes, this is looking better. You don't need to do the case where ##a, b \equiv 0 \ mod \ m## separately. But, you do need to specify that ##0 \le r < m##. And that, by definition, means that ##r = b \ mod \ m##.

If you tidy that up, you have the first implication. The converse should be simpler.

Note that this proof is a little bit more difficult than expected.

 

[r0bHadz]

a≡b(mod m) => m | a-b => mx = a-b for x ∈ℤ

b = my + r and 0≤r<m by definition, so b mod m = r by definition

mx = a- (my + r) => mx + my + r = a => m(x+y) + r = a so by definition a mod m = r as wellConverse:

a mod m = b mod m => a = mx + r and b = my + r 0≤r<m

=> a-b = mx + r - my - r => a-b = m(x-y)

=> m | a-b which is equivalent to a ≡ b(mod m)

 

[r0bHadz]

This proof was difficult but I think I'm done proving it now. I'm reading Rosens discrete math book rn. Do you recommend giving a proof for every theorem even if I'm not asked to do so?

 

[PeroK]

This proof was difficult but I think I'm done proving it now. I'm reading Rosens discrete math book rn. Do you recommend giving a proof for every theorem even if I'm not asked to do so?

Yes, the proof looks correct.

I don't know Rosen's book, so I'm not sure. Generally, you should do at most what the book asks. Anything extra might be useful, but it also takes more time.