The last thing I want to talk about this week is the Fundamental Theorem of Arithmetic.
So I always joke with students and I say
you know, “If something is called the Fundamental Theorem of something,
you know insert subject name here,
you should probably know it. You should probably know it inside out, you should
know it frontwards, backwards,
in different languages, you should just know the theorem, okay?”
It's probably important.
So what do we need to do this? So we want to prove the Fundamental Theorem of Arithmetic,
which we'll get to in the next slide, but before we do that
we’re going to need a couple of tools that we don't have yet,
so we're going to assume these for granted and
in the following week, we'll talk about the proofs of these things.
So the first thing is called -
the first thing that we’ll need is Euclid's Lemma,
and in our notes we call it Primes and Divisibility,
for now. I'm hoping just to get this changed to Euclid's Lemma.
This is the name of the theorem in general,
but in this course we've called it Primes and Divisibility and we use the acronym, PAD.
So let a and b be integers and let p be a prime number.
If p divides a product, then p must divide
one of the two terms in the product.
This seems really obvious. If like
7 divides, you know, 14 times 20,
then 7 must divide 14 or 7 must divide 20.
It feels really obvious, but it's actually not
completely trivial to prove.
There's actually a little bit of thought that has to go into this proof.
But we'll see that next week.
This actually will follow quite nicely from our work
with greatest common divisor, which is where we're going.
Our goal is to prove this basically next week.
And a corollary from this, and this is actually in the
January 2016 term we actually will get
you to prove this; this Generalized Euclid’s Lemma,
so if I have
a bunch of integers, so a1, a2, all the way up to a n
and some prime number p,
then if p divides the product of these numbers,
then p must divide one of the terms
for some i between 1 and n.
It could divide more than one term, but it must divide at least one.
It turns out this Generalized Euclid’s Lemma is really what we're going to need.
This follows quite nicely from Euclid's Lemma and I won't say anything more
other than this because you'll have to -
well because at least in one class we’ll prove it,
but...
that's it.
So let's go through these. So with these tools,
again, so the Generalized Euclid’s Lemma just keep in your mind,
if a prime divides a product, then it must divide one of the things in the product.
That's all it says.
So if p divides… so
p is let's say 3 and it divides 4 times 9, times 16,
then 3 must divide one of 4, 9, or, 16.
Possibly more than one. In the case of 2, 2 divides 4 and 16.
But it must divide at least one.
Fundamental Theorem of Arithmetic, what is it?
Here it is.
Sometimes it's called Unique Factorization Theorem.
So that's why we use the abbreviation UFT.
We’ll see that FTA will be reserved
for another fundamental theorem later in the course.
So what does UFT say? What does the Fundamental Theorem of Arithmetic say?
Every… bad pluralization here…
every integer n greater than 1, can be factored uniquely
into a product of primes, so product of prime numbers.
Every number can be factored into primes.
And I say uniquely here, I actually don't mean uniquely.
I mean uniquely up to reordering of the primes.
So I should be a little bit careful here, I'll update that
in the PDF.
So every integer - and I'll fix the typo - every integer n greater than 1
can be factored uniquely into a product of prime numbers
up to reordering of the primes.
So for example, if I have the number 6,
right, I can write that as 2 times 3, or I can write that as 3 times 2.
Those really aren't different. I mean
those should be the same thing, you shouldn't count that twice.
So up to that reordering,
6 can be uniquely factored as 2 times 3. The prime numbers 2 and 3.
By convention - so something else to mention -
by convention, primes are just said to be a single element product.
This is really just a technicality.
You could include every integer n greater than 1 is either prime, or can be factored uniquely
into a product of primes up to reordering, that's fine too.
This is just usually the way it's stated, so I'm going to leave it as so.
Okay.
So again, what's the idea behind this? So if you factor a number…
so I always use this analogy, if you factor a number in
Canada, and your buddy in Australia factors a number,
you should have them put the same factorization into primes,
up to reordering of the primes.
Let's see the proof.
So existence.
Before I go through this proof,
existence: you can prove this by the Well Ordering Principle or by Mathematical Induction.
If you've seen one way in class, I suggest you should pause the video
and try using the other principle. Challenge yourself,
see if you can actually do this.
But for now, let's just talk about the proof existence and uniqueness.
So assume towards a contradiction that not all numbers
can be factored into a product of primes.
So there's going to be some number, some numbers,
that cannot be factored into a product of primes.
So the set of all numbers that can't be factored into primes is non empty.
Well because it's non empty, well by the Well Ordering Principle,
there must be a smallest such number.
I'm going to call that number n.
Then either n is prime, and that's a contradiction, right?
Again, we said primes are just
single element prime factorizations, that's fine.
Well what's the alternative? Or n is composite,
and we're going to write n is equal to a times b,
where both a and b are strictly between 1 and n.
So what does that mean? Well by the minimality of n,
both of a and b must be able
to be factored as product of primes.
They're less than n, bigger than 1,
so they satisfy that the statement, or the hypothesis of the
Fundamental Theorem of Arithmetic.
So I must be able to factor them into a product of primes.
So if I can factor a and b as a product of primes, then n, which is
the product of a and b, must also be
able to be factored into a product of primes.
But that doesn't make sense because we said that n couldn't be factored
into a product of primes, and that's a contradiction.
So hence, every number can be factored into a product of prime numbers.
So that's part one.
I mentioned nothing about the uniqueness here though.
So how do we deal with uniqueness?
And that can be done as follows.
So here I'm going to do an informal proof of uniqueness.
In class I decided to do a formal proof
and after some pondering I thought, "Well maybe I should do the informal proof
in class now. Maybe save the formal proof for later."
That being said, let's take a look at an informal proof
of how this works. I feel like you're going to get an idea of how
the uniqueness part of the Fundamental Theorem of Arithmetic really works.
So we're going to suppose that n can be factored in
two distinct ways. So it,
you know, it could have been…
it could have been more.
Maybe I shouldn't even use the word distinct. Maybe I should say suppose
n can be factored in two ways. okay?
And I'm going to prove that they’re the same. That's what's going to happen.
So let's write n as a product of
primes p1 up to p k, and as primes q1 up to q m.
Again, all these numbers are prime. I don't know if k equals m.
I'll try to figure that out as I go through this.
But that's the idea here, okay?
So suppose that I have a number that can be
factored in two ways.
Now let's look at the first prime p1.
Well p1 divides this product,
and this product is equal to the product of primes from q1 up to q m.
So by the Generalized Euclid's Lemma
or Generalized Primes and Divisibility, however you want to call it,
what do we know? Well p1 divides a product of things,
so p1 must divide some element in that product.
So p1 divides some q j.
“By reordering if necessary,” so what do I mean by this? Well
q j is just some arbitrary element in this product, right?
So let's say q j was something like, I don't know, the tenth term, right?
Well...
I'm going to move that q j to the first term,
I'm going to move q 1 over to where q j was.
So what am I doing? I’m basically renaming things.
So q j was once called Tom, now I'm going to call him Harry, okay?
That's basically what's happening here. So
I can assume without loss of generality that
p1 must divide q1
because if it wasn’t, then just move the terms around, right, reordering.
That's the reordering part of the uniqueness, right?
So remember they're unique up to reordering. So if
it wasn't the first term, then just reorder it so that it was the first term.
Now dividing by p1, we can reduce
the number of primes on both sides. We can go from p2 to p k and q2 up to q m.
Now hopefully after seeing this, you can say, “Oh okay,
well I can just keep doing this,”
and the idea is yes that's the idea behind
the uniqueness proof of the Fundamental Theorem of Arithmetic,
just keep repeating this argument until you match up all the primes.
By the end we'll know that k must equal m,
and that each prime is equal to each other up to reordering.
We might have to keep shuffling the primes, but that's okay.
And that's the idea behind the Fundamental Theorem of Arithmetic.
So again, it's really important… it's a really…
it's just a useful result,
that numbers can be factored into primes.
We'll see some applications next week and throughout the course we'll see
applications of the Fundamental Theorem of Arithmetic pop up.
But that's the main idea.
So where are we going now in the course?
Maybe we'll give you a little bit of a spoiler alert,
so next week we're going to talk about gcd’s.
We're going to kind of enter the number theory part. So this is more of the
proof basics part, first 16 lectures of this course,
and then from here on out, we're going to actually
use this in the context of number theory.
And our goal in number theory will be to head towards
RSA encryption,
so kind of how we communicate with banks online and other industries,
and then from there, we'll go into complex
numbers and talk about the algebraic properties of complex numbers.
That's it, I think that's all I really have to say.
Again induction was the main
topic of this week, so focus on that.
That's also, for the January...
well so for the winter 2016 offering,
that was also our “midterm line”: induction. So
we don't need to know the Fundamental Theorem of Arithmetic for our midterm,
but you do need to know up to
induction and including induction.
So thank you for your time, hopefully this helps you and best of luck.