Let \( a , b \in \mathbb{Z} \) and assume \( b \ne 0 \). Define \( S = \left \lbrace x \in \mathbb{Z} : x \ge 0 \text{ and } x = a + \left | b \right | \cdot k \text{ where } k \in \mathbb{Z} \right \rbrace \supseteq \mathbb{N}_{0} \), we'll show that \( S \) is non-empty. We can think of \( S \) as taking \( a \) and then either adding muliples of \( \left | b \right | \) or subtracting them to \( a \), each time leaving some remainder, thinking ahead we can guess that the smallest value of this set should be the smallest remainder and possibly the \( r \) we are looking for.
If \( a \ge 0 \) then when \( k = 0 \) we have \( a + \left | b \right | \cdot k = a \ge 0 \) thus \( a \in S \), on the other hand if \( a \lt 0 \), then observe that since \( 0 \le r \lt \left | b \right | \), then \( 1 \le \left | b \right | \iff 0 \le \left | b \right | - 1 \) and also \( - a \gt 0 \), then we have \( 0 \le \left ( \left | b \right | - 1 \right ) \cdot \left ( - a \right ) \). But also we can see that \( \left ( \left | b \right | - 1 \right ) \cdot \left ( - a \right ) = \left | b \right | \cdot \left ( - a \right ) + a \) so it's of the form of an element in \( S \) and since it's non-negative, it must be an element of \( S \). Therefore this paragraph shows us that \( S \) has at least one element, no matter the value of \( a \).
Due to this and since \( S \subseteq \mathbb{N}_{0} \), then by the well ordering principle there is some smallest element \( s \in S \), we know that this value satisfies \( s = a - \left | b \right | \cdot k \). Now we will show that \( 0 \le s \lt \left | b \right | \).
\( s \in S \) so therefore \( s \ge 0 \), if we were to assume that \( s \ge \left | b \right | \) then \( s - \left | b \right | \ge 0 \). By recalling the equality that \( s \) satisifies we can write \( s - \left | b \right | = \left ( a - \left | b \right | \cdot k \right ) - \left | b \right | = a - \left | b \right | \left ( k + 1 \right ) \), therefore \( s - \left | b \right | \in S \) but since \( \left | b \right | \gt 1 \) then \( s - \left | b \right | \lt s \) which is a contradiction because we assumed that \( s \) was the smallest element in \( S \), thus we must have that \( s < \left | b \right | \)
At this point we have \( a = \left | b \right | \cdot k + s \) where \( 0 \le s \lt \left | b \right | \) so take \( q = \text{sgn} \left ( b \right ) \cdot k \) and \( r = s \). If \( b \ge 0 \), then \( \left | b \right | = b \) and \( \text{sgn} \left ( b \right ) = 1 \), so we obtain \( a = b \cdot k + s \), if \( b < 0 \), then \( \left | b \right | = - b \) and \( \text{sgn} \left ( b \right ) = - 1 \) so again we have \( a = \left ( - b \right ) \cdot \left ( - 1 \right ) k + s \). We'll finish the proof by showing that these values are unique.
Assume we have another pair \( \overline{q} , \overline{r} \) satisfying \( a = b \cdot \overline{q} + \overline{r} \) with \( 0 \le \overline{r} \le \left | b \right | \) but \( \overline{q} \ne q \) and \( \overline{r} \ne r \), therefore we have \( b \cdot q + r = b \overline{q} + \overline{r} \iff \overline{r} - r = b \cdot \left ( \overline{q} - q \right ) \).
Without loss of generality assume \( \overline{r} \gt r \), then \( \overline{r} - r \gt 0 \) and since \( 0 \le r \lt \left | b \right | \) then \( 0 \le \overline{r} - r \le \overline{r} \lt \left | b \right | \), recalling that \( \overline{r} - r = \left | b \right | \cdot \left ( \overline{q} - q \right ) \), we can re-write our last inequality as \( 0 \le \left | b \right | \cdot \left ( \overline{q} - q \right ) \lt \left | b \right | \) and since \( b \ne 0 \) we can divide by \( \left | b \right | \) to get \( 0 \lt \overline{q} - q \lt 1 \) but since \( q , \overline{q} \in \mathbb{Z} \) this force \( q = \overline{q} \), which then shows \( r = \overline{r} \) by previous equalities, therefore assuming we have another solution, it turns out it must be our original one, and thus our solution is unique.
For brevity define \( q = a / / b \), we know that \( a = b \cdot q + r \) with \( 0 \le r \lt b \), thus far we know that \( q \in \mathbb{Z} \), though if \( q < 0 \), then we know that \( b \cdot q < r \cdot q \le 0 \), therefore \( a = b \cdot q + r < r \cdot q + r = r \left ( q + 1 \right ) \)
For a contradiction assume that \( q \lt 1 \iff q \le 0 \), therefore \( r \left ( q + 1 \right ) \le r \left ( 0 + 1 \right ) = r \), which shows that \( a \lt r \), since \( 0 \le r \lt b \), then we have \( a \lt b \) which is a contradiction because we know that \( a \ge b \).
Since by assuming \( q \lt 1 \), we have a contradiction, so therefore \( q \ge 1 \), which is the same as \( a / / b \ge 1 \).
If \( m \% n = 0 \), then \( m = \left ( m / / n \right ) \cdot n \), therefore \( \gcd{\left ( m , n \right )} = \gcd{\left ( \left ( m / / n \right ) \cdot n , n \right )} = n \), so now assume that \( m \% n > 0 \)
Recall that \( m = \left ( m / / n \right ) \cdot n + m \% n \), therefore \( m - \left ( m / / n \right ) \cdot n = m \% n \), so that if \( d \) divides both \( m , n \), then it must divide \( m \% n \) (and clearly \( n \)), and by the original equation if \( d \) is a divisor of both \( n , m \% n \) then \( d \) divides \( m \) (and clearly \( n \)).
The above paragraph shows that a number is a divisor of \( m , n \) if and only if it is a divisor of \( n , m \% n \), which shows that their set of divisors are equal and thus \( \gcd{\left ( m , n \right )} = \gcd{\left ( n , m \% n \right )} \)
For the base case, suppose that \( n = 1 \), so we'd like to prove that \( r_{2} \lt \frac{b}{2} \). Firstly we know that \( a = b q_{0} + r_{0} \) with \( 0 \le r_{0} \lt b \), then applying the next iteration we have \( b = r_{0} q_{1} + r_{1} \) with \( 0 \le r_{1} \lt r_{0} \) and one more time, we get \( r_{0} = r_{1} q_{2} + r_{2} \) with \( 0 \le r_{2} \lt r_{1} \), this shows us that \( b = \left ( r_{1} q_{2} + r_{2} \right ) q_{1} + r_{1} \).
Since \( a \ge b \), \( b \gt r_{0} \) and \( r_{0} \gt r_{1} \), then \( q_{0} \ge 1 \), \( q_{1} \ge 1 \) and \( q_{2} \ge 1 \), therefore \( b = \left ( r_{1} q_{2} + r_{2} \right ) q_{1} + r_{1} \ge \left ( r_{1} \cdot 1 + r_{2} \right ) \cdot 1 + r_{1} \ge r 1 + r 2 \) therefore \( r_{2} < \frac{b}{2} \) which concludes the base case
Now let \( k \in \mathbb{N}_{1} \) assuming that \( r_{2 k} \le \frac{b}{2^{k}} \), we want to prove that \( r_{2 \left ( k + 1 \right )} = \frac{b}{2^{k + 1}} \), noting that \( 2 \left ( k + 1 \right ) = 2 k + 2 \).
To start let's say we have an intance of the euclidean algorithm that lasts for at least \( 2 k + 2 \) iterations, therefore we know that \( r_{2 k} \le \frac{b}{2^{k}} \) by our induction hypothesis, additionally at the \( 2 k \)-th iteration we would have an equation of the form \( r_{2 k} = r_{2 k + 1} \left ( q_{2 k + 2} \right ) + r_{2 k + 2} \), since we know that \( r_{2 k + 1} > r_{2 k + 2} \), then \( q_{2 k + 2} \ge 1 \), which then shows that \( r_{2 k} = r_{2 k + 1} \left ( q_{2 k + 2} \right ) + r_{2 k + 2} \ge r_{2 k + 1} + r_{2 k + 1} \), and since \( \frac{b}{2^{k}} \gt r_{2 k} \) , then we know that \( r_{2 k + 2} \lt \frac{1}{2} \cdot \frac{b}{2^{k}} = \frac{b}{2^{k + 1}} \) which is what we needed to show
Let \( m , n \in \mathbb{Z}^{+} \) and assume that \( \gcd{\left ( m , n \right )} = 1 \), we'd like to prove that \( d \left ( m \right ) \cdot d \left ( n \right ) = d \left ( m \cdot n \right ) \)
Suppose that the divisors of \( m \) are \( P = \left \lbrace p_{1} , \ldots , p_{j} \right \rbrace \) and the divisors of \( n \) are \( Q = \left \lbrace q_{1} , \ldots , q_{k} \right \rbrace \)
Claim that the set \( P \cdot Q = \left \lbrace p_{x} \cdot q_{y} : x \in \left [ j \right ] , y \in \left [ k \right ] \right \rbrace \) is exactly equal to the divisors of \( m \cdot n \)