Remainders

Loading...

From the course by University of California San Diego

Number Theory and Cryptography

58 ratings

University of California San Diego

Number Theory and Cryptography

58 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]

So division is not always possible.

But we can generalize this notion to be applicable to all a and b.

So suppose we have a positive integer b.

And we will introduce division with remainder now.

The result of the division of a by b with a remainder is a pair of integers q,

which is called quotient, and r, which is called a remainder.

Such that a is equal to q times b + r and

r is nonnegative but is at most b.

And note that, if r = 0, then b divides a.

And note that this notion, this definition just turns out

to be the definition of the fact that b divides a if r is equal to 0.

Okay, now, what is the intuition behind this notion?

So here is the definition again on the top of the screen.

And the intuition is simple.

So, and assume here, again, for simplicity that a is positive.

So suppose we have a group of a objects and

you would like to split it into some groups of size b.

And now we can pick these groups of size b one by one.

And if we do it, then in the end, we might have some number of

objects left that are not enough to form one more group.

And then this number of objects will be r, will be the remainder, and

the number of groups we have formed will be q, the quotient.

And so this formula will be exactly true.

So we have q groups of size b, and we have additionally r objects left.

And since r objects are not enough to form a new group, then r is less than b.

So here's the intuition behind this definition.

And let's consider some examples.

For example, consider a = 15 and b = 4.

Note that 15 doesn't divide 4.

But still, it divides.

So we can divide 15 by 4 with the remainder.

15 = 3 times 4 + 3.

It can be easily checked.

And then q = 3, and r is also equal to 3.

Here is another example.

We can apply division with remainder to negative numbers.

If a is 13 and b is 3, then we have the following equality,

-13=(-5) times 3, which is -15 + 2.

And so q here is equal to -5 and r is equal to 2.

And one more example.

Consider a to be equal to 12, and b equals 4,

then 12 is 3 times 4 + 0.

And here the remainder r is 0, q is equal to 3, and a is divisible by b.

So let's get some more intuition.

How do numbers that give the remainder 1 when we divide them by 7 look like?

Let's look at them, at the number line.

So they all have the form a equals to q times 7,

we divide it then by 7, plus 1, the remainder is 1.

And q here is arbitrary integer number.

It can be 0, 1, 2, 3 and so on, and minus 1, minus 2, minus 3, and so on.

Okay, so which numbers have this form?

So one simple example is for q = 0, then a = 1, well, here is 1.

Now, we have a sequence of numbers for positive q.

We have 7 plus 1, so for q equals 1,

we have 2 times 7 plus 1 for q equals 2, which is 15.

Then we have 22, and so on.

Note that each next number is by 7 greater than the previous one.

Finally, for -q, we have another sequence of numbers.

For q = -1, we have -7 plus 1, which is minus 6.

For q = -2 we have -2 times 7 + 1, which is -13.

And then we have -20, and so on.

So note that here again, each next number is smaller than the previous one by 7.

So we have a sequence of numbers.

And note that between two adjacent numbers the distance is 7.

So each 7th number on the line has a remainder 1.

And that's how we look like.

And in general, if you consider the numbers that give some

fixed remainder r when we divide them by b,

then in general we have the form a = q times b + r for all possible q.

And one example is for q equals 0, this is just the remainder itself is equal to r.

And then we have a sequence for positive q,

r + b, r + 2b, r + 3b, and so on.

So each next number is greater than the previous one by b.

Then we have a sequence for negative q, q = -1, -2, -3, and so on.

And the sequence is r-b, r-2b, r-3b.

Each next number is smaller by b than the previous one.

And so again, the distance between adjacent numbers

that give the remainder r when we divide them by b is b.

And so each bth number has the remainder r.

Let's discuss briefly why this is always possible,

why we can always divide a by b with the remainder, why such q and r exists.

And the intuition is simple.

We have already mentioned that we can just do the following.

We can take a group of a objects and we can form groups of size b one by one.

And in the end we will be left with some amount of objects

that is not enough to form a new group.

And then the number of remaining objects is r and the number of groups is q, so

intuition is simple.

So we can restate it slightly more formally.

So what we can do, we have a number r and we can subtract b from it.

We can subtract it once again from the result, and so on.

So we can repeatedly subtract b from our number,

until we are left with a number which is less than b.

And then the remainder will be r, the resulting number

we are left with will be r and the number of subtractions we have made will be q.

And know that r is less than b, because

r is not enough to subtract b once again and to stay within nonnegative numbers.

What happens if a is negative?

So here in this intuition, in this explanation, a is positive.

What happens if a is negative?

It's also simple, just instead of subtracting b from a,

just add b to a until we get a positive number.

And then this positive number will be r, and the number of additions will be q.

Now we have introduced the new notion, divisibility with the remainder.

And there's a simple connection of this notion to the notion of divisibility.

And here it is.

If you have two integers a1 and a2 and they have the same remainder when

we divide them by b, if and only if the difference is divisible by b.

So here is the connection, and let's prove it.

So suppose a1 and a2 have the same remainder.

Then a1 = q1 times b + r, a2 = q2 times b + r.

So let's consider the difference and note that the difference r and r cancel out.

And the difference is q1 minus q2 times b.

And just by definition, so we have the difference is b times some integer number.

So just by definition, we divide the difference of a1 and a2.

Okay, so in the other direction.

Suppose b now divides the difference, a1 minus a2.

Then this means that there is some k that a1 minus a2 is equal to k times b.

And now it took us some remainder when we divided by b,

so it has some form a2 = q1 times b + r for some r.

And then we can substitute a2 into the first equality,

and then we have that a1 = a2 + k times b.

And then a1 is just equal to b times some number q1 + k + r.

And this is exactly the form for division with remainder,

and r here is the remainder.

So the remainder of a2 when we divide a1,

when we divide it by b is the same as

the remainder of a2 when we divide it by b.

[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