PineWikiThe division algorithm says that for any integers n and m≠0, there exist unique integers q and r such that n = qm+r and 0≤r<|m|. The number q is called the quotient of n by m and r is the remainder. The number m is called the divisor or (when we are mostly interested in remainders) the modulus.
The quotient is often written as ⌊n/m⌋, the floor of n/m, to make it clear that we want the integer version of the quotient and not some nasty fraction. The remainder is often written as (n mod m), pronounced "the remainder of n modulo m" when paid by the word but usually just "n mod m."
This can be proved any number of ways, e.g. by induction on |n|, but the easiest is probably this method taken from BiggsBook §8.2. Let's assume for the moment that n and m are both non-negative. Consider the set R = { r | r ≥ 0 and there exists some q such that n = qm+r }. Observe that R is non-empty since it contains n. Since this is a nonempty subset of the naturals, it has a least element—call it r. We already have r ≥ 0 by definition, and if r ≮ m we have r = n - qm implies r' = n-(q+1)m ≥ 0 with n = (q+1)m + r' and thus r is not the minimum (note we need m≠0 here so that r'≠r). So for the minimum r we have 0 ≤ r < m.
Note that this r is unique (since R only has one minimum), but we haven't proved that it's the only element of R less than m (BiggsBook cheats a bit on this point). To do so, consider any r' with r' ≥ r and corresponding quotient q' such that n = qm+r = q'm+r'. Then r' - r = m(q-q'). If q-q' = 0, r' = r and we are happy. If q-q' ≥ 1, then r' - r ≥ m and thus r' ≥ m + r ≥ m.
So far we have only proved the result when n and m are both non-negative. If m is negative, use the existence and uniqueness of q and r such that n = q(-m)+r with 0 ≤ r < -m to get n = (-q)(m) + r with 0 ≤ r < |m|. If n is negative, first compute -n = q'm + r' and then let either (a) q = -q' and r = 0 if r' = 0 or (b) q = -q'-1 and r = m-r' if r' > 0. In the first case we then have n = qm+r = (-q')m + 0 = -(q'm+r') as expected, and in the second we have n = qm+r = (-q'-1)m + (m-r') = -q'm - m + m - r' = -(q'm+r').
Note that quotients of negative numbers always round down. For example, ⌊(-3)/17⌋ = -1 even though -3 is much closer to 0 than -17. This is so that the remainder is always non-negative (14 in this case).