Division Algorithm
Every can be written with and ; moreover and are unique.
Proposition 4.7 (Division Algorithm)
Given , we can write , where with . [We are using and to denote the quotient and remainder respectively.]
Proof
Induction on . The statement is true for . For the inductive step, let and suppose the statement holds for all natural numbers , so for some with . If , then
with . Otherwise , and then
Either way has the desired form.
The values obtained are unique: if , then . Since , we have , and the only multiple of in this range is . Hence and therefore .
Related
Stated in
- Proposition 4.7 (Division Algorithm)§4.2 Highest Common Factor