Chapter 2: Prime Numbers and Prime Factorization

Proof (by contradiction).

Suppose, for contradiction, that there are only finitely many primes and let $p_1, p_2, \ldots, p_n$ be all of them.

Consider the number $N$ defined by

$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

Since $N > 1$, it is divisible by some prime $p$.

However, dividing $N$ by $p_1$ gives $N = p_1 \cdot (p_2 \cdots p_n) + 1$, so the remainder is always $1$. The same is true when dividing by any of $p_2, p_3, \ldots, p_n$: the remainder is $1$.

In other words, $N$ is not divisible by any of the primes in our list. Hence the prime $p$ that divides $N$ differs from every $p_1, p_2, \ldots, p_n$.

This contradicts the assumption that $p_1, \ldots, p_n$ are all the primes.

Therefore, there are infinitely many primes. $\square$

Proof.

Assume $p \mid ab$ but $p \nmid a$ ($p$ does not divide $a$). Since $p$ is prime, the greatest common divisor of $p$ and $a$ is $\gcd(p, a) = 1$ (the divisors of $p$ are only $1$ and $p$, and $p$ does not divide $a$).

Since $\gcd(p, a) = 1$, there exist integers $s, t$ such that

$$ps + at = 1$$

holds. This is known as Bézout's identity, and $s, t$ can be computed explicitly by reversing the steps of the Euclidean algorithm (see Euclidean algorithm for details). Multiplying both sides by $b$,

$$pbs + abt = b$$

The first term $pbs$ on the left is divisible by $p$. The second term $abt$ is also divisible by $p$ since $p \mid ab$. Hence the right-hand side $b$ is also divisible by $p$. $\square$

Proof (existence).

We prove by induction on $n > 1$.

When $n = 2$: $2$ is prime, so it is itself its prime factorization.

Inductive hypothesis (up to $n - 1$): assume the statement holds for every integer between $2$ and $n-1$ inclusive.

• If $n$ is prime, then $n$ itself is the prime factorization.
• If $n$ is composite, then $n = ab$ for some $1 < a, b < n$.

By the inductive hypothesis, both $a$ and $b$ have prime factorizations.

Multiplying them yields a prime factorization of $n$. $\square$

Proof (uniqueness).

Suppose $n$ admits two prime factorizations:

$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$$

Since $p_1$ divides the left-hand side, it also divides the right-hand side $q_1 q_2 \cdots q_s$. Repeated application of Euclid's lemma shows that $p_1$ divides some $q_j$. Since $q_j$ is prime, $p_1 = q_j$.

Canceling $p_1 = q_j$ from both sides and repeating the same argument, one eventually shows that all prime factors agree (up to order). $\square$

Proof (number of divisors).

Each divisor of $n$ has the form $d = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ with $0 \leq a_i \leq e_i$.

Each $a_i$ has $(e_i + 1)$ choices, namely $0, 1, 2, \ldots, e_i$.

Therefore, the number of divisors equals $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$. $\square$

Proof (sum of divisors).

The sum of divisors of $n$ is the sum over all divisors $d = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ with $0 \leq a_i \leq e_i$, so

$$\sigma(n) = \sum_{a_1=0}^{e_1} \sum_{a_2=0}^{e_2} \cdots \sum_{a_k=0}^{e_k} p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

Since the summations over different primes $p_i$ are independent, the multiple sum factors as a product:

$$= \left(\sum_{a_1=0}^{e_1} p_1^{a_1}\right) \left(\sum_{a_2=0}^{e_2} p_2^{a_2}\right) \cdots \left(\sum_{a_k=0}^{e_k} p_k^{a_k}\right)$$

Each factor is a geometric series:

$$\sum_{a=0}^{e} p^a = 1 + p + p^2 + \cdots + p^e = \dfrac{p^{e+1} - 1}{p - 1}$$

Therefore,

$$\sigma(n) = \dfrac{p_1^{e_1+1}-1}{p_1-1} \cdot \dfrac{p_2^{e_2+1}-1}{p_2-1} \cdots \dfrac{p_k^{e_k+1}-1}{p_k-1} \qquad \square$$