Chapter 5 Congruences

At the time of typsetting these notes, it was 11 o’clock. In 1 hours time it will be 12 o’clock and in 2 hours it will be 13 o’clock. Of course we don’t normally refer to that time as 13 o’clock, but rather as 1 o’clock. In referring to the time, we use a system of arithmetic that we refer to as modular arithmetic. In modular arithmetic we simplify number-theoretic problems by replacing each integer with its remainder when divided by some fixed positive integer \(n\). So, for example, when telling the time we use \(n=12\).

This has the effect of replacing the infinite number system \(\mathbb Z\) with a number system \({\mathbb Z}_n\) which contains a finite number (\(n\)) of elements.

In this and the next chapter we shall study the properties of this new number system and show that we can perform arithmetic on these ‘numbers’ in the same way we can for the integers. We will find that we can

• add,
• subtract and
• multiply

the elements of \({\mathbb Z}_n\), just as we can in \({\mathbb Z}\). Indeed we’ll see that the number system \({\mathbb Z}_n\) is an example of a ring.

WARNING: as usual we will avoid ‘’division’’ but for modular arithmetic there are even some difficulties with cancellation. The axiom (ZD) may not hold.