v (mod d) and w x (mod d), then u·w v·x (mod d). To prove that an if--then statement (p
q) is true, we assume that p is true and show that q is also
true.5b) The statement we are required to prove is: If u v (mod d) and w x (mod d), then u·w v·x (mod d).
To prove that an if--then statement (p q) is true, we assume that p is true and show that q is also
true.
Recall that to say that a b (mod d) is equivalent to saying:
1. a mod d = r and b mod d = r,
2. a - b = kd for some integer k, or
3. d | (a - b).
Use the second point from the list above to rewrite u v (mod d) and w x (mod d), as equations.
Proof Suppose that u, v, w, x and d are integers
such that u v (mod d)
and w x (mod d).
By the definition of congruence this is equivalent to saying that u - v = sd and w - x = td, for some integers s and t.
We can rearrange these equations to see that: u = v + sd and w = x + td.
Multiplying the above two equations we see that: uw |
= |
(v + sd) (x + td) |
= |
vx + vtd + sdx + std2 | |
= |
vx + (vt + sx + std)d |
Since v, x, s and t are all integers, we know that vt + sx + std
is also an integer. Hence, u·w - v·x = md, for some integer m.
By point 2 in the definition of congruence, this is equivalent to saying that
u·w v·x (mod d).