Re: valid proof? of "x = y modulo m => x, y same remainders divided by m"

In article <1163448534.423080.293330@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
G Patel <gaya.patel@xxxxxxxxx> wrote:
I've seen a proof of "x = y modulo m if and only if x and y have same
remianders when divided by m" that was rather akward (I've added it at
end of this post for reference).

I was dissatisfied because this theorem is intuitively "obvious" and
this intuition was based on something that I think leads to a different
proof (the intuition doesn't related too directly with the proof I
saw). Please tell me if my proof has any holes.

---
Proving => implication:

By division algorithm, x = qm + r , 0 <= r < m

By definition of congruence, y = x + km, for some k in integers

therefore y = qm + r + km, 0 <= r < m
y = (q+k)m + r, 0 <= r < m

By division algorithm, r must be remainder when y is divded by m.


Proving <= implication:

By division algorithm,

x = sm + r, 0 <= r < m
y = tm + r, 0 <= r < m (same remainders)

solving for r in first and subbing into second:

y = tm + x - sm
y = x + (t-s)m which implies x = y (mod m)

=============================================

any holes?

As a minor nitpick, congruence is usually defined as "x = y (mod m) if
and only if m|x-y". The fact that this is equivalent to "y = x + km
for some integer k" is a (very, extremely) minor lemma.

Otherwise, no.

This is the book's proof:
----------

By div. alg,

x = km + r, 0 <= r < m
y = lm + s, 0 <= s < m

subtract second from first:

(x-y) = (k-l)m + (r-s), where -m < r-s < m

[proving <= implication]
So if x, y have same remainders (r-s) = 0 and
x - y = (k-l)m => x = y + (k-l)m, which implies x=y (mod m)

[proving => implication]
if x = y (mod m), then m|(x-y)

hence m| [ (x-y) - (k-l)m ] = m|(r-s)

But -m < r-s < m , so r-s has to be 0 => r=s, as required.

This is basically the same as your proof, only doing the division
first. What is your objection to this?

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages