So this is a reminder slide. So I spoke about this,
I believe in the week 4 video, the Fundamental Theorem of Arithmetic,
but I'd like to revisit it at this point.
“Suppose that n greater than 1 is an integer,
then n can be factored uniquely as a product of prime numbers
up to reordering up the prime numbers.”
UFT, as the acronym is, is for Unique Factorization Theorem.
Hopefully this will get changed to fundamental - or FTA1.
You'll see why the FTA1 is useful, FTA 2 is going to come later,
but this is the acronym that we're using at this moment. We'll probably change it later.
Okay so suppose that n greater than 1 is an integer, then it can be factored uniquely.
So every number has some prime factorization,
as long as the number’s bigger than 1. That's the summary of this.
This is something you probably already knew before. The proof is pretty tricky, as you noticed,
it's very complicated, but…
it's useful. It's very useful.
And it's good to do, it's good practice. It's good to do a couple of things that are hard.
Now let's talk about the uses of this, so why do I care about this?
Well one thing that we can do
is we can now take a number
and factor it into its prime factorization.
Why is that important? Well we have a couple of theorems now,
talking about divisors and greatest common divisors,
that come from the prime factorization of a number.
So here I said let n be
equal to this prime factorization.
Now I mentioned…
so in the notes, you can actually see a couple
of ways to write out a prime factorization.
This is the one I'm choosing for this problem.
So I'm going to write n as the product
of distinct prime numbers: p sub i
to the power of alpha sub i, where alpha sub i - these are integers
and they're going to be greater than or equal to 1.
So every prime factor, every prime that appears in this product,
has to appear in the prime factorization of n,
and there's also this k. So the k value is just your stop index.
So you have k prime factors
and they’re raised to certain powers, okay?
So for example, 12 is equal to 2 squared, times 3, right?
There would be an example of a prime factorization in this form, right?
Then d can be.. then d is a positive divisor of n
if and only if a prime factorization of d can be given by the following:
so d is equal to this product.
We're now... we have
the same primes, but now they’re to the power of delta i,
and these delta i’s are bounded between 0 and alpha i.
So notice here that the deltas can be 0.
So some prime factors that appear in n might not appear in the divisor of n.
And this has to hold and this range of this bound has to hold for every i.
So let's just see an example, so positive divisors of 63.
So 63 is 3 squared, times 7, 9 times 7.
The positive divisors are given by what?
They're given by 3 to the 0, times 7 to the 0,
so I take no 3’s and no 7’s,
or I take no 3’s and one 7,
or I take one 3 and no 7’s,
or I take one 3 and one 7, and so on and so forth.
And if I summarize this list, or if I actually simplify this list,
I get 1, 7, 3, 21, 9, and 63.
So again what is this saying? So this is saying
positive divisors from a number can be given by the prime factorization by taking
subsets of the total number of primes that we have.
Just like as follows.
The proof of this
is technical, we didn't do it in class and I believe it's not done in the notes.
Maybe it is done in the notes I don't actually know.
I didn't do it in my class
It's just technical to make the symbols work out,
and this is something that we kind of already believe
before this course started, so I don't think the
proof is going to add a lot to our understanding.
This is Divisors From Prime Factorization,
and once we now have what kind of divisors…
can occur - by the way I've just noticed a typo:
“Divisors Form Prime Factorization” should be “Divisors From Prime Factorization.”
But anyways, now that we know
the type of divisors that can come
from a prime factorization, what we can do is we
can now determine when we have the greatest common divisor
from prime factorization.
And that's what the next theorem says.
So “Suppose we have two integers written in their prime factorizations…”
and notice that these two integers, all we require is that they are...
positive.
When we allow for the 0 exponents, then we can actually get the number 1
by just taking all 0’s as the exponents, okay?
So this type of prime factorization gives us a way to write
every single number in terms of prime factors.
Notice also that we have two different numbers but we've used the same
prime factors. How can we do that?
And the way to do that is to actually just allow for 0 exponents.
So for example I'm going to write 14 and 15 using the same prime divisors.
Well 14 is 2 to the 1, times 3 to the 0, times 5 to the 0, times 7 to the 1,
and 15 is 2 to the 0, times 3 to the 1, times 5 to the 1, times 7 to the 0.
So there I’ve used the primes 2, 3, 5, and 7
to write those two numbers in their prime factorization.
So don't let the notation fool you,
don't let the k’s fool you. They can have 0 - like
some of the primes might not contribute to a and b.
So again so “…if a and b are written in the prime factorizations,
then the gcd of a and b is this product,
where the only thing that we have to define is this m i,
and m i is the minimum of alpha i and beta i”.
So a prime factorization so…
again we knew from the previous theorem what
the divisors of a and b are,
so the greatest common divisor involves the largest possible exponent
in the common divisors, and that value is going to be given by the minimum
of the primes appearing in a and b.
So let's just see a concrete example. Again this
is a lot of abstract notation, but the idea is actually pretty simple.
So here we have the gcd of 20,000 and 30,000
so that's the gcd of 2 to the 5, times 3 to the 0, times 5 to the 4.
And the other number is 2 to the 4, times 3 to the 1, times 5 to the 4,
so how do I get this prime factorization? Well
I know that 10,000 divides both of these numbers, and
10,000 is 2 to the 4, times 5 to the 4,
so it's actually not too hard to factor these.
Sometimes factoring is really difficult though. Actually, in general, factoring is very difficult.
But here it's easy, when we have these nice forms we can factor no problem.
And now what do we do? Well we're going to use our GCDPF that's
the equal sign…
that's the second equal sign here.
What do we get? So we take the minimum of the powers of 2,
so we have the minimum of 4 and 5
we take the minimum of the powers of 3, so minimum of 0 and 1,
and the minimum of the powers of 4, the minimum of 4 and 4.
So this term is going to go away, because it's 3 to the 0.
This term becomes 2 to the 4, and this term becomes 5 to the 4.
Simplifying that becomes 10,000.
And that's it for GCDPF.
You do this computation, and this is the result that you're going to get in the end.
I think it's a very powerful result, but you have to be careful when using it,
which is what the next slide is going to talk about.