divides
an integer $$n$$ is divisible by a non-zero integer $$m$$ if there exists an integer $$k$$ such that $$n = k \cdot m$$. If this is all true we write $$m | n$$.
1 divides everything
Suppose that $$j \in \mathbb{Z}$$, then $$1 | j$$
In the definition of divides take $$k = j$$, then we can see that $$j = j \cdot 1$$ thus we can say that $$1 | j$$
0 is divisible by everything
for any $$d \in \mathbb{Z}^{\ne 0} , d | 0$$
In the definition of divides take $$k = 0$$, then we can see that $$0 = 0 \cdot d$$ thus we can say that $$d | 0$$
any integer cannot divide something smaller than itself
Suppose that $$m \in \mathbb{Z}$$, then for any $$a \in \mathbb{Z}^{\ne 0}$$ such that $$- \left | m \right | < a < \left | m \right |$$, then $$m$$ does not divide $$a$$
Suppose that for the sake of contradiciton that $$m | a$$ , then there is some $$k \in \mathbb{Z}$$ such that $$a = m k$$
forced division of sum
Suppose that $$m | a$$ and that $$m | \left ( a + b \right )$$ then $$m | b$$
TODO
even number
Given an integer $$a$$, we say that it is even when $$2 | a$$
quotient remainder
Suppose that $$a , b \in \mathbb{Z}$$, but that $$b \ne 0$$, then there exists unique integers $$q , r$$ such that $$a = b \cdot q + r$$ where $$0 \le r \lt \left | b \right |$$

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.

remainder function
Given two integers $$a , b \in \mathbb{Z}$$ such that $$b \ne 0$$, then we get some $$q , r \in \mathbb{Z}$$ with $$0 \le r \lt \left | b \right |$$ such that $$a = b \cdot q + r$$ and we define $$a \% b := r$$
divisor function
Given two integers $$a , b \in \mathbb{Z}$$ such that $$b \ne 0$$, then we get some $$q , r \in \mathbb{Z}$$ with $$0 \le r \lt \left | b \right |$$ such that $$a = b \cdot q + r$$ and we define $$a / / b := q$$
quotient remainder on positive integer has positive divisor
Suppose that $$a , b \in \mathbb{N}_{1}$$ such that $$a \ge b$$ then $$a / / b \ge 1$$

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$$.

every integer is either odd or even
For any $$z \in \mathbb{Z}$$, it is even or it is odd
Let $$z \in \mathbb{Z}$$ and then we know that $$z \% 2 \in \left \lbrace 0 , 1 \right \rbrace$$, if $$z \% 2 = 1$$ then there is some $$q \in \mathbb{Z}$$ such that $$z = q \cdot 2 + 1$$, and thus odd, if $$z \% 2 = 0$$, then we have some $$q \in \mathbb{Z}$$ such that $$z = q \cdot 2 + 0$$ and is thus even.
composite number
A number $$n \in \mathbb{N}_{1}$$ is said to be composite, when it has a positive divisor other than $$1$$ and itself
prime
A number $$p \in \mathbb{N}_{1}$$ is said to be prime if it's only divisors are $$1$$ and $$p$$
greatest common divisor
suppose that $$a , b \in \mathbb{Z}$$ then the greatest common divsor of $$a$$ and $$b$$ notated as $$\gcd{\left ( a , b \right )}$$ is the largest positive integer that divides each of $$a , b$$
same divisors implies same gcd
Suppose that $$a , b , p , q \in \mathbb{Z}$$ and that $$D_{a , b} = \left \lbrace d \in \mathbb{Z} : d \left \lvert a \text{ and } d \mid b \right \rbrace \right.$$ and $$D_{p , q} = \left \lbrace d \in \mathbb{Z} : d \left \lvert p \text{ and } d \mid q \right \rbrace \right.$$ are equal, then $$\gcd{\left ( a , b \right )} = \gcd{\left ( p , q \right )}$$
TODO
coprime integers
$$a , b \in \mathbb{Z}$$ are said to be coprime if the only positive integer that divides them is $$1$$.
$$a , b \in \mathbb{Z}$$ are coprime if and only if $$\gcd{\left ( a , b \right )} = 1$$
TODO
euclidean algorithm
Let $$m , n \in \mathbb{N}_{1}$$ such that $$m > n$$, if $$m \% n > 0$$, then $$\gcd{\left ( m , n \right )} = \gcd{\left ( n , m \% n \right )}$$. Otherwise if $$m \% n = 0$$, then $$n | m$$ and $$\gcd{\left ( m , n \right )} = n$$

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 )}$$

bounded sum implies one less then half
Suppose that $$x , y , b \in \mathbb{N}_{1}$$ and $$x < y$$ with $$x + y \le b$$, then $$x < \frac{b}{2}$$
Suppose for the sake of contradiction that $$x \ge \frac{b}{2}$$, then we know that $$y > x \ge \frac{b}{2}$$ so therefore $$x + y \gt \frac{b}{2} + \frac{b}{2} = b$$, so we have $$x + y > b$$ which is a contradiction so that $$x < \frac{b}{2}$$.
euclidean algorithm has exponentially decreasing remainders
Let $$a , b \in \mathbb{N}_{1}$$ with $$a \ge b$$ be two integers, and suppose we will preform the euclidean algorithm on them to compute $$\gcd{\left ( m , n \right )}$$, supposing that $$r_{k}$$ represents the remainder after $$k$$ (where $$k \in \mathbb{N}_{1}$$) steps into the euclidean algorithm, then $$r_{2 n} \lt \frac{b}{2^{n}}$$

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

upper bound on euclidean algorithm iterations
The euclidean algorithm terminates in at most $$2 \log_{2}{\left ( b \right )}$$ iterations
The euclidean algorithm terminates in $$k$$ iterations if and only if $$r_{k} = 0$$, we know that for all $$n \in \mathbb{N}_{1}$$ that $$r_{2 n} \lt \frac{b}{2^{n}}$$, therefore when $$n = \log_{2}{\left ( b \right )}$$, then we have $$r_{2 \log_{2}{\left ( b \right )}} \lt \frac{b}{2^{\log_{2}{\left ( b \right )}}} = \frac{b}{b} = 1$$, but if $$r_{2 \log_{2}{\left ( b \right )}} \lt 1$$, then since the remainders are always elements of $$\mathbb{N}_{0}$$, then we know that $$r_{2 \log_{2}{\left ( b \right )}} = 0$$, thus we've shown after $$2 \log_{2}{\left ( b \right )}$$ iterations the algorithm must terminate
multiplicative function
an arithmetic function is said to be multiplicative when
$$f{\left ( m \right )} \cdot f{\left ( n \right )} = f{\left ( m \cdot n \right )}$$
for all coprime positive integers $$m , n$$
Suppose that $$d \left ( n \right )$$ is the number of divisors of $$n$$, then $$d$$ is a multiplicative function.

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$$