The following content is
provided under a Creative
Commons license.
Your support will help
MIT OpenCourseWare
continue to offer high quality
educational resources for free.
To make a donation, or
view additional materials
from hundreds of MIT courses,
visit MIT OpenCourseWare
at ocw.mit.edu.
PROFESSOR: So
welcome to this week.
We are going to talk
about number theory.
Actually, before I
forget, there are
some handouts at the very back.
Please raise you hand if you
don't have any, then one of us
can actually come
over and hand you
out this sheet, which
contain some facts
about the visibility.
Thanks a lot.
And we will be using these
throughout the lecture.
So today we're going to
talk about number theory.
And this is a really different
way of thinking, actually.
But we will use
the same concepts
as you have learned before,
like induction, and invariance,
stuff like that, to
prove whole theorems.
So what is number theory?
Well, first of all,
it's a very old science.
One of the oldest
mathematical disciplines.
And only recently
it actually got
to have some more
practical applications.
So what this number theory--
it's actually the
study of the integers.
And what are the integers?
Well, these are the numbers
0, 1, 2 3, and so on.
So number theory got--
Oh, there's some more over here.
Another handout over there.
So number theory got used
actually in cryptography
only about 40 years ago.
And at the end of
the second lecture,
we will be talking about this
application into cryptography.
There are many application
in cryptography.
But we'll be talking
about one of them
to show you how useful
this actually is.
Now cryptography is the study
and practice of hiding numbers.
So you can imagine
how important that is.
We have like medical
data that we need
to store outside in the cloud.
Right?
So, gee.
Do we really want that?
We actually want to
hide our information.
We do not want
others who are not
allowed to see my private
information to see it.
So this art of
hiding information
is extremely important,
especially nowadays.
And number theory actually
will help us with this.
So number theory is something,
you'll be very surprised,
that can be used to save--
oops.
I have to put this on.
To save New York City in the
Die Hard number 3, I believe.
So let me start up again.
So let's see where it plays.
Maybe not.
[VIDEO PLAYBACK]
-Yeah, go ahead and grab it.
-You're the cop.
-Simon said you're supposed
to be helping with this.
-I'm helping.
-Well, when you going
to start helping?
-After you get the bomb.
Careful.
-You be careful.
-Don't open it.
-What?
I got to open it.
And it's going to be all right.
[BEEPING]
[ELECTRONIC CHIRPING]
Shit.
-Shit!
I told you not to open it.
[PHONE RINGING]
[PHONE RINGING]
-I thought you'd
see the message.
It has a proximity circuit,
so please don't run.
-Yeah, I got it.
We're not going to run.
How do we turn this thing off?
-On the front there
should be two jugs.
Do you see them?
A give gallon, and
a three gallon.
Fill on of the jugs with
exactly four gallons of water
and place it on the scale,
and the timer will stop.
You must be precise.
One ounce or lower less
will result in demolition.
If you're still alive in five
minutes, we'll speak again.
-Wait!
Wait a sec.
I don't get it.
You get it?
-No.
-Get the jugs.
Obviously, we can't fill
the three gallon jug will
four gallons of water, right?
-Obviously.
-I know.
There we go.
We fill the three gallon jug
exactly to the top, right?
-Uh-huh.
-OK.
Now we pour that three gallons
into the five gallon jugs,
giving us exactly 3 gallons
in the five gallon jug, right?
-Right.
Then what?
-Now, we take the
three gallon jug,
fill it a third of the way up--
-No, no.
He said be precise.
Exactly four gallons.
-Every cop in 50 miles
is running his ass off,
and I'm out here playing
kids games in a park.
-Hey.
You want to focus on
the problem at hand?
[END PLAYBACK]
[LAUGHING]
PROFESSOR: All right.
You can imagine what we are
going to do right here, right?
So.
You can imagine what's
below this table is a bomb.
[LAUGHING]
You guys have to save 6042.
[LAUGHING]
So we have the fountain here.
Each tennis ball is
one gallon of water.
We have a big jug, five
gallons and three gallons.
So you all got to
help me out here.
So who has an idea
of what we can do?
So.
AUDIENCE: [INAUDIBLE]
PROFESSOR: All right.
Let's first do that.
Fill up the three gallons.
AUDIENCE: And pout
it into the five.
PROFESSOR: Let's
pour it into five.
Maybe someone else can--
can continue.
Over there.
AUDIENCE: If we
do the same again,
we'll end up with just one
gallon in the three gallon.
PROFESSOR: Uh-huh.
So, let's do that.
Because that's true, right.
You can only fill it
up to five gallons.
So only, at more,
two gallons can add
to this, exactly two gallons.
And one gallon is left.
All right, next one.
You?
Would you like to--
AUDIENCE: Take out the five.
PROFESSOR: Take out the five.
All right.
And then what?
AUDIENCE: Pour the
one over there.
PROFESSOR: Pour
the one over here?
AUDIENCE: [INAUDIBLE]
AUDIENCE: Then fill
the three gallon,
and put it into the five.
PROFESSOR: All right.
That's great.
And I fill it up right here.
Fantastic.
So we actually have
four gallons here.
And luckily, they are safe.
Right?
So you say, thank god.
6042
So we can continue.
So this is actually
pretty amazing, though.
How can we get four gallon
out of three gallon jug,
and a five gallon jug?
And that's what we are
going to talk about in more
generality, actually.
And if you would just change
it a little bit, right?
Then things would get more
difficult. For example,
if you would change the five
gallon jug into a six gallon
jug, can we still
get four gallons?
No.
Why not?
AUDIENCE: [INAUDIBLE]
PROFESSOR: Everything has
to be multiples of three.
That's exactly right.
This is a multiple of 3.
1 times 3.
This is 2 times 3.
So if I do combinations
with those,
like pouring one into the
other completely, or emptying,
of filling up, we
always will have
a multiple of three gallons in
either one of those, or both.
So we can never
have four gallons.
So this is something
that we would like
to analyze a little bit more.
And to do that, we're
going to first a all
start with a definition.
Actually you can put up
the screen over here.
So let me take that out.
Can someone up there
pull up the screen?
Maybe not?
Maybe later.
All right.
So let's go with a definition.
We say n denote by m and a bar,
and a, we mean m defines a.
And how do you define this?
Well, we say that n
divides a, if and only
if there exists an
integer k, such that a can
be written as some multiple
m, mainly k times m.
So if you look at
this definition
we, for example, have
that 3 divides 6,
like what we just discussed.
There's something
interesting going on.
Suppose a is equal to 0.
Well, any integer will
define a, will define 0.
Why is that?
Because I can't take
k to be equal to 0,
so this is equal to 0
times any integer m.
So m defines 0 for all integers.
So this is kind of
the exception, right?
And we are going to use
this to set up a theorem,
and analyze this whole
situation over here.
Now in order to do that, we
will need to sort of define
what we can do with all this.
So there are states.
We will define a state machine.
We will see what kind
of possible transitions
we can have.
And once we have modeled
all this very precisely,
we can start proofing stuff.
Now let me first of all write
out what our assumptions are.
So suppose we have
an a gallon jug.
So in our case, a equals 3.
And we have also b gallon jug.
And in our case,
b equals 5, right?
And we issue that
a is at most b.
That is sort of the situation
that we are working with.
And he would like
to prove a theorem.
Exactly what we notice over
here, that three defines both.
The three gallon jug,
and the six gallon jug,
we would like to prove
something like this.
If m defines a, and
also m defines be,
well, then m should
define any results
that I can get with the pouring,
and emptying and filling
those jugs.
So this is the theorem,
if you'd like to prove.
And we can only do that
if you start to have
a proper model for this.
So let's go for that.
And--
And, well, the state machine
that we're going to use here
looks like this.
First of all, the
states that we have
are the number of gallons
that are in these two jugs.
So we will denote
those by pairs.
Pairs x, comma y.
And x denotes the number of
gallons in the a gallon jug.
The number of gallons m m that
we abbreviate as by the a jug,
and y is the number of
gallons in the b jug.
So these are the states.
And the start state it
exactly as it is right there.
We have nothing in
either of the jugs.
So that's the pair 0, comma 0.
So now we start to build up
some mathematics here, right?
So we express the state
of this whole situation
by a pair of number.
Now we need to find out
what they can do with it.
So what are the transitions?
The transitions are,
as we have seen, right?
We can just fill
one of the jugs.
We can empty those.
And the other
possibility is that we
can pour one jug over into the
other one as much as we can.
So let's write all of those out.
We can do emptying.
Well, how does that
change the state?
If we have x gallons
in this jug, and y--
and y gallons in that one,
we can transition this into,
for example, emptying
the a gallon jug.
So be y of 0.
Or we can empty the b jug.
Well, filling is
something similar.
But now we are actually pouring
more water from the fountain,
essentially.
Right?
All those tennis balls here.
And we can fill up say the
a gallon up to a gallons,
and leave the b jug as it is.
Or w we can fill up the b gallon
jug, and leave the a gallon jug
as it is.
So these are these
two transitions.
And the pouring of one--
of one jug into the
other is actually
a little bit more complex.
So let's have a look.
So how does pouring work?
Well, suppose we
start with x and y.
So let's have a look here.
Um, I don't know.
Suppose we have 2 balls in
here, and 2 balls in here.
Well, in that case, I can say
pour all of these over in here.
Right?
So that's easy.
But there's also another
possibility, better
when I pour all of
these over in here.
But hey, I can
only put in 1 ball,
because it's only
a three gallon jug.
So I'm left with only 1.
A gallon in this jug.
So these are two--
these are two situations
that we need to explain.
So let's first do the first
example that I just did.
I pour everything over
into the other jug.
So we have 0 gallons
left in here,
and x plus y gallons
left in the other jug.
And this can happen if there's
sufficient space, right?
So this can only happen
if x plus y is at most b.
Which is the capacity
of this b gallon jug.
Now if that's not
the case, then I
can pour in just a little
bit, like just say 1 ball.
Like just one of
these can go in here.
So that's the other case.
So x, y we'll actually go to--
well, let's just
see how this works.
How many gallons are left in
this b gallon jug to fill up?
Well, we have b minus
y gallons left, right?
Space left.
So we can take b minus y
gallons out of this one
to fill up this one.
So let's do it.
We take b minus y
gets out of the a jug,
and put it all in here, and it
makes it completely filled up.
So we have b gallons over here.
So this is really equal to
x plus y minus b, comma b.
And this only is possible if--
if you are essentially in
the complimentary case.
So we have that x
plus y is at least b,
such that there is enough
gallons in the a jug
to be poured over to
fill up the b jug.
So these are the
two kinds of cases.
And, of course,
by symmetry we can
do also the pouring from the
other jug into the first.
So let's write all
those out, as well.
So x, y can actually go
to x plus y, comma 0.
I pour everything
from here to there.
And this only holds if
x plus y is at most a.
The other possibility is
where, exactly as in this case,
we can only pour a minus
x gallons over from y
into this particular jug.
And then this one is
completely filled up.
And then I have a few
gallons left over here.
So how does that look?
Well, we completely fill
this up to its capacity.
And what is left
this is y minus--
how much did we have
to pour in here?
Well, that's a minus x.
And we again have
a similar formula.
But it now looks a
little bit different.
X plus y minus a.
And this is only for the case
where x plus y is at least a.
OK.
So these are all the cases.
So maybe there are some
questions about this.
Is this clear, that we have
these different possibilities?
Like when we look at
these jugs we can either
empty them, filling them up.
Or we can pour say
only 1 ball over up
to the full capacity
of this jug.
Or we can just pour everything
over into, say, this jug.
So those are the different cases
that are now fully described
by this state machine.
So now we can start to prove
this theorem over here.
So how do we go ahead?
How are we going to use what
you've learned like induction,
and invariance?
So let's do it.
But before,
actually, we do this,
let's take this
example that we had
and see how we can describe all
the transitions that we just
did, as far as I remember them.
So we have that a
equals 3, b equals 5.
Right?
We start with empty jugs.
We need to filled up the
five gallon jug, right?
Then we started pouring
the five gallon jug as much
as we could into the
three gallon jug.
So it's one of those rules.
We've got 3 into 2.
Then we emptied the
three gallon jug.
We got 0 and 2.
Then we did--
What did we did next?
Oh yeah, we poured
everything into this one.
So we have 2, 0
as the next state.
We filled up-- actually I
forgot exactly what we did next.
But I think we filled
up the five gallon jug.
And then we simply
poured over as much
as he could from
the five gallon jug.
And we got 3 and
4, and here we are.
We got 4 gallons.
So what we just did is fully
describe this state machine.
So let's not try to
prove this theorem.
So as I said, we're
going to use induction.
So you always would
like to write this out
if you solve your problems.
What are we going to assume?
Well, we assume actually
that m defines a,
and m defines also b.
That's the assumption
of the theorem,
and now we need to prove that
defies any result that you can
achieve in this state machine.
So what's the invariance
that we are thinking about?
Invariance is going to be--
Oops.
It's a predicate.
And it says something
like, if the state xy--
if this is the state
after n transitions--
Then we would like to conclude
that m the fights both x,
and m defines y.
So this is our--
our invariance.
And we like to use this
to prove our theorem.
So how do we start
usually, right?
So we always start with--
with a base state.
Great.
So let's do it.
The base case is--
well, we start with the all
0s, like the empty jugs.
It's-- well, and we also--
have paid a little
bit of extra attention
to what we mean by
division over here.
We said that all integers
actually divide 0.
So in particular,
m. m divides 0.
m, 0.
So the very initial
state, 0 comma 0,
is indeed complying to
is particular invariant.
So let's write it out.
So we have the
initial state 0, 0.
We know that m divides 0.
And therefore, we
know that p 0 is true.
So that's great.
So the inductive step.
How do we start the
inductive step--
step all the time?
And we will assume,
actually, p of n, right?
So lets assume that.
And now we would like to
prove p, and then n plus 1.
So what do we really want to do?
We want to say, well, we know
that we reached a certain state
x comma y, for which m
divides x, and m divides y.
Now we would like to show
that if we transition
to a next state, we again have
that same property, that m
divides the number of gallons
in both jugs once more.
And then we can con--
can conclude p, n plus 1.
So that's how we always proceed.
So let's see where
we can write it out
in a bit more formal way.
OK.
So how do we go ahead?
Suppose that x, y is the
state after n transitions.
Well, what can we conclude?
Well, we have the predicate
pn, the invariant.
So we know that n divides
x, and n divides y.
And we concluded that
because pn is true.
So after another transition--
what happens after
another transition?
So we can conclude
that the jugs are
filled by the different
types of numbers
that we see here this
is state machine.
So let's write them out.
So after another transition,
um, each of the jugs
is actually filled--
Um, are filled with--
well, either if I've emptied
it, say a 0, 0 gallons, a, b, x
and y.
I see appearing over here.
And I also notice
that I see x plus y.
And x plus y, minus b.
And x plus y, minus a.
Those are all the
different number
of gallons that can be in jug.
Yes, please?
AUDIENCE: [INAUDIBLE]
PROFESSOR: In our example--
Yeah, that's a good question.
So in our example
problems of 3 and 5,
it turns out that
the only number that
divides 5 both the three gallon
jug, and the five gallon jugs
is actually one.
So in our example, we
would have that m equals 1.
So over here we have
that only 1 divides a,
as well as 1 divides b.
So m equals 1 in our case.
But for example, in the three
gallon jug, and the six gallon
jug--
Right?
We have that m equals 3, like
3 divides 3, And 3 divides 6.
So those are the two cases that
you sort of look at right now.
But you put into a much
more general setting, right,
we are distracted away
from the actual numbers.
And use a and b as
representations.
Are any other questions?
So after another
transition, each of the jugs
are filled with, well,
either 0 gallons, if we
have a completely emptied them.
Or we have filled the first
a gallon jug, or it can be b.
We also noticed that it can be--
it can be of x, of course.
It can be y, because that's
the state that we are in.
And we can have x plus y, minus
a, which appears over here.
And x plus y, minus b.
So these are all the
different number--
possible number of gallons.
The x plus y.
That's also present.
Is that true?
Yeah.
That's right. x plus y.
So we also have x plus y.
Actually, it's good
to check that again.
So we have 0, x, y, a, b.
Got those.
X plus y, and x plus y, minus
p, and x plus y minus b.
Yeah.
So now we can start using our--
our assumptions.
So what our they?
We have that in order
to prove this-- right?
At the top over here, we assume
that m divides, and m divides
b.
So we know that first of
all, m divides 0, of course.
But we know that m divides a.
We know that m divides b.
We have concluded
that m divides x.
And also m divides y.
So if you now use some
facts about divisibility
on your handout, which
we will not prove now.
But I think most of them will be
on your problem set, actually.
We can conclude that also linear
combination of a, b x and y
will be divisible by m.
In particular, m
will divide x plus y.
m will divide x plus y minus
a, and also x plus y, minus b.
So we will conclude
that m actually
divides any possible results.
So divides any of the above.
And now we're done.
Why is that?
Because we have shown now that
after the next transition--
after we have reached
x, y after n steps,
then in our n plus 1-th step,
all that you can achieve
is divisible by m.
So that's exactly
the invariance.
So we conclude that
p, n plus 1 is true.
And so now we're done.
Are any questions
about this proof?
So this is like the
standard technique
that we tried to use all
the time here in this class.
We will use it in all
the other areas, as well.
In graph theory, in particular.
And especially in number
theory, will also use it,
especially in this class.
OK.
So let's apply this to theorem.
Let's I think about
this movie that we saw,
this Die Hard number 3.
Die Hard number 4 came out.
And then the cast got
stuck in Die Hard number 5.
There's was a problem,
because the rumors
were that in Die Hard number 5,
they had like a 33 gallon jug.
That's a lot.
And a 55 gallon jug.
So Bruce has in
training his muscles,
because you can imagine
those are pretty heavy.
So if you want the pour one
into the other, my goodness.
So-- but the question is, is
he training the right muscles?
So can we apply this theorem
now, and showed that--
Oh, I should to tell
you what is the problem.
Well, again, he has to
get say 4 gallons out
of this-- out of these two jugs.
So is that possible?
It's not.
I see someone shaking his head.
Do you want to explain why?
AUDIENCE: A and b are
both divisible by 11.
PROFESSOR: Yeah.
AUDIENCE: So any other
configuration will also
have to be divisible by 11.
And 4 is not divisible by 11.
PROFESSOR: Exactly.
4 is not divisible by 11, so
the whole cast got blown up
in Die Hard number 5.
And so we have no Die
Hard number 6, as well.
OK, so-- so now
all of this stuff
actually helps us to define
a new concept, as well.
So let's do that.
I'll put it up here.
We will use the
terminology GCD of a and b
as being the greatest
common divisor of a and b.
So, for example, if we
are looking at a equals 3,
and b equals 5, well
then the GCD of 3 and 5
is actually equal to 1.
There's no other larger integer
that divides both 3 and 5.
In other examples are, for
example, if we have the GCD of
say 52 and 44.
Well, what's this equal to?
Well, this actually
is 4 times 13.
This is 4 times 11.
So 4 divides both this,
and both this one.
But nothing larger can
divide both of those.
So we have that
this is equal to 4.
We will have a
separate definition
that talks about this
very special case where
two numbers--
if you look at their
greatest common divisor--
when that greatest common
divisor is equal to 1,
we actually define
those two numbers
to be relatively
prime to one another.
So let's put that out over here.
So that's another definition.
We say that a and
b are relatively
prime if the greatest common
divisor is actually equal to 1.
Now today we will not really
use his definition so much,
but it's actually
very important.
And we'll come back
to this next lecture.
So if we now look at this
particular thing them
over here, can we see a
nice corollary of this?
Like a result, if you
think about this greatest
common divisor.
Well, the greatest
common divisor off a an b
divides both a and b.
So the greatest common
divisor of a and b
will divide any result that
we can generate by playing
this game with the jugs.
So the corollary here is
that the GCD of a and b
divides any result.
OK, so that's really cool.
So this already tells us
quite a bit about this game
that we have here.
So now what we would
like to do is to find out
what exactly we can be reached?
We have a property that
we have shown here.
But what else can we do here?
Now it turns out that
you can say much more,
and we would like to prove the
following theorem to make--
to analyze this whole
thing much better.
I don't think I need the
state machine anymore.
So let's take that off.
The theorem that we
would like to prove
is that any linear
combination of the-- let's
change this into
the 3 and 5 again.
Any linear combination
of 3 and 5,
I can make with these 3
and the 5 a gallon jug.
So let's write it out.
So any linear
combination l, which
we writes as some integer s
times a, plus some integer
t times b.
So any linear combination
of a and b, with--
well, of course, the
number of gallons
should fit the largest the jug.
So with 0 is, at most l.
Is it mostly can be reached.
So this theorem we
would like to prove now.
And in order to
do that, we would
like to already think about
some kind of a property
that we have.
So when we talk about linear
combinations, the s and the t
can be negative, or positive.
We really don't care.
So for example, we could
have like, I don't know,
minus 2 times--
so for example, 4 is equal
to minus 2, times 3, plus--
actually, is that true?
Yeah.
Plus 2, times 5.
So here we have s to be equal
to minus 2, and t is equal to 2.
And of course, a is
equal to 3, right?
And be is equal to 5.
So 4 is a linear
combination of these two.
And according to the theorem,
we can create that number
of gallons in this jug.
And we already saw
that, because we did it.
But for our theorem,
in order to prove this,
we really would like
s to be positive.
So how can we do that?
If anybody has an
indea what we could do?
AUDIENCE: Let's assume
that b is greater than m.
PROFESSOR: Yeah.
We have still that a
is supposed to be--
We will assume that
throughout the whole lecture.
Thanks.
So in order to prove
this, we really
would like to have
s to be positive.
So let's just play
around a little bit
with linear combinations
to get a little bit
of feeling for that.
How could we write
4 differently,
as a linear
combination of 3 and 5,
such that we have actually
a positive number over here?
Does anybody see
another way to see that?
AUDIENCE: [INAUDIBLE]
PROFESSOR: Yeah, that's true.
3 times 3, minus--
minus 5.
So-- and how did we do that?
Well, we can just say
5 times 3 to this one,
and then subtract the same
again, minus 3 times 5,
over here.
And if he adds those
things together,
he will see 5 minus 2, is
3 times 3, as you said.
And we have minus 3 plus 2
is actually minus 1 times 5.
And this will be a different
linear combination of 4.
So what we can do here, we can
sort of play around and make
this s over here, which we now
say call s prime, is positive.
Actually, it's larger than 0.
So let's start the
proof for this theorem.
It's pretty amazing
to me, actually,
that you can do so
much a game like this,
and see so much happening.
So let's figure
out how this works.
OK.
So let's first formalize this
particular trick over here.
And how do we go ahead with it?
Ah, well, notice
that we can rewrite
L, which is equal to s
times a, plus t times b.
s, you know, we can just add
a multiple of b over here.
n times b, say m times a.
And we can subtract the
same amount over here,
minus n times a, times b.
So do you see what
I did over here?
I have added n times b, times a,
and subtracted n, times a times
b.
And we did something similar
over here, not exactly
the same.
But that's what we did.
And you can imagine
that we can choose m,
such that s plus n times
b will be larger than 0.
We can do that.
So essentially this proved to
us that there exists an x prime,
and also the t
prime, such that L
can be rewritten as
a linear combination,
s prime, times a,
plus t prime, times b.
But now with you extra
property, that s prime
is actually positive.
Now this is really
important, because we're
going to create an
algorithm of playing
with those jugs that can
achieve this particular linear
combination.
And that's how we're going
to prove this theorem.
So let's assume that 0 is
less than L, is less than b.
I know that we, in
the theorem, we also
consider the case is L
equals 0, and L equals b.
But those are obvious, right?
You could either empty
the jugs, or just
fill up with the bigger one.
So we will consider
just this case.
All right.
So what's the algorithm
going to do for us?
The algorithm is going to
repeatedly fill and pour
our jugs in a very special way.
And miraculously we
will be able to get
the desired linear
combination every single time.
And of course, we're going
to use induction again
to prove this property.
OK.
So how does the algorithm work?
Well, to obtain L gallons
we're going to repeat
s prime times, which is the
number that we have over here.
The following algorithm--
we first of all,
we will fill the a jug.
This one.
After we have done
this, we are going
to pour this into the b jug.
So how do we go ahead?
We pour- oops.
This into the b jug.
And when this b jug becomes
full, we are going pour it out.
So let's write it out.
So when it becomes full, it
will actually empty it out.
And we will continue pouring
the a jug into the b jug.
So we'll continue this process.
So let's take an example
to see how that works.
So we keep on doing this until
the a jug is actually empty.
So let's take an example.
So let's see.
Let's do that over here.
Actually we can do
the tennis balls, too.
Let's do that first.
See how that works.
So essentially, in
order to get 4 gallons,
we just fill up the
three gallon jug.
We empty it all in here.
We fill it up again.
You pour in as much as we can.
That's-- that's it.
We have to empty this one.
Oops.
We have to keep on pouring.
Put this in here.
Fill this one up, and then pour
over into the five gallon jug.
And now we've got 4
gallons over here.
So what did we do?
So let's write it out.
So for our special linear
combination over here,
we have that 4 equals 3,
times 3, minus 1, times 5.
So we need to repeat
this process three times.
So let's do that.
In our first loop we
will do the following.
We start with the start
state, the pair 0, 0.
We're going to fill up the
very first jug all the way up
to its capacity, 3.
And we put it all
over into the b jug.
What happens in the second loop?
The second loop, we
again fill up the a jug.
So we have-- we start at 0, 3.
We fill it up.
We get 3, 3, the pair 3, 3.
We pour everything in
here, as much as we can.
That give us 1, 5.
Only 2 gallons are poured
into the bigger gallon.
We empty the bigger
gallon, the bigger jug.
We get 1, 0.
And we keep on pouring,
and you get 0, 1.
So now in the third loop--
and that's where we
should get the 4 gallons.
We start off with 0,1.
Um, we fill up the a jug.
We pour everything over into
the bigger jug, and we get 0, 4.
And that's the end result.
So this algorithm seems to work
for this particular example.
Of course we would like to prove
it for the general situation.
So how do we do it?
Well, we're going to just
to analyze the algorithm
in the following way.
We can notice that
in this algorithm,
we fill up s prime
times the a jug,
and we essentially pour
everything out into the b jugs,
and we sometimes
empty the b jug.
So let's try to think
about this a little bit,
and see how we could
try to formalize this.
So let's write it out.
We have filled the a
gallon jug s prime times.
We also know that the
b jug has been emptied
a certain number of times.
So let's-- let's just assume--
suppose that the b jug is
actually emptied, say, u times.
I do not know how many times.
But I say, well, let's
assume it's u times,
and try to figure
out whether we can
find some algebraic expression.
So at the very end
of the algorithm,
let r be what is in the b jug.
So let r be the remainder,
in the b gallon jug.
So now we can continue.
We know if r is what left
in the b gallon jug, well,
we know already
some property of it.
Actually, let's put
that on the next board.
We know that 0 is at
most r, and at most b,
because that's what's left
in the b gallon jug, right?
So we know these bounds.
We have assumed that 0 is
less than L, is less than b,
which we put over there.
We know that r must
be equal to what
kind of linear combination
of s prime, and u?
So-- Well, we have been
filling of s prime times.
So this is what we added in
water to the whole system,
you can say, s prime times a.
And we poured out water.
Well, we did that u times
from the b gallon jug.
So we poured out
u times b gallons.
So this is the remainder that
this left in this bigger jug,
right?
So are there any
questions about this?
So-- OK.
So we also know that
L is equal to s prime,
times a, plus t prime, times b.
And this is the
linear combination
that we would try
to prove of, that it
is left at the very end.
So what we want to show
is that r equals L.
So how do we do that now?
How are we going to show
that r can be expressed
in L, in a special way.
So let's have a look.
So these are all
tricks in the sense
that I'm giving you
this proof, but how do
you come up with this yourself?
Sometimes you play a lot
with these kinds of things,
and you get a feeling
of what kind of--
sort of pattern exists,
and what kind of intuition
you need in order to write
down a proof like this.
So let's rewrite this.
I'm going add t prime times b.
And I'm going to
subtract it again.
So I have s prime times
a, plus t prime times b.
I subtract it again, and I
still have this amount left open
here.
So what is this equal to?
Well this part is equal to L.
So this is equal to minus--
and I have a multiple
of b, which is t prime,
plus u times b.
Hm.
Now this is very interesting.
Does anybody see how
we could continue here?
So we have r expressed as
L, minus a multiple of b.
And I also know that
L is in this range.
I also know that r
is in this range.
So that's kind of
interesting, right?
So how can that be?
What should be the case here?
Does anybody see what kind
of property t prime plus u
must have in order
to make that happen?
So let's have a look here.
We have L. It's in this range.
So let's just draw an axis.
So at 0, we have b.
And somehow in this
range, we have L. Now
if I subtract like actually
b, or something more than b,
or I add more than b.
I will jump out of this range,
and I go somewhere over here,
or I go somewhere over there.
Right?
So if I said suppose
L is over here,
then L minus b would be over
here, which would be negative.
Or if I add b, it
will be over here,
which would be more than b.
Now we know that this is equal
to r, but r is in this range.
So that's not really possible.
So let's write it out.
So if t prime plus
u is unequal to 0,
so we're actually
really subtract
or add a multiple of b.
Then I know that r is
either smaller than 0,
or r is larger than b.
Now we know that
cannot be the case,
so we can conclude that
t prime plus u equals 0.
Now that implies that
t prime equals minus u,
or maybe other way around,
because that's easier
to see what's happening.
So u equals minus t prime.
If you plug that
in here, well, we
get exactly the same expression.
You see?
Minus, minus t prime is
equal to plus t prime.
And we get the exact
same linear combination.
So we conclude that r equals L.
And now we're done.
Why is that?
Well, we have shown that the
very last number of gallons
that is left after
this procedure,
after this algorithm,
is actually
exactly equal to the
linear combination
that we wanted to achieve.
So now we got the
proof for this theorem
that tells us that any linear
combination is actually--
of a and b can
actually be reached
by pouring gallons
over and back,
and emptying and
filling those jugs.
All right let's continue.
So there was a question over
here that I would like to--
that I would like to address.
So maybe I did not make
so clear what the s prime,
and the t prime is over here.
And in this proof,
we started off
with this linear combination.
I would like to
have an algorithm
of pouring that creates L
gallons in say the bigger jug.
So in order to do that,
I want to find, say,
a linear combination that
makes this L such that this
s prime is an integer--
positive integer.
Why do I want to have
a positive integer?
Because in this algorithm,
I'm going to repeat something
s prime times.
If s prime is negative,
I cannot do it, right?
So s prime has to be
a positive integer.
In order to create such
a positive integer,
I can just add like
1,000 times b times,
and subtract 1,000
times a times b.
That's OK I could
just add a lot.
And if I add enough, I can
make s plus n times b positive.
Even if s is, say, minus 100,
well, if I add 1,000 times 5,
I will get a positive number.
So that's sort of
the reason this proof
that we want to rewrite
the linear combination
to a new one, such that
s prime is positive.
And if we have s prime
positive, then we
can actually talk
about this algorithm,
because we can only repeat
something s prime times,
if s prime is say 1, or 2,
or 3, or something positive.
All right.
So let's-- I'll talk
about say the next part.
So we have gone--
We have proved two theorems.
But in the end we would like
to have a characterization
of the greatest common divisor.
That's the goal of this lecture.
So let's do it.
Um.
In order to do this,
let's first of all
look at our five gallon,
and three gallon example.
We know that the greatest
common divisor is equal to 1.
We know that 1 can be rewritten
as a linear combination, as 2
times 3, minus 1 times 5.
So that means that according
to the theorem that we
have up here, we can
actually make exactly 1
gallon in one of these jugs.
So that means that we can also
have any multiple of those.
So we can reach any multiple 1.
That's very special.
So this particular case,
we know that any multiple
of 1, any number of
gallons can be reached.
So can we sort of
generalize this a little bit
by using the greatest
common divisor?
So the greatest common
divisor 3 and 5 is equal to 1.
And we have shown that the
greatest common divisor defies
any result. Can we
say something more?
Can we say that the
greatest common divisor
can be maybe written
as a linear combination
of this type over there?
And that's how we are
going to proceed now.
So let's set talk about the
very special algorithm which
is called Euclid's algorithm.
And I think in the book it's
also called The Pulverizer.
And you will have
a problem on this
just to see how that works,
and to really understand it.
So let's explain
what we want here.
So first of all, we know
that for any b and a,
there exists a unique
quotient and remainder r.
So let's write it out.
There exists unique q, which
we will call the quotient.
And r.
We call this the remainder.
Such that b equals
q times a, plus r.
With the property that 0 is
at least r, and at most a.
So we're not going to
prove this statement.
It's actually like
a theorem, right?
But let's just
assume it for now.
And in the book you
can read about it.
We're going to use this to prove
the following lemma that we
will need to give
a characterization
of the greatest common divisor,
as a linear combination
of integers.
Oh, before I forget, you
will denote this remainder
as rem of b, a.
And this is the notation
that we use in this lecture.
So what's the lemma?
The lemma is that the greatest
common divisor of a and b,
is equal to the greatest common
divisor of the remainder of b
and a.
With a.
So what did we do?
Let's give an example
to see how this works.
For example, let's take--
actually let's do it
on this white board.
So, let's see.
For example, let's
see whether we
can use this to calculate the
greatest common divisor 105,
and 224.
So how can we go ahead?
Well, according
to this lemma, we
can rewrite this as the
greatest common divisor
of first the remainder of
224, after dividing out
as many multiples
of 105 as possible.
And 105.
So what are we
going to use here?
We're going to use that 224 is
actually equal to 2 times 105,
plus 14.
So we had the GCD of 14 and 105.
Now why can I do this?
Well, I'm essentially just
subtracting like 2 times 135
from 224.
Well, the greatest
common divisor
that divides 105 and
224 also divides 105,
and a linear
combination of 105, 224.
That's essentially
what we are using.
And that's actually
stated in this lemma,
and that's what we
would like to prove.
So let's continue
with this process,
and do the same trick once more.
So we can say that we can
rewrite this as the greatest
common divisor of, well,
the remainder of 105
after taking out this many
multiples of 14 as possible,
and 14.
So what are we going
to use over here?
We are going to use that 105
is equal to 7 times 14, plus 7.
So this is the greatest
common divisor of 7, and 14.
Now if you just
continue this process,
we can see that this is equal
to the greatest common divisor,
again, of the
remainder of now 14,
after dividing out as many
multiples of 7 with 7.
Now this is equal to 0, 7.
Why is that?
Because 14 is equal
to 2 times 7, plus 0.
So 0 is the remainder
after dividing out
7 as many possible
times as possible.
OK.
So we have the greatest
common divisor of 0, and 7.
What's the largest integer
that can divide both 0 and 7?
Well, any integer can divide 0.
So we know that
this is equal to 7.
So essentially, what
we have done here,
we have repeatedly used
this particular lemma
to compute in the end, the
greatest common divisor of 105
and 224.
And we have been very methodol--
we have used a specific method.
We used the lemma,
and we worked it out.
We used the lemma
again, and we just
plugged in the actual numbers.
Used to lemma again.
Plugged in the actual
numbers, and so on.
And this is what is
called Euclid's algorithm.
And in the book it's also
called The Pulverizer.
And there's, I think,
a few other names.
But I like this one.
So this is an example
of Euclid's algorithm.
So now let's have
to look whether we
can have prove this particular
lemma, and actually I will--
Yep.
We're going to prove this lemma.
OK.
So how do we do the proof?
Well, first before we
know that if- yeah.
Well, how do we do this?
You would like to prove that
if the great-- well, if n
divides a and b, in
particular, the greatest
common divisor divides a and b.
We would like to show
that it's dividing also
the remainder of b, after
dividing out a, and a itself.
If you can show
that, then we know
that the greatest common
divisor of this thing
is at least what
we have over here.
So I said a lot right now.
So let's try to write
it out a little bit.
So suppose that m
is any divisor of a.
And at the same time,
m also divides b.
Well, then I know
that m also divides
b minus, say, the quotient, q
that we had over here, times a.
And-- and this is actually equal
to the remainder of b and a.
Now we also note
that m divides a.
So what did we show here?
We showed that if m divides,
and m divides b, then m
also divides the
remainder of b and a.
And n divides a.
So what does is prove?
Well, it proves
that, in particular,
the greatest common divisor
over here divides this one.
That's interesting.
That essentially means that
we have shown this inequality.
Because if this
one divides this,
well, that means that
this number over here
must be at least what
we have over here.
OK.
So let's continue.
We consider two cases.
If the remainder of b and
a is unequal to 0, well,
what can we say now?
We can say that if I
know that m divides
this remainder of b and a, which
can be rewritten as b minus q,
times a.
And I also note that--
if I also know that n
divides a, then this actually
implies the reverse of this
statement, that n divides a,
and divides b.
Now why is that?
Well, we're actually
using the fact
that if n divides b, minus
q, times a, and m divides a,
then m also defies any linear
combination of these two.
In particular, this plus
q, times a, which is b.
m divides b.
So maybe I'm going a little
bit fast here, I notice.
This all also has to do with
all the lecture handouts.
You see a few facts
on the divisibility.
And in particular, item number
three that talks about the fact
that I'm using here.
If a divides b on your handout,
and a divides c, then I
know that a divides any
linear combination of b and c.
So that's essentially what
I'm using here repeatedly.
OK
So let's look at the other case.
If the remainder is equal
to 0, well, then I actually
know that b minus q,
times a is equal to 0.
Well, if I know that
m divides a, well,
then since 0 equals b minus q,
times a, I know that b equals
q, times a.
So if m divides a, I also
now that m divides b.
So this is one argument.
This is another one.
And this was--
These are the three
arguments that
now show that anything
that divides these two also
divides a and b.
So now we have the
reverse argument, right?
So this greatest common
divisor divides this one here,
and this one.
And we just proved that
it divides a and b,
and so it must
divides the greatest
common divisor of a and b.
So now we have shown
the other inequality,
and this proves equality.
So you should definitely look
this up in your lecture notes.
So now we can finally prove
this beautiful theorem
a that will help us to
characterize the-- actually,
let me put this over here.
So the final theorem
that we prove here
is that the greatest
common divisor of a and b
is actually a linear
combination of a and b.
So we're going to use this
algorithm that you have
over here, Euclid's algorithm.
And we are going to do a
proof, again, by induction.
And we use an invariance.
So we use a similar kind
of strategy, of course.
The invariance that we
are going to use says--
well, if Euclid's algorithm
reaches the greatest
common divisor of x and y--
so for example, it's reach, say,
7 or 14, and 105, for example.
Then, say, after n steps
then both x and y are
linear combinations of a and b.
So then x and y are linear
combinations of a and b.
And at the same
time, we also know
that the greatest common
divisor of a and b
is equal to the greatest
common divisor of x and y.
So this is my invariance.
And the way I will go ahead is
to simply do what you do always
in these situations.
So we start with the base case.
And we can immediately see that
after 0 steps in the Euclidean
algorithm, I've done
absolutely nothing.
So obviously after
0 steps, x equals a.
y equals b.
So of course, they are linear
combinations of a and b.
And this equality
holds, as well.
So for the base case--
So after 0 steps, we immediately
know that p 0 is true.
Now for the inductive step, we
have to do a little bit more.
As usual, right?
We always assume p n.
And now we would like
to prove p n plus 1.
So how do we do this?
Well, we notice that
there exists a q such
that the remainder of y and x
is equal to y minus q, times x.
So we assume p n.
We have reached
some state, x, y.
We know that the remainder
of y, x equals y minus q,
times x, for some quotient q.
We know that y is a linear
combination of a and b,
and x is, as well.
So that means that this
one is actually also
a linear combination of a and b.
So now when we look at this
, algorithm we can see that--
that if you look at
the remainder that
appears in here, that's still a
linear combination of a and b.
So after a extra step, we
notice that what we have reached
are still in
combinations of a and b.
And of course, the
lemme has showed--
has shown us that what
we reach is still equal--
the greatest common
divisor is still
equal to what we originally
started out with.
So this proves p of n plus 1.
So n-- let's finish
this particular proof.
So for the very last
step, if you now
look at this particular--
so if you look at the very end,
we notice that in every step
the remainder is getting
smaller, and smaller,
and smaller.
Right?
And you can use a similar
kind of proof technique
to show that after a
finite number of steps,
we will reach a GDP of 0, y.
Something like this.
So in the very last step
of Euclid's algorithm
we achieve something
off this form.
We now use our
predicate over here,
and say that y is a linear
combination of a and b,
but the greatest
common divisor of 0, y
is also equal to the original
greatest common divisor
that we want to characterize.
So now we have
proved the theorem
that says that the greatest
common divisor of a and b
is actually a
linear combination.
So now we're going to
combine all those three
theorems in one go.
And that will show
us the final result,
which is that the theorem that
the greatest common divisor
of a and b is
actually the smallest
positive linear
combination of a and b.
So we're going to combine
all of these together.
We know that the greatest common
divisor divides any result.
The theorem up there says
that any linear combination
can be reached.
And also just showed--
have shown that the
greatest common divisor
is a linear
combination of a and b.
So we can combine those
three to get this theorem.
So how do we do it?
Well, let's just look
0 all the way up to b.
Suppose these are all
the results that we
can reach in our problem.
We know that the greatest common
divisor divides all of those.
At the same time, it's
also linear combination
that's over here.
Since it's a linear combination,
it can also be reached, right?
By the theorem that we have.
So suppose that this is the
greatest common divisor.
But we also know that the
greatest common divisor
is dividing all of these points
here that can be reached.
So therefore, it must
be the smallest one.
And I will leave you
with some homework
to think about this
very carefully.
And you can show for
yourself that you can now
combine those three
arguments together, and see
that the greatest common divisor
must be the smallest positive
linear combination.
So, I will see next Thursday.
