Problems

Loading...

From the course by University of California San Diego

Number Theory and Cryptography

74 ratings

University of California San Diego

Number Theory and Cryptography

74 ratings

Course 4 of 5 in the Specialization Introduction to Discrete Mathematics for Computer Science

We all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for thousands of years. And for thousands of years it was more or less just a game that was only interesting for pure mathematicians. Famous 20th century mathematician G.H. Hardy once said “The Theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the word nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

From the lesson

Modular Arithmetic

In this week we will discuss integer numbers and standard operations on them: addition, subtraction, multiplication and division. The latter operation is the most interesting one and creates a complicated structure on integer numbers. We will discuss division with a remainder and introduce an arithmetic on the remainders. This mathematical set-up will allow us to created non-trivial computational and cryptographic constructions in further weeks.

Divisibility6:50

Divisibility Tests5:35

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

[MUSIC]

Let's consider several problems in number theory and consider the following problem.

Suppose a is not divisible by 2, so a is odd.

What possible remainders can a have when we divide it by 4?

Okay, so

there are four possible remainders for the number when we divide it by 4.

The remainder can be 0, it can be 1, it can be 2 and it can be 3.

So let's consider these cases and see which of them are possible.

Okay, clearly the remainder is 0 is impossible.

If the remainder is 0, it means that a is divisible by 4.

So it has the form 4 times some integer k.

And so a is even.

But we know that a is odd, so this case is impossible.

Okay, there is one more similar case.

Consider the remainder 2.

So suppose a has remainder 2 when we divide it by 4.

So a has the form 4 x some q + 2.

Note that here, a is also even.

Note that 4 x q is even, and 2 is also even.

So the sum of these numbers is also divisible by 2.

So this is also impossible since we know that a is not divisible by 2.

There two remainders left, 1 and 3, and they are both possible.

So clearly, here are simple examples.

a = 1, and then if we try to divide 1 by 4, then clearly the remainder is 1.

And a = 3 is another example.

If we try to divide 3 by 4, then the remainder will be 3.

So the remainders 1 and 3 are possible and the remainders 0 and 2 are impossible.

Let's consider the following problem.

So suppose we have four integers, a, b, c and d.

Can we say that two of them must have a difference that is divisible by 3?

Can we say that for any four integers,

there are two among them such that their difference is divisible by 3?

Okay, let's consider some examples.

Let's just pick some numbers and see whether this is true or not.

Let's pick number 1, 100, 27 and, for example, 5.

Okay, let's look at these numbers.

Can we find two of them that has difference that is divisible by 3?

And indeed, we can.

If we subtract 1 from 100, then we have 99, which is divisible by 3.

99 is 3 times 33.

We failed, we tried to find an example and we failed.

So probably we should try to show that it is always the case.

And indeed, this is true.

It turns out that this is always the case.

Among any four numbers, there are two such that their difference is divisible by 3.

Why is it so?

And the crucial idea here is the following.

Just note that there are only three possible remainders

when we try to divide numbers by 3.

The remainders are 0, 1 and 2.

And we have four numbers.

So note that among these four numbers,

at least two must have the same remainder when we try to divide them by 4.

And so if we subtract these two numbers as we already observed,

their difference is divisible by 3.

If two numbers have the same remainder when we try to divide them by 3,

then their difference is divisible by 3.

So it is always the case.

Among any four numbers, there are two such that their difference is divisible by 3.

Let's consider our next problem.

Consider 3-digit non-negative numbers, and the question is the following.

Suppose we are trying to divide them by 101.

How many of the numbers will have the remainder 7 if you divide them by 101?

And here in this problem, we assume that 1-digit numbers and

2-digit numbers are also 3-digit numbers, they just start with 0.

So 3-digit numbers are numbers from 0 to 999.

Okay, let's see how many numbers do we have in this problem.

Let's look at all numbers that has a remainder 7 when we

try to divide them by 101.

And all of them has the following form.

a = 7 + q x 101.

And q here is arbitrary integer number.

Okay, let's look at all possible values of q and

see whether they fall in our interval, whether the result is between 0 and 999.

Note that if q is negative, then a is clearly also negative.

So these numbers doesn't fall in our interval.

Now the first number that falls in our range is for

q = 0, then a = 7 + 0 x 101, which is just 7.

So for q = 0,

a satisfies our property.

Okay, now we have q.

The remaining values of q are 1, 2, 3 and so on.

And the number a grows when q grows.

And the last q such that a is still a 3-digit number,

it is not hard to check that this q = 9.

Then a = 7 + 9 x 101,

which is just 7 + 909, which is 916.

The next a will be already greater than 1,000.

So this is the last q for which our number falls into this interval.

So a falls in our interval, a 3-digit for q from 0 to 9.

There are 10 such numbers q.

So there are 10 such numbers over a 10 3-digit numbers that

give a remainder 7 when we try to divide them by 101.

[MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play