As in Example, the congruence modulo 2 relation E is

Chapter 8, Problem 1E

(choose chapter or problem)

Problem 1E

As in Example, the congruence modulo 2 relation E is defined from Z to Z as follows: For all integers m and n,

m E n&m ⇔ n is even.

a. Is 0 E 0? Is 5 E 2? Is (6, 6) ∈ E? Is (–1,7) ∈ E?

b. Prove that for any even integer n, n E 0.

Example

The Congruence Modulo 2 Relation

Define a relation E from Z to Z as follows: For all (m, n) ∈ Z × Z,

m E n ⇔ m – n is even.

a. Is 4 E 0? Is 2 E 6? Is 3 E (–3)? Is 5 E 2?

b. List five integers that are related by E to 1.

c. Prove that if n is any odd integer, then n E 1.

Solution

a. Yes, 4 E 0 because 4– 0 = 4 and 4 is even.

Yes, 2 E 6 because 2 – 6 = –4 and –4 is even.

Yes, 3 E (–3) because 3 – (–3) = 6 and 6 is even.

No, 5 Ɇ2 because 5 –2 = 3 and 3 is not even.

b. There are many such lists. One is

1 because 1 – 1 = 0 is even,

3 because 3 – 1 = 2 is even,

5 because 5 – 1 = 4 is even,

–1 because –1 – 1 = –2 is even,

–3 because –3 – 1 = –4 is even.

c. Proof: Suppose n is any odd integer. Then n = 2k + 1 for some integer k. Now by definition of E,n E 1 if, and only if, n–1 is even. But by substitution,

n – 1 = (2k + 1) –1 = 2k,

and since k is an integer, 2k is even. Hence n E1 [as was to be shown].

It can be shown (see exercise at the end of this section) that integers m and n are related by E if, and only if, m mod 2 = n mod 2 (that is, both are even or both are odd). When this occurs m and n are said to be congruent modulo 2.

Exercise

Prove that for all integers m and n, m –n is even if, and only if, both m and n are even or both m and n are odd.