Background required: none.

For the first lecture, we shall look at congruence and modular arithmetic. Many of you may have already known (at least on an intuitive level) that square integers can only end in 0, 1, 4, 5, 6, 9; that the product of two odd numbers is odd; that it’s possible to compute the last digit of (say) without since the last digit of goes in cycles. Here, we shall develop the theory behind it and use it to solve some problems later.

We need a language to state something like “n has remainder 5 when divided by 8″. This is where modular arithmetic comes in.

Definition : if a, b, m are integers, we write if a-b is a multiple of m; i.e. if a-b = mk for some integer k. In English, we say “a is congruent to b modulo m”.

Thus, saying “n has remainder 5 when divided by 8″ is the same as . [ Exercise in definition: what does it mean to say ? ] To do anything useful with this notation, we need to develop its properties. First, some very basic ones.

Let a, b, c, m be integers. Then the following hold:

1. We always have .
2. If , then .
3. If and , then .

We shall leave out their proofs since they’re really easy. [ E.g. to prove the third property, we have and for some integers j and k; thus, . ]

The crux of these three properties is that on a purely symbolic level, the notation behaves like equality. Thus, we can write without restraint something like

thanks to the third property above.

The next three properties tell us that the notation is consistent with respect to arithmetic operations.

Let a, b, c, d, m be integers. Then the following hold:

4. If and then .
5. If and then .
6. If then for all n = 1, 2, 3, …

The proofs are as follows. For (4) and (5), we can write a – b = mj and c – d = mk for some integers j and k. Thus:

For (6), we use the known factorisation: for any positive integer n, we can factor the polynomial

In particular, this gives which is a multiple of m. So our proof is done.

Finally, while the above properties already suffice, the following may come in useful.

7. (Cancellation) If , and (c, m) = 1 (here, (x, y) is the greatest common divisor, or highest common factor, of integers x and y), then .

The proof requires Bezout’s identity : if (c, m) = 1, then we can write cx + my = 1 for some integers x and y. For example, if c = 5, m = 8, then we can write x = -3, y = 2. Thus, multiplying this identity by a–b then gives:

(a – b)cx + (a – b)my = (a – b).

Since , the (a – b)c is a multiple of m, so the first term is divisible by m. Clearly, the second term is also divisible by m. Thus, the RHS is divisible by m so . QED.

 If c and m have a common factor > 1, then cancellation fails. E.g. pick m = 6, a = 4, b = 2 and c = 9. Then but .

Coming up next: some applications of modular arithmetic.