Monday Math: So What Is a Prime?
Jan. 28th, 2013 06:51 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowLast time, I explained that the biggest reason why 1 isn't a prime is the Fundamental Theorem of Arithmetic. This time, I want to go over the proof of the FTA, and point out some subtleties.
The FTA really comes in two pieces: first, that every positive integer can be written as a product of primes, and second, that except for ordering, this representation is unique. Let's start with the first one. Suppose you have a positive integer. If it's 1, we're done; it's the product of the empty list of primes, {}. If it's a prime p, again we're done; it's the product of the singleton list {p}. So suppose it's a composite, n. Since it's composite, it can be written as a product of smaller numbers: n=rs. If r and s are both primes, you're done. If one or the other is composite, you can break it down further. Keep at it; each time, the numbers involved are smaller, and this can't go on forever. But it can only stop when all of the factors are primes.
(Note that this argument depends crucially on the "can't go on forever" bit. If it weren't for this - which is essentially the Well-Ordering Principle - the proof wouldn't work.)
Now for the second part. Suppose that the product of the list of primes {p1,p2,...} equals the product of the list {q1,q2,...}. Then, in particular, p1 divides the product of the q-list. But primes have another useful property: if a prime divides a product, it divides one of the factors. So p1 had to divide one of the qs; but since the qs are prime, this implies that p1 is actually one of the qs. OK; pull it out of both lists, and repeat as necessary. At the end, all of the ps must be qs, and vice versa; the two lists are the same, except perhaps for ordering.
We've used two different properties of primes here. The first is that a prime can't be factored into smaller numbers; the second is that if a prime divides a product, it must divide one of the factors. But these are, indeed, different properties, and there's no a priori reason for them to go together. In fact, if we weren't talking about the positive integers - if we were dealing with some other number system - they wouldn't necessarily go together. That will be our next topic: defining "number system", and exploring the different things that can happen.
The FTA really comes in two pieces: first, that every positive integer can be written as a product of primes, and second, that except for ordering, this representation is unique. Let's start with the first one. Suppose you have a positive integer. If it's 1, we're done; it's the product of the empty list of primes, {}. If it's a prime p, again we're done; it's the product of the singleton list {p}. So suppose it's a composite, n. Since it's composite, it can be written as a product of smaller numbers: n=rs. If r and s are both primes, you're done. If one or the other is composite, you can break it down further. Keep at it; each time, the numbers involved are smaller, and this can't go on forever. But it can only stop when all of the factors are primes.
(Note that this argument depends crucially on the "can't go on forever" bit. If it weren't for this - which is essentially the Well-Ordering Principle - the proof wouldn't work.)
Now for the second part. Suppose that the product of the list of primes {p1,p2,...} equals the product of the list {q1,q2,...}. Then, in particular, p1 divides the product of the q-list. But primes have another useful property: if a prime divides a product, it divides one of the factors. So p1 had to divide one of the qs; but since the qs are prime, this implies that p1 is actually one of the qs. OK; pull it out of both lists, and repeat as necessary. At the end, all of the ps must be qs, and vice versa; the two lists are the same, except perhaps for ordering.
We've used two different properties of primes here. The first is that a prime can't be factored into smaller numbers; the second is that if a prime divides a product, it must divide one of the factors. But these are, indeed, different properties, and there's no a priori reason for them to go together. In fact, if we weren't talking about the positive integers - if we were dealing with some other number system - they wouldn't necessarily go together. That will be our next topic: defining "number system", and exploring the different things that can happen.
