math_class: Number Theory 101 (Fundamental Theorem of Arithmetic)

First things first---Definitions

I should start off by mentioning (again) that a prime number is an integer greater than one whose only positive divisors are one and itself. For example, 2 is a prime number. Its only positive divisors are 1 and 2. Similarly, 5 is a prime number. It is not divisible by 2, 3, 4 or any number greater than 5. Its only positive divisors are 1 and 5. The number 6 is not a prime number. It is divisible by 2 and 3 (in addition to 1 and 6).

Integers greater than one which are not prime are called composite numbers.

Prime numbers play some very important roles in number theory (as well as other branches of mathematics). As I mentioned in the previous lesson, all of the numbers relatively prime to a number n form a group under the operation multiplication modulo n. Every number which is not a multiple of n is relatively prime to n if n is a prime number. At the same time, all numbers form a group under the operation addition modulo n. Those two things (along with a few other properties which easily hold for integers modulo n) mean that the integers modulo n form what is called a field under the operations of multiplication and addition modulo n. Every element in a field which isn't equivalent to zero has a multiplicative inverse. This will come in handy later in this lesson and in future lessons.

Knowing that the numbers modulo a prime number form a field is not really critical to this course. But, for the curious, I will demonstrate this a bit. I will explicitly show the addition and multiplication tables of the numbers modulo 7.

Here is the addition table.

Here is the multiplication table.

You'll note in both of these that (if you ignore the multiples of zero in the second table) that each number appears once in each row and once in each column. Some of our proofs will depend upon the fact that each number appears at least once in each row and each column. Other proofs will depend upon that fact that each number appears only once in each row and each column. Still other proofs will only be concerned with the fact that 1 appears in every row and every column.

Some Divisibility Things

Euclid's Lemma states that if b * c is divisible by a and gcd(a,b) = 1, then c is divisible by a. The proof of this is a bit subtle, but well within our grasp here.

We showed in an earlier lesson that the greatest common divisor of two numbers a and b can be written in the form gcd(a,b) = a * x + b * y where x and y are integers. In this case, it means that we can write 1 in the form 1 = a * x + b * y.

If we multiply that expression by c, we get that c = ( a * x + b * y ) * c. We can multiply that through to form: c = a * c * x + b * c * y. It is easy to see that a * c is divisible by a. And, we were given that b * c is divisible by a. Thus, a * c * x + b * c * y is divisible by a. That whole expression was equal to c, so c is divisible by a.

In terms of prime numbers, what this means is that if a * b is divisible by a prime number p, then either a or b (or both) is divisible by p. More on that after an aside on notation.

Mathematicians almost always use p when they need a variable to mean a prime number. To this point, I have used the variable n and explicitly specified when it was known to be prime. From here on out, I will probably never use n to signify a number that we are asserting must be prime. Additionally, I will not use the variable p to signify any number which we do not know to be prime. At the risk of beating a dead horse, I may use n to signify a number which turns out to be prime inadvertently. But, I would not use n to represent a number which we know from the start must be prime.

So, how can we prove the statement before that aside? Well, if a is divisible by p, then it's easy. Otherwise, gcd(p,a) = 1 because p only has divisors 1 and p. If the greatest common divisor of p and a were p, then a would have been divisible by p.

Okay, so if a is not divisible by p, then we know that gcd(p,a) = 1. If that's the case, then we can use Euclid's Lemma to show that b must be divisible by p.

This may sound blazingly simple. It may feel entirely obvious to you that you cannot multiply together two numbers which aren't divisibly by p and come out with a number that is divisible by p. But, it really is a special feature of prime numbers. If you consider trying to do the same thing with n = 6 in place of the prime p, then you would find that 90 = 9 * 10 is divisible by 6, but neither 9 nor 10 are divisible by 6. So, this result isn't so trivial as it may feel.

The Infinitude of Primes

Euclid proved that there had to be infinitely many prime numbers. If we assume that there are only n prime numbers p₁, p₂, ..., p_n, then we can form a new number a = p₁ * p₂ * ... * p_n + 1. Either the new number a is divisible by one of the primes that we already know or our list is incomplete.

It is easy to see that for any of the primes in the list p_i, that a == 1  (mod p_i). Thus, a is not divisible by any of the primes that we already know. So, our list is incomplete.

But, if we added a new prime to our list to accomodate this a, then we could repeat the process again with the new list. No finite list will ever contain all of the primes. Lather. Rinse. Repeat.

Thus, we've shown that it's invalid to assume that the list is finite. So, we've proven that the full list of primes must be infinite.

The Fundamental Theorem of Arithmetic

It's likely that you already know the Fundamental Theorem of Arithmetic. If you think you don't know it, chances are that you do know it---you just don't know that's what it's called. As you can guess from the name, this theorem states a very basic fact about numbers (integers greater than one, to be specific). This will probably also seem fairly trivial. Please, bear with it.

The Fundamental Theorem of Arithmetic

For any integer greater than 1, one can express that number as a product of prime numbers. That expression is unique apart from the order of the factors.

Another way to put that is that for any integer n which is greater than 1, that number can be written in only one way as: n = p₁^^e₁ * p₂^^e₂ * ... * p_k^^e_k where each of the p_i are prime numbers, the e_i are positive integers, and p_i < p_[i+1] for all i from 1 through k-1.

You should convince yourself that those two say the same thing. We're going to prove the latter, slightly uglier version.

This proof follows Jones.

We're going to do a proof by induction here. Proof by induction is, year-in and year-out, a tricky concept to get the hang of. For this proof, we're going to be using the principle of strong induction. One uses it as follows:

1. One establishes that at least one case is true
2. Then, one assumes that it is true for all cases less than the current case and then shows that it must be true for the current case.

In doing this, then what happens is that the first case was proven explicitly. Then, the second case must be true because all of the cases less than the second case are true. Then, the third case must be true because all of the cases less than the third case are true. Lather. Rinse. Repeat. Every (finite) case must be true.

We're going to use this strong induction principle to show that it is possible to write numbers in the proper form. After that, we'll show that the representation is unique.

Proper form

Our first case is going to be n = 2. Since 2 is prime, it is easy to write it in the proper form: 2 = 2^¹. That takes care of step one for our strong-induction proof.

Now, if we assume that n > 2 and that we can write every number that is greater than one but less than n as a product of prime numbers in this way, we have to show that this means that n can be written as the product of primes in this way.

If n is prime, then n = n^¹ fulfills our need.

If, on the other hand, n is composite, then we can find a and b which are both greater than one such that n = a * b. Since they are both strictly between one and n, then we have assumed that they have prime factorizations of the form we are looking for. If we substitute those in for a and b, collect like terms, and sort the primes by size, then we have a prime factorization of n which satisfies our requirements.

Uniqueness

Assume that n = p₁^^e₁ * p₂^^e₂ * ... * p_k^^e_k and n = q₁^^f₁ * q₂^^f₂ * ... * q_l^^f_l are two factorizations of n.

It is clear from the first factorization that n is divisible by p₁. And, from the section above about divisibility, it is clear that there is some q_i which is divisible by p₁. Move that one to the front of the list so that it gets called q₁. Since q₁ is prime, we know that p₁ = q₁ (because p₁ is not one and the only factors of the prime q₁ are one and q₁).

Now, we divide both factorizations by p₁ (which is equal to q₁) and we are left with: p₁^^(e₁-1) * p₂^^e₂ * ... * p_k^^e_k for the first one and q₁^^(f₁-1) * q₂^^f₂ * ... * q_l^^f_l. And, we lather, rinse, and repeat.

The only concern to deal with is whether any e_i may reach zero before the corresponding f_i or whether there could be more factors one side than the other. I'm not going to go into this full-bore here. I'll just mention that if either of those cases happened, then there would be some number that was a divisor of one side which wasn't a divisor of the other side. Since the two sides are equal, that won't happen.

Problems

There aren't any problems for this week. I suppose you could calculate the prime factorization of a few numbers if you like. Let's say 1066 and 2001.

Next Lesson

In the next lesson, we'll get to how one recognizes when something is prime. And, if space-time permits, we will do some RSA encryption with the stuff we've learned.