9. If a and b are positive integers and n is a positive integer, prove that a mod n = b mod n if and only if n divides a-b.

Proof:

Step 1:  Assume a mod n = b mod n and prove n divides a-b.

Since a mod n = b mod n, we can write a = q1 n + r and b = q2 n + r.

Then a-b = (q1-q2)n is divisible by n.

Step 2:  Assume n divides a-b and prove a mod n = b mod n.

We know we can write a = q1 n + r1 and b = q2 n + r2, with remainders r1 and r2 both between 0 and n.

Then a-b = (q1 - q2) n + (r1 - r2).

Because n goes evenly into (q1 - q2) n, the remainder when a-b is divided by n is the same as the remainder when r1 - r2 is divided by n.

Since a-b is divisible by n, the remainder when r1 - r2 is divided by n must be 0.  So r1 - r2 is a multiple of n.

But r1 and r2 are both numbers between 0 and n, so the only way r1 - r2 can be an even multiple of n is for it to equal 0 n = 0.

So r1 = r2 and a mod n = b mod n.

The proof is complete.

When writing your own proofs please state what you are trying to prove as you begin each major step of the proof and also state your assumptions or "givens".  At the end of the proof, state your conclusion.  If you're not sure you've given enough justification for your conclusions, set the problem aside and re-read it the next day.  If you find yourself wondering "so why was that true?" you should add more explanation.

50.  Let S be the set of integers.  If a and b are elements of S, define aRb if a + b is even.  Prove that R is an equivalence relation and determine the equivalence classes of S.

a)  Proof:

To prove R is an equivalence relation we must verify three properties:

1)  Reflexive:  a R a if a+a is even.  a+a = 2a is even.

2)  Symmetric:  If a R b is true, is it true that b R a?  If a+b is even, then b+a = a+b is even.  (You may mention the commutative law of addition here if you wish.)

3)  Transitive:  If a R b and b R c, is it true that a R c?

If a+b is even, then either both a and b are even or both are odd.

Case 1:  a and b are both even.

In this case, bRc means b+c is even, so b and c must both be even.

Then a and c are both even, so a + c is even.

Case 2:  a and b are both odd.

In this case, bRc tells us c is odd, and so a+c is the sum of two odd numbers and therefore even.

In both cases, a+c is even so aRc.

This completes the proof that R is an equivalence relation.

b)  In order for a+b to be even, all that is necessary is for both to be even or both to be odd.  So the equivalence class of any even number contains all even numbers and the equivalence class of any odd number contains all odd numbers.  Using 0 as a representative even number and 1 as a representative odd number, we find that the equivalence classes are:

[0] = all even integers, and

[1] = all odd integers.

Note that in the proof very little justification was necessary for a good grade.  However, if you found yourself puzzled by any of the conclusions in the proof you'd want to add more justification in your version.  The paragraph starting part (b) was not necessary for a good grade but does make the problem more readable.  Similarly, it's not necessary to explicitly split the problem into two parts.  However, you must complete part (a) before you can conclude that the sets listed in part (b) are actually equivalence classes.