Let integer a,b \in \mathbb{Z}, where b \neq 0. We say b divides a (i.e. b|a) if there’s some m \in \mathbb{Z} such that a = bm. additional information division algorithm Let a,b \in \mathbb{Z}, b > 0. Then, there exists, uniquely, some q,r \in \mathbb{Z} such that a = bq + r with 0 \leq r <b. “division with remainder” You will note that, if a < b, we can just say q = 0. Proof: Existence Let us define some:

We will note that this set is definitely non-empty: If a \geq 0, then a = a-b\cdot 0 \in S If a < 0 , then a-b(2a) = a(1-2b), we note that a < 0 and since b >0, (1-2b) <0, so a(1-2b) > 0 and so a(1-2b) \in S So by the WOP, S has a smallest element. Let us, by WOP, define r to be the smallest element in S. Therefore, we can make some r = a-bq \in S. We also know that r is non-negative, as that is the constraint of S. Finally, we have to ensure that r is the actual remainder, we have to ensure that r < b. Assume for contradiction r \geq b. Then, r-b = (a-qb)-b = a-(q+1)b \geq 0. Therefore, r-b \in S. Yet, we said that r was the smallest element, reaching contradiction. Therefore, r<b . \blacksquare Uniqueness Let us have:

Recall that, 0 \leq r < b. We desire that q = q’, r = r’. WLOG let r \leq r’. So, 0 \leq r’ - r. Both r’ and r are remainders after dividing by b, so r’ < b and r < b. Therefore, we have:

Now, recall that:

Now, we have that b|(r’ - r). Hence, we have some positive r’ - r, which is smaller than b, but which is divisible by b. This forces us to conclude that r’ - r = 0. Given r’ = r, now, we can see that q = q’. \blacksquare