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