Composite Numbers
Composite Numbers
Definition: A Composite Number is an integer $c > 2$ that is not prime and hence contains more positive divisors apart from $1$ and $c$. |
For example, the first few composite numbers are:
(1)\begin{align} \quad 4, 6, 8, 9, 10, 12, 14, 15, 16, ... \end{align}
We will immediately jump into some nice results regarding composite numbers.
Lemma 1: If $c$ is a composite number then there exists a divisor $d$ such that $1 < d ≤ \sqrt{c}$. |
- Proof: Let $c$ be a composite number. Then for $d_1$ and $d_2$ as divisors of $c$ where $d_1, d_2 > 1$ we can write $c$ as:
\begin{align} \quad c = d_1d_2 \end{align}
- Now suppose that $d_1$ and $d_2$ were such that $d_1 > \sqrt{c}$ and $d_2 > \sqrt{c}$. Then:
\begin{align} \quad c = d_1d_2 > \sqrt{c} \cdot \sqrt{c} = c \end{align}
- But clearly $c \neq > c$. Therefore at least one of $d_1$ or $d_2$ is greater than $1$ and less or equal to $\sqrt{c}$. $\blacksquare$
Lemma 2: If $c$ is composite, then there exists a prime divisor $p_i$ of $c$ such that $1 < p_i \leq \sqrt{c}$. |
- Proof: Let $c$ be a composite number. Consider a prime factorization of $c$:
\begin{equation} c = p_1p_2...p_n \end{equation}
- Since $c$ is composite we must have that $n \geq 2$. Suppose that $p_1, p_2, ..., p_n > \sqrt{c}$. Then:
\begin{align} \quad c = p_1p_2...p_n > \sqrt{c}^n = \sqrt{c}^{2} \cdot \sqrt{c}^{n-2} = c \sqrt{c}^{n-2} \end{align}
- Since $c > 1$ we have that $\sqrt{c}^{n-2} > 1$. Therefore:
\begin{align} \quad c = ... > c \sqrt{c}^{n-2} > c \end{align}
- Once again $c \neq > c$ and so at least one of $p_1, p_2, ..., p_n$, say $p_i$ where $i \in \{1, 2, ..., n \}$ is such that $1 < p_i < \sqrt{c}$. $\blacksquare$
Lemma 3: If $p$ is a prime and $p \mid a_1a_2...a_k$ then $p \mid a_i$ for some $i \in \{1, 2, ..., k \}$. |
- Proof: This can be proven with induction. Let $S(k)$ be the statement that if $p \mid a_1a_2...a_k$ then $p \mid a_i$ for $i \in \{1, 2, ..., k \}$.
- Base Step ($k=1$): It follows that trivially that when $k=1$, then $p \mid a_1$.
- Induction Step $S(m) \implies S(m+1)$: Fix some integer $m \geq 1$ and assume that the statement $S(m)$ is true, that is:
\begin{align} \quad S(m): p \mid a_1a_2a_3...a_m \quad \mathrm{then} \quad p \mid a_i \quad \mathrm{for} \quad 1 \leq i \leq m \end{align}
- We thus want to show that $S(m)$ implies $S(m+1)$:
\begin{align} \quad S(m+1): p \mid a_1a_2a_3...a_{m+1} \quad \mathrm{then} \quad p \mid a_i \quad \mathrm{for} \quad 1 \leq i \leq (m+1) \end{align}
- We have that:
\begin{align} \mathrm{If} \quad p \mid a_1a_2a_3...a_m \quad \mathrm{then} \quad p \mid a_1a_2a_3...a_ma_{m+1} \end{align}
- Since $p$ is a prime that divides the product of $a_1$ through $a_m$ as well as $a_{m+1}$, it follows that:
\begin{align} \quad p \mid (a_1a_2a_3...a_m) \quad \mathrm{or} \quad p \mid a_{m+1} \end{align}
- If $p \mid a_{m+1}$ then $i = m+1$ and the proof is complete. If not, then:
\begin{align} p \mid (a_1a_2a_3...a_m) \quad \mathrm{then} \quad p \mid {a_i} \quad \mathrm{for} \quad 1 ≤ i ≤ m \end{align}
- Hence $S(m+1)$ is true and by the principle of mathematical induction, $S(k)$ is also true for all $k \geq 1$. $\blacksquare$