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:
(2)
\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:
(3)
\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$:
(4)
\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:
(5)
\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:
(6)
\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:
(7)
• We thus want to show that $S(m)$ implies $S(m+1)$:
(8)
• Since $p$ is a prime that divides the product of $a_1$ through $a_m$ as well as $a_{m+1}$, it follows that:
• If $p \mid a_{m+1}$ then $i = m+1$ and the proof is complete. If not, then:
• Hence $S(m+1)$ is true and by the principle of mathematical induction, $S(k)$ is also true for all $k \geq 1$. $\blacksquare$