Computer Security and Cryptography

11.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM

The starting point for our study of modular arithmetic is Proposition 11.3.

Proposition 11.3: (The Division Algorithm for Integers): If a, b ∈ , with b > 0, there exist unique integers q, r ∈ such that a = qb + r with 0 ≤ r < b and we write a = r (modulo b).

Proof: If b divides a, then a = qb and the algorithm is true with r = 0. Otherwise, let S = {a − qb : q ∈ , a − qb > 0}.

11.3a	If A > 0, q = 0 is in S so that S ≠ ;
11.3b	If a ≤ 0, let q = a − 1 so that q < 0. If b ≥ 1, then a − qb = a(l − b) + b > 0 so again S ≠ .

By the well-ordering principle, S has a minimum element, say r. If r = a − qb, then 0 ≤ r < b or otherwise r − b = a − (q + 1)b, contradicting the minimality of r.

For every integer n ≥ 2, addition, subtraction, and multiplication can be defined on the set of residues modulo n, that is, on the set of integers