## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 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 = {aqb : q , aqb > 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 = aqb, then 0 ≤ r < b or otherwise rb = 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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required