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 defines 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?