ELEMENTARY PROPERTIES
Lemma 6.1 (Division Algorithm for Z). If is a positive integer and is any integer, then there exist unique integers and such that
Proof. We give an intuitive diagrammatic explanation. On the “real x-axis” of analytic geometry, mark off the multiples of and the position of . Now n falls either on a multiple of and can be taken as 0, or falls between two multiples of . If the latter is the case, let be the first multiple of to the left of . Then is as shown on the diagrams in Fig 6.1. Note that 0 ≤ < . After a little thought, the uniqueness of and is clear from the diagrams