Hello everyone. Welcome to week 5 of Carmen's Core Concepts. My name is Carmen Bruni,
and this week we're going to talk about Math 135 week 5.
This had a lot to do with greatest common divisors.
There were a couple of other topics scattered about,
but that's the main topic of this week.
Again I just want to remind everyone that this isn't meant to replace lectures.
And if you use these in lieu of lectures, you're
probably not going to get as much
out of the course as you would have you've done both.
The idea behind these videos is to give you some sort of
spaced repetition where you go to the lectures during the week,
and then maybe later on you go back and you review them.
And that should help you reinforce your learning about these concepts.
Okay so Euclid’s Theorem, this is one of my favorite theorems in mathematics.
“There exists infinitely many primes.”
The reason why I like it, it's very simple and it's just very creative.
It's a cool little argument that we're going to talk about briefly here.
This isn't a full sketch, but
the idea is that you argue by contradiction.
It's tough to say that there exists infinitely many primes,
but it's easier to argue that if you have finitely many,
you can't have… you reach a contradiction.
So...
beginning with that, we
start with finitely many primes, let’s call them the p1 to p n…
p little n
And then we're going to create the following number.
We're going to create capital N is equal to 1 plus the
product of all the finitely many primes, okay?
Now why can we do this topic now? Well
we talked earlier about the Fundamental Theorem of Arithmetic;
Unique Factorization, right? So N can be factored
uniquely as a product of primes.
So that means that one of these primes
must divide N, at least one of them.
One of the primes must also divide this product.
That's also by
Euclid’s Lemma, or the Generalized Euclid’s Lemma.
So we have that a prime divides N and a prime divides this product,
so it must divide the difference. Well the difference is 1,
by Divisibility of Integer Combinations, and that's a contradiction.
Again these are - this is just shorthand. This is just a
very brief sketch, right? You shouldn't write
p divides something equals something else.
You should write p divides this and hence p divides 1,
but for a proof sketch I'm just going to write the shorthand.
Okay so that's the idea. I think this is a cool little proof. It
doesn't require too much heavy duty mathematics.
The Fundamental Theorem of Arithmetic is used,
some sort of unique factorization thing, but
again it's not too too bad.
I like this argument. I think it's one of these
arguments that every math major should know.
Greatest common divisor.
So this is something that we spent a lot of the week talking about. So let's just
go over the definition again:
“The greatest common divisor of integers a and b
with a or b not 0…” so one of these has to be not 0
in order to use this definition,
‘…it's an integer d such that
d is a common divisor of a and b,”
that's condition 1: d divides a and d divides b,
and condition 2 is “if I have another common divisor of a and b [call it c],
then I know that c must be less than or equal to d.”
That's the greatest condition of a greatest common divisor.
So the greatest common divisor is a common divisor,
and it is the largest such common divisor.
The maximal such.
We write d equals the gcd of a and b, so that's how we denote it.
Some examples: so the gcd of 120 and 84, that was one
we saw in class, this is equal to 12.
Again 12 divides 120 and 12 divides
84, happens to be the largest such number that has that property.
gcd of 0 and 0, we define that to be 0.
It just works out a lot easier in many proofs.
Works out a lot easier in many ways, so
we just define the gcd of 0 and 0 to be 0.
gcd of a and b is equal to the gcd of b and a.
That holds in all cases. I'll leave that as an exercise.
gcd of a and a is equal to the absolute value of a. Don't forget that
a can be negative,
so it's important to use the absolute values here and same as the gcd of a and 0.
The last thing, the gcd, the greatest common divisor,
of a and b exists and is unique.
Perhaps not surprising. There's only one greatest common divisor,
and it does exist.
I mean, we know that it's bounded between 1…
so 1 is a common divisor of a and b, and the biggest
the common divisor could be is the minimum of the absolute value of a and b.
So that proves that it exists and it’s unique.
That's all I want to say about the greatest common divisor definition.
Well maybe I'll say one last thing
there are other definitions of the greatest common divisor.
This is the one that we used in in our notes and that's the one that we used in class.
So let's start our theorem...
montage? I guess.
So gcd with remainder is our first one.
“If a, b, q, r are elements of the integers
and a equals b q plus r, then the gcd of a and b is equal that the gcd of b and r.”
So something to be careful of
when you're going through these proofs;
you always want to make sure you watch the “a equals b equals 0” case.
Sometimes it'll fall through with your proof
and sometimes it won’t. You have to isolate that case
I believe this one just falls through. You can
double check this as you're reading this
or as you're listening to this.
For the proof, whenever you're trying to prove something about a gcd
equalling some other object,
it's usually easier, I find it easier,
to write, “let d equal the gcd of a and b
and let e equal the gcd of b and r”
and then I'm arguing about d and e.
I just find it easier to argue like this. I don't have to write
the letters gcd a b everywhere.
It just makes it easier.
The general proof technique when you're using the definition of the
greatest common divisor, it's usually good to show something - well in this case -
that d is less than or equal to e, and e is less than or equal to d.
Just turns out to be easier that way,
and then because of that, we know they must be equal.
So how do we go?
So with this, we're going to start by showing
that d is less than or equal to e, and e is less than or equal to d.
So what connects a, b, and r? Well
a equals b q plus r. So that's the thing that we're going to have to use a lot.
That's the only thing we're really given.
So since a equals b q plus r,
and we know that d is the greatest common divisor of a and b,
so it is a common divisor of a and b.
Thus by DIC, Divisibility of Integer Combinations,
we have that d divides
a plus b minus q.
But a minus b q that's just r. So hence, d divides r.
So d divides b and d divides r,
so by the maximality of e,
so e is the greatest common divisor
of b and r, we see that d must be less than or equal to e.
Alright, now in reverse, it's the same sort of idea.
e divides b and e divides r, so
once again, by DIC, e divides b q plus r,
so b times q plus r, and that's just a,
so therefore e divides a.
Since d is the largest common divisor of a and b, we see that e is less than or equal to d
and hence d equals e.
So again, this is a very typical argument
of what you would do if you're trying to argue by the definition of gcd.
Arguing by this definition usually works...
probably I can almost say “always” here and be very safe.
You can always go back to the definition, but it usually helps to use the tools
that we've given you in this course to help prove different or new theorems.
Just know that it is possible to go straight back to the definition.
Oh…I guess I kind of spoiled it,
but what can we use GCDWR for?
Remember I said it was kind of like…actually let me go back…
I said it was kind of like a division algorithm
statement.
a equals b q plus r. This looks like the division algorithm,
right, except we don't have any restriction on r.
Usually we bound r.
But here we don't have that restriction. r can be positive, negative,
it can be very big, it can be very small.
Again it turns out that
if we use this in sort of the context of the division algorithm, we actually can
get this algorithm called the Euclidean Algorithm,
which helps us to compute the greatest common divisor of very large numbers
very, very quickly.
So that's what we're going to talk about next.
Again, this is the heart of the Euclidean Algorithm.
So let's see an example of the Euclidean Algorithm here.
So compute the greatest common divisor of 1239 and 735, okay?
So the idea here is repeated use of gcd with remainders.
So 1239 is equal to 735
times 1 plus 504.
That's basically the division algorithm,
but on the right hand side, this is gcd with remainders,
so the greatest common divisor of 1239 and 735,
think of this as my a and think of this as my b,
is the same as the gcd of b, 735,
and r, 504.
So with that, you can kind of see oh okay well we've gotten from
a 4 digit number and a 3 digit number…
the greatest common divisor of a 4 digit number and a 3 digit number
to the greatest common divisor of a 3 digit number and a 3 digit number.
So we're slowly getting smaller and each of these numbers
is strictly less than the previous examples,
and we can keep going through this, okay?
So now…there's a little typo here. This should be 735, this shouldn't be 725.
So 735 is equal to 504 times 1, plus 231.
So again what do we get? We get the gcd of 735 and 504 is equal to the gcd of 504 and 231,
and then again we do it again. So the idea is that this number goes here,
and this number goes here, and then we repeat.
This number goes here, and this 231 goes here,
and we keep going through this with the division algorithm,
and we see by doing this, our numbers are getting smaller and smaller
and smaller and eventually we're going hit the gcd of 21 and 0.
So eventually 0 will appear. I'll leave that as something to think about.
Why does 0 have to always appear? That comes from the division algorithm though.
When we get to there, we know what the gcd is, right? It's just the non-zero number,
which is 21. That was on the previous slide.
And that's basically the Euclidean Algorithm.
Now the second part of the Euclidean Algorithm
that we talked about was back substitution.
Now back substitution answers this other question.
So this slide’s very, very hectic but
it's okay.
So one question that we might want to know the answer to, and we'll see why in a little bit,
this actually helps us to prove Euclid's Lemma,
we might want to find x and y such that 1239, 735…
or so 100… oh sorry,
we might want to find x and y integers such that 1239x plus 735y is
equal to the greatest common divisor of 1239 and 735.
So from before, this is just the previous slide.
The content on the left.
And on the right, what we're going to do is we're going to start with the 21,
so that's the greatest common divisor that we figured out,
and what we're going to do is we're going to back substitute. So
we're going to keep isolating for the remainders,
and substituting those in to the previous steps, okay?
So step one is just isolate the remainder, that's easy,
and step two now is okay well we have this 42 here, and 42 was the previous remainder,
so we're going to isolate for the previous remainder: so we get
42 is equal to 504 times 1,
plus 231 times negative 2,
and we're going to substitute that in.
And then we're going to keep going, okay?
Let's take a look at this step. So 42 is equal to that, that we said from before,
now I'm going to take the minus 5 and distribute it in,
so I'll do that once very slowly, so 231 times 1 that comes down
plus 504 times 1, times negative 5, that's 504 times negative 5.
231 times negative 2, times negative 5, that's going to be 10, right?
This is going to distribute, so the negative 5 distributes to that term in the bracket,
and the negative 5 distributes to that term in the bracket. That's what's happening there.
Adding, so 1 plus 10 is 11, so I have 11 versions of 231,
and I have negative 5 versions of 504.
Now again I do the same argument with 231. So
isolate for 231, substitute that in.
Then I take the 11 and bring it into each term,
and then I'm going to add it to the 504 times negative 5, so I'm going to get
11 copies of 735, and
negative 11 minus 5 negative 16 copies of 504.
Then with the 504, I'm going to do it again. I’m going
to isolate my remainder in step one,
plug it in, simplify, and I get the following equation.
Something to mention here is that your textbook also
refers to this as a Certificate of Correctness.
So on every step, you can actually make sure that
you're doing the computations correctly, right? There's no reason to get this computation wrong.
At any step you can check your answer by just multiplying it out,
making sure that I always get 21.
And if you don't then you made a mistake.
So this is a good way to double check your answer
when you're doing your homework.