Loading [MathJax]/jax/element/mml/optable/MathOperators.js

Monday, September 24, 2012 CC-BY-NC
The fundamental theorem of arithmetic

Maintainer: admin

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 pN{0,1} is prime if its only divisors are ±1 and ±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):

Sieve of Eratosthenes illustration

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 >n, for after sqrtn, all the numbers that have not yet been crossed off will no longer be crossed off by subsequent multiples. Consequently, once we get to n, all the non-crossed-off numbers that remain are prime.

That we only need to check the numbers up until n can be proved as follows. Let n=pq, where p and q are prime. Then, we have that either pn or qn. This is because if both p and q are greater than n, then pq>nn, 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=ϵp1pm, where ϵ=±1, and 0p1pm, where m0, and that these values for pi are unique. Without loss of generality (WLOG), we can restrict our proof to Z+ (with ϵ=1, so with n0.1

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, n0, such that n0ssS. Now, n0 cannot be prime, or equal to 1, because those can be trivially written as the product of primes.

So if n0 is not prime, then it can be written as the product of integers s,tN, such that 1<s,t<n0. Now, s and t cannot be in S, because they are less than n0 and the minimality of n0 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:

s=q1qat=p1pb

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=q1qap1pb, which is a product of primes. This contradicts our original premise that n0 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 pZ. 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) (2). So p is prime, which means that if has no divisors other than p and 1. Well, if p, 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 qs (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 ps and qs 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 hypothesis2. \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 follows3:

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.

  1. To extend this proof to the negative integers, we simply have to say that if n < 0, then -n > 0, and as the theorem holds for -n it must hold for n as well, as we can just set \epsilon = -1

  2. Actually, it seems that it doesn't reduce exactly to the induction hypothesis. Perhaps that is not important 

  3. The proof given here is not exactly what was given in class, but my notes for that section don't really make sense so this will have to do.