# Introduction to Number Theory: Divisibility

## Mathematical Induction
**Mathematical induction** is a powerful proof technique used to prove that a statement $\mathcal{P}(n)$ is true for all integers n greater than or equal to a starting integer $n_0$.

The principle of mathematical induction states:

* **Base Case:** If the statement $\mathcal{P}(n_0)$ is true for some integer $n_0$.
* **Inductive Step:** If the truth of the statement for some integer $k \geq n_0$ (the inductive hypothesis) implies its truth for $k+1$, i.e., $\mathcal{P}(k) \Rightarrow \mathcal{P}(k+1)$.

Then, the statement $\mathcal{P}(m)$ is true for all integers $m \geq n_0$.

:::warning
**Exmaple** Prove that $n! \leq n^n$ for any integer $n \geq 1$.

**Proof.**
* **Base Case:** For $n=1$, we have $1!=1$ and $1^1=1$. Since $1 \leq 1$, the statement holds.
* **Inductive Step:** Assume the statement holds for some integer $k \geq 1$. That is, assume $k! \leq k$ (**inductive hypothesis**).

We want to show that the statement also holds for $k+1$, i.e., $(k+1)! \leq (k+1)^{k+1}$.

Using our assumption, we can write:
$$
(k+1)! = (k+1)\cdot k! \leq (k+1) \cdot k^k.
$$

Since $k<k+1$, we know that $k^k < (k+1)^k$. Therefore, we have:
$$
(k+1) \cdot k! < (k+1) \cdot (k+1)^k = (k+1)^{k+1}
$$

Thus, we have shown that $(k+1)! \leq (k+1)^{k+1}$.

By the principle of mathematical induction, the statement $n! \leq n$ holds for all $n \geq 1$. $\Box$
:::

Another form of mathematical induction is **strong induction**.

* **Base Case:** If the statement $\mathcal{P}(n_0)$ is true for some integer $n_0$.
* **Inductive Step:** If the truth of the statement for all integers $k$ from $n_0$ up to some $n$ implies its truth for $n+1$, i.e., $\left[\mathcal{P}(1) \wedge\mathcal{P}(2) \wedge \ldots \wedge \mathcal{P}(n) \right] \Rightarrow \mathcal{P}(n+1)$.

Then, the statement is true for all integers $n \geq n_0$.

:::warning
**Example.** Let $\{x_n\}_{n \geq 1}$ be the sequence defined as: $x_1 = 2$ and $x_{n+1} = x_n + x_{n-1} + \cdots + x_1 + 2$. Prove that $x_n = 2^n$ for each integer $n \geq 1$.

**Proof.**
* **Base Case:** For $n=1$, we have $x_1=2$, and $2^1=2$. The statement holds.
* **Inductive Step:** Assume that $x_k = 2^k$ for all integers $k$ such that $1 \leq k \leq n$ for some $n \geq 1$. We want to prove that $x_{n+1} = 2^{n+1}$.

From the definition of the sequence, we have:
$$
x_{n+1} = x_n + x_{n-1} + \cdots + x_1 + 2
$$

Using our strong inductive hypothesis, we can substitute $x_k=2^k$ for each term in the sum:

$$
x_{n+1} = 2^n + (2^{n-1} + \cdots + 2^1) + 2
$$

The terms in the parentheses form a geometric series with a sum of $2^n-2$. Therefore,

$$
x_{n+1} = 2^n + (2^n-2) + 2 = 2 \cdot 2^n = 2^{n+1}
$$

Since we have shown the statement holds for $n+1$, by strong induction, $x_n=2^n$ for all integers $n \geq 1$.
:::

:::success
**Exercise**
1. Conjecture a formula $A^n$ where $A = \begin{bmatrix}1&1\\
0 & 1 \end{bmatrix}$. Prove your conjecture using mathematical induction.
2. Show that any amount of postage that is an integer number of cents greater than 11 cents can be formed using just 4-cent and 5-cent.
3. Use amthematical induction to prove that $n^2<n!$ for $n \geq 4$.
4. Suppose that $a_0=1,a_1=3,a_2=9$ and $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ for $n\geq 3$. Show that $a_n \leq 3^n$ for every nonegative integer $n>0$.
:::

## Divisibility
:::info
**Definition** Given $a,b \in \mathbb{Z}$ and $a \neq 0$, we say $a$ **divides** $b$ (denoted by $a \mid b$) if there exists an integer $c$ such that $b=c\cdot a$.
:::

### Properties of Divisibility
For $a,b,c,m,n \in \mathbb{Z}$, we have the following properties:
* (Transitivity) If $a\mid b$ and $b \mid c$, then $a \mid c$.
* (Linear Combination) If $c\mid a$ and $c \mid b$, then $c \mid ma+nb$

:::danger
**The Division Algorithm**
For any integer $a$ and any positive integer $b$, there exist unique integers $q$ (the **quotient**) and $r$ (the **remainder**) such that:
$$
a=bq+r \quad \text{where} \quad 0 \leq r<b
$$

We can compute these values as follows:
* $q = \lfloor \frac{a}{b} \rfloor$
* $r = a - b \lfloor \frac{a}{b} \rfloor$
:::

:::warning
**Example**
1. $a=1028$ and $b=34$.
* $q = \lfloor \frac{1028}{34} \rfloor = \lfloor 30.235... \rfloor = 30$
* $r=1028−34(30)=1028−1020=8$
* Therefore, $1028=34⋅30+8$.
2. $a=-380$ and $b=75$.
* $q = \lfloor \frac{-380}{75} \rfloor = \lfloor -5.066... \rfloor = -6$
* $r=−380−75(−6)=−380+450=70$
* Therefore, $−380=75(−6)+70$.
:::

:::success
**Exercise**
5. Show that the product of two intergers of the form $4k+1$ is again of this form, whereas the product to two integers of the form $4k+3$ is of the form $4k+1$.
6. Show that the square of every odd integers is of the form $8k+1$.
7. Show that the product of any three consecutive integers is divisible by 6.
:::