Let n ∈ N and a, b, c ∈ Z. Recall that c mod n is the remainder r ∈{0, 1, . . . , n − 1} on division of c by n. Provide a short proof that ifa mod n = b mod n, then a ≡ b mod n.2

The statement "a mod n = b mod n, then a ≡ b mod n" is essentially saying that if the remainder of a divided by n is equal to the remainder of b divided by n, then a is congruent to b modulo n.

Here is a short proof:

1. Let's start with the given, a mod n = b mod n. This means that when a is divided by n, it leaves the same remainder as when b is divided by n.

2. We can write this as: a = q1n + r and b = q2n + r, where q1 and q2 are the quotients of a and b when divided by n, and r is the common remainder.

3. Subtract the second equation from the first to get: a - b = (q1 - q2)*n.

4. This equation tells us that the difference of a and b is a multiple of n, which is the definition of congruence modulo n.

5. Therefore, we can conclude that a ≡ b mod n.

This completes the proof.