Proof of a congruence relation

Question

Let n∈N, and let a,b∈Z. Suppose that a≡b (mod n). Prove that n|a if and only if n|b.

As can be proceed?

$n\mid a\iff a\equiv 0\pmod {! n}$. Since $a\equiv b$, we must have $a\equiv 0\iff b\equiv 0$. — user26486, May 13 '15 at 17:25

score 2 · Answer 1 · answered May 13 '15 at 17:06

2

hint: You have: $a-b = kn, a = mn \to b = (b-a)+a = -kn+mn = (m-k)n$

answered May 13 '15 at 17:06

DeepSea

Kevin Zakka · Accepted Answer · 2015-05-13T17:34:31.927

Since it's a biconditional statement, you must prove the statement in both directions.

$a - b = nk$ for some integer k (by hypothesis)

$a = qn$ for some integer q (by definition of divisibility)

$b = a - kn = nq - nk = n(q-k)$

Thus n divides b.

$a - b = nk$ for some integer k (by hypothesis)

$b = np$ for some integer p (by definition of divisibility)

$a = nk + b = nk + np = n(k+p)$

Thus n divides a.

This ends the proof.

2 Answers2