Monday, September 24, 2012

The fundamental theorem of arithmetic

Lecture notes for lecture #9 of MATH 235, normally taught by Henri Darmon, but with Miljan Brakočević temporarily filling in while Darmon is away for a week. These lecture notes are student-generated and any errors or omissions should be assumed to be the fault of the notetaker and not of the lecturer. To correct an error, you have to be registered and logged-in; alternatively, you can contact @dellsystem directly.

1Primes and unique factorisation¶

An integer $p \in \mathbb{N} \setminus \{0, 1\}$ is prime if its only divisors are $\pm 1$ and $\pm p$.

1.1The sieve of Eratosthenes¶

One method for efficiently finding all the primes up to a number $n$ is called sieve of Eratosthenes. This method has been known since the days of ancient Greece, and is illustrated in the following example, with $n=120$ (source):

We start at two, and record that as prime. Then, we cross off all the multiples of two (2, 4, 6, etc). Then we move on to three, and record that as prime, then cross off all the multiples of three. And so on. We can stop the crossing-off when we reach a number $> \sqrt{n}$, for after $sqrt{n}$, all the numbers that have not yet been crossed off will no longer be crossed off by subsequent multiples. Consequently, once we get to $\sqrt{n}$, all the non-crossed-off numbers that remain are prime.

That we only need to check the numbers up until $\sqrt{n}$ can be proved as follows. Let $n = pq$, where $p$ and $q$ are prime. Then, we have that either $p \leq \sqrt{n}$ or $q \leq \sqrt{n}$. This is because if both $p$ and $q$ are greater than $\sqrt{n}$, then $pq > \sqrt{n} \cdot \sqrt{n}$, and so we would have that $pq > n$, which contradicts the premise that $n = pq$.

The description of this algorithm is mostly a historical remark, as an introduction to prime numbers. Still, this method is quite efficient and is often used in computer algorithms for computing and detecting prime numbers.

1.2The fundamental theorem of arithmetic¶

The fundamental theorem of arithmetic can be stated quite simply:

Every non-zero number can be uniquely represented as a product of primes.

The proof of this is slightly more involved. First, by convention, we allow the empty product to be equal to 1. Then, to prove the theorem, we have to prove first that every number can indeed be represented as a product of times (the existence property), and then we have to prove that this prime factorisation is unique for each integer (the uniqueness property).

In symbolic notation, we are trying to prove that for all $n > 0$, we can write $n = \epsilon p_1 \ldots p_m$, where $\epsilon = \pm 1$, and $0 \leq p_1 \ldots \leq p_m$, where $m \geq 0$, and that these values for $p_i$ are unique. Without loss of generality (WLOG), we can restrict our proof to $\mathbb{Z}^+$ (with $\epsilon = 1$, so with $n \geq 0$.¹

1.2.1The existence property¶

To prove that every $n > 0$ can be written as a product of primes, we use the well-ordering principle of the natural numbers in a proof by contradiction. Suppose that the existence property does not hold, i.e., there is a non-empty set $S$ of numbers, $n > 0$, which can not be written as a product of primes. This set $S$ must have a minimal element, $n_0$, such that $n_0 \leq s \forall s \in S$. Now, $n_0$ cannot be prime, or equal to 1, because those can be trivially written as the product of primes.

So if $n_0$ is not prime, then it can be written as the product of integers $s, t \in \mathbb{N}$, such that $1 < s, t < n_0$. Now, $s$ and $t$ cannot be in $S$, because they are less than $n_0$ and the minimality of $n_0$ in $S$ would be contradicted. So $s$ and $t$ must not be in $S$, and so it must be possible to write them as the product of prime numbers:

$\begin{align*} s & = q_1 \ldots q_a \\ t & = p_1 \ldots p_b \end{align*}$

But if $s$ and $t$ can be written as the product of primes, then $st$ must also be a product of primes, and so we can write $n = st = q_1\ldots q_a p_1 \ldots p_b$, which is a product of primes. This contradicts our original premise that $n_0$ cannot be written as a product of primes, by virtue of belonging to the non-empty subset $S$. It then follows that the the set $S$ is empty, and so there are no numbers $n$ where $n > 0$ that cannot be written as a product of primes.

1.2.2The uniqueness property¶

Next we have to prove that there is only one way of writing a number as a product of primes. First, we prove the following lemma (proposition 10.0.5 in the notes):

Let $p \in \mathbb{Z}$. Then, the following are equivalent (TFAE):

1. $p$ is prime
2. If $p$ divides $ab$, then either $p$ divides $a$ or $p$ divides $b$.

First, we prove that (1) $\to$ (2). So $p$ is prime, which means that if has no divisors other than $p$ and $1$. Well, if $p \nmid a$, then the gcd of $p$ and $a$ is, trivially, 1 (since they have no other common divisors). By corollary 9.1.3, it must be that $p \mid b$.

Now, we prove that (2) $\to$ (1). We can write $p$ as the product of numbers $s$ and $t$, which may or may not be prime. We have to show that $s$ and $t$ are none other than $1$ and $p$. Since it is trivially true that $p \mid st$, we can use the fact that either $p \mid s$ or $p\mid t$. WLOG, we let it be true that $p \mid s$. That means that $s = p \cdot s'$, where $s' \in \mathbb{Z}$, and so $p = ps't$. Clearly, $s't = 1$, and so $s'$ and $t$ are also both equal to 1; consequently, $s = p \cdot 1 = p$. So we've proved that $s$ and $t$ are none other than $p$ and 1, and so the proof of the lemma is complete.

Remark: if $p$ (still prime) divides $q_1 \ldots q_t$, then $p$ must divide one of these $q$s (from proposition 10.0.5 above, worked further by induction).

We can now begin the proof of the uniqueness property. Suppose we have two prime factorisations for $n$: $n = \epsilon p_1\ldots p_m = \mu q_1\ldots q_t$, where $p$ and $q$ are ordered such that $p_1 < \ldots < p_m$ and $q_1 < \ldots < q_t$. We can let $\epsilon = \mu = 1$ since $n > 0$. We want to prove that $p_i = q_i$ for all $i$.

We then proceed along a proof by induction of the uniqueness property using proposition 10.0.5. For $n=1$, we have the empty product on both sides, so it's trivially true. Now we assume that the uniqueness property holds for $n-1$, and we have to show that it holds for $n$ as well. WLOG, let $p_1 \leq q_1$ (we could just switch them around to account for the other case). So if $p_1 \mid q_1 \ldots q_t$ (which is true, as $p_1 \mid n$, since it's a prime factor of $n$), then $p_1 \mid q_i$ for some $i$, from proposition 10.0.5. But since all the $p$s and $q$s are prime, the it must be that $p_1 = q_i$, and it must also be that $i = 1$ due to the ordering we previously imposed (that is, $p_1 \leq q_1$). So $p_1=q_1$, and we can cancel them on both sides, which reduces the statement to the induction hypothesis². $\blacksquare$

At long last, the proof for the fundamental theorem of arithmetic is complete. Let's move on.

1.3Euclid's theorem¶

Euclid's theorem, presented in section 10.0.7 of the notes, states that there are infinitely many primes. Although Euclid's original proof was not technically a proof by contradiction (though it did contain one nested within it somewhere), the proof presented in lecture is, and proceeds as follows³:

Assume that the set of all the primes in the entire world is finite, represented in an ordered set as $P = \{p_1, \ldots, p_n\}$ (where $p_n$ is the largest prime number). Now consider the number $N = p_1\ldots p_n + 1$. This number can't be a prime number, because it is greater than the largest prime number $p_n$ by at least one, and so is not in $P$. And yet it is a prime number, because the gcd of $N$ and any $p \in P$ (i.e. any prime) is 1, as dividing $N$ by $p$ will always leave a remainder of 1. So we reach a contradiction, which implies that the set of all the primes is not finite.

1.4The number of primes in an interval¶

The number of primes in the interval $\displaystyle [1, n] \sim \frac{n}{\log n}$ as $n \to \infty$. Pretty neat.