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.
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 p1, p2, ..., pn, then we can form a new number a = p1 * p2 * ... * pn + 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 pi, that a == 1 (mod pi). 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.
This proof follows Jones.
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.
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.