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

Start Free Trial

No credit card required