I'll explain the significance of the theorem, and hopefully that will give you a better idea of what it means and why it's useful.
In basic number theory we tend to use facts which we learn to intuitively accept without proof such as every positive integer being uniquely factorised into prime factors i.e. 15 = 3*5. But being particular as they are, mathematicians require that this be proved. To prove such a result one naturally asks the question, under what assumptions? What can I assume is true about the integers which I can use without proof to derive results such as this.
The key property of the integers which we assume without proof is that any non-empty subset of the positive integers, (such as {5, 100} or {x such that x is a prime number}), has a smallest element in it (5 and 2 respectively). And naturally we give it a hopefully suggestive name:
The Well Ordering Property - Every non-empty subset of the positive integers has a smallest element.
This property seems very obvious right? What isn't quite obvious is how we derive so much using such a simple axiom! But lo and behold this statement is logically equivalent to mathematical induction, meaning they imply each other, I'll leave this as an exercise. So now we have induction too, great!
Divisibility is easily defined, 20 is divisible by 2 because there's an integer which when multiplied by 2 gives 20, with the appropriate generalisation. Primes are also easily defined as positive integers divisible only by 1 and itself, and noting that we normally exclude 1 from being a prime.
Now what we want to do is show that we can factorise any positive integer into primes. If you think about how we normally factor an integer a natural idea which may occur to you is that we can start off with an integer n > 1, if it's prime then we're done, we've written it as a product of primes, otherwise we can write n = pq, with p,q > 1, and furthermore since both p and q are smaller than n we can use an inductive argument to show that each of them can be written as a product of primes, then n = pq can be written as a product of primes. (We can think of 1 as a product of primes, namely as the empty product to get the induction started).
We have the result that a positive integer can be written as a product of primes, but there's a subtlety, how do we know that 15 = 3 * 5 and that the only way to write 15 as a product of primes is as 3*5? In other words, how do we know that the factorisation is unique! How do we go about doing this? Well if 15 = 3 * 5 = p1 * p2 * ... * pn for some primes p1.., then we want to conclude that one of those is a 3, say p1 = 3, then we could divide off by 3 and get 5 = p2 * ... * pn, and we can repeat the same argument to show that one of these primes say p2 must be equal to 5, and dividing off by 5 gives 1 = p3*...*pn, from which we conclude that n must've been 2, and so this statement is really 1 = 1. Then we'd have shown that p1 = 3 and p2 = 5, and so the factorisation was really the same!
But I've been a little sly, because I didn't say how I concluded that some pm, say p1, must be equal to 3. This is in fact the key step to proving unique factorisation, and it is named after Euclid.
Euclid's Lemma: if a prime p divides a*b, then p divides a or p divides b. This is where your result comes in, in order to prove Euclid's lemma we first prove a very very useful result called
Bezout's identity: there exists integers x and y such that ax + by = gcd(a, b), with gcd(a,b) denoting the greatest common divisor of a and b. It's not obvious why this is useful, or how this might be useful, and unfortunately I don't have the time to motivate it (I'm supposed to be studying for an exam I have tomorrow morning). I'm assuming you read the proof of Bezout's identity, the key step being the well ordering theorem (which can be used to prove the
division algorithm with remainder which we all know from grade 3).
Once we have Bezout's identity we're ready to prove Euclid's lemma, which as a reminder states that if a prime p divides ab then p divides a or p divides b. Proof:
If p divides a then we're done! So assume that p doesn't divide a, so that gcd(p, a) = 1, then by Bezout's identity we have ax + py = 1 for some integers x and y. Multiplying both sides by b, gives abx + pby = b, but we know that p divides ab, so that ab = k*p, for some integer k which we can substitute into our equation, giving kpx + pby = b, or p(kx + by) = b, which shows that p must divide b and we're done! This completes our proof of Euclid's lemma and hence our proof of unique factorisation. So we have proved the
Fundamental Theorem of Arithmetic that each positive integer can be written uniquely as a product of primes.
(Sorry the ending is kind of not motivated very well, I'm kinda strapped for time atm, also apologise for any typos/errors).
Home
Help
Search
Login
