Let a, b, c, and d be integers, and let n be a positive integer. Prove that if a is congruent to c mod n and b is congruent to d mod n, then (a-b) is congruent to (c-d) mod n
Given:
a≡c mod n
b≡d mod n
Prove that (a-c)≡(b-d) mod n.
Let
a=kn+r ... k,r ∈ ℤ+
c=ln+r ... l,r ∈ ℤ+
Subtract:
(a-c)=(k-l)n
Similarly,
(b-d)=(p-q)n ... p,q ∈ ℤ+
Therefore
(a-c)≡(b-d) mod n
To prove that (a - b) is congruent to (c - d) mod n, we need to show that their difference is divisible by n.
By definition, if a is congruent to c mod n, then n divides (a - c). Similarly, if b is congruent to d mod n, then n divides (b - d).
We can write this as:
(a - c) = kn ------> (1)
(b - d) = mn ------> (2)
where k and m are integers.
Now, let's compute the difference (a - b):
(a - b) = (a - c) + (c - d)
Substituting Equation (1) and (2):
(a - b) = kn + c - d
Rearranging the terms:
(a - b) = (kn + c) - d
Since n divides (kn + c) (as n divides (a - c)) and n divides d (as n divides (b - d)), we can rewrite the above equation as:
(a - b) = xn
where x = kn + c - d.
This shows that (a - b) is divisible by n, which means (a - b) is congruent to (c - d) mod n.
Hence, we have proved that if a is congruent to c mod n and b is congruent to d mod n, then (a - b) is congruent to (c - d) mod n.