Congruences

A clock shows 14:00; we set it forward by 3 hours: it now shows 17:00. We set it forward by a further 10 hours: it does not show 27:00, but 3:00. We have just performed a calculation modulo 24.

The definition

Two integers a and b are congruent modulo n if they have the same remainder when divided by n. We write:

a ≡ b  (mod n)

Which is the same as saying that n divides a - b.

27 ≡ 3   (mod 24)      car 27 - 3 = 24
38 ≡ 12  (mod 26)      car 38 - 12 = 26

This is exactly the operation that mapped Z back to A in the Caesar cipher.

What remains unchanged

The advantage is that one can calculate before or after reduction; the result is the same:

si  a ≡ a'  et  b ≡ b'   (mod n)
alors  a + b ≡ a' + b'   (mod n)
et     a × b ≡ a' × b'   (mod n)

In practical terms, we can reduce at each stage without changing the final result. This is what makes cryptographic calculations feasible: the numbers never grow larger than n.

17 × 23 (mod 5)  =  2 × 3 (mod 5)  =  6 (mod 5)  =  1

A pitfall

Addition and multiplication are carried out modulo, but not division. Writing a / b (mod n) generally makes no sense. We need to use the concept of an inverse — this is the subject of the next lesson.