0:00

Modular arithmetic is little more than working with the remainders left over

after performing normal arithmetic operations and

dividing by a particular divisor known as the modulist.

We actually do this all the time.

For instance, if it is currently 2:30 PM and

I have to leave in 45 minutes, I don't say that I need to leave at 2:75 PM.

Instead, I add 45 to 30, get 75, and for

the minutes I keep the remainder of this number after dividing by 60.

The reason that I can reduce 75 by 60 is because

the world of minutes only has 60 elements.

We call this a modulus 60 system.

0:38

In this lesson, we're going to look at the fundamentals of modular arithmetic

including the defining relationship for modular arithmetic, the concept

of residue and congruence classes, the distinction between modular congruence and

modular reduction, the modular operations available to us, and

when we can and can't perform modular reductions.

Finally, we'll look at a few examples,

including a generic way to efficiently determine if one number is divisible

by another without performing the actual division.

1:09

Any integer, positive, negative, or

zero, can be written in the form of a product of two integers, plus a third.

This is the defining relationship for modular arithmetic.

We use the same names as in normal arithmetic.

n is the dividend.

d is the divisor, though in modular arithmetic,

we usually call it the modulist.

q is the quotient, but

in modular arithmetic, we usually don't care about it.

And r is the remainder, which we call the residue in modular arithmetic.

Even if we specify the divisor, there are an infinite number of remainders.

We can pick any integer for the quotient and get the corresponding remainder.

Here are just two examples for a dividend of 37 and a divisor of 13.

By convention, we typically choose the value of the quotient

that makes the remainder a non-negative integer strictly less than the divisor.

We are guaranteed that such a choice exists for any strictly positive divisor.

Again, we seldom care what the quotient actually is,

we simply perform the division like we did in grade school and only keep the residue.

2:15

Using our defining relation, we can let the quotient take on any integer value and

collect all of the resulting residues into a set known as a residue class.

Given a particular modulus, every integer belongs to exactly one residue class.

The number of residue classes is equal to the modulus.

Within this modular world, all members of a residue class

could be replaced by any other member and still behave the same way.

Thus, we say they are congruent or equivalent.

So other common names for the residue classes are congruence classes or

equivalence classes.

For instance, in a mod 13 world, -2, 11, and 24 are all congruent.

This is not to say that 11 and 24 are equal.

They aren't and we don't claim that they are.

They are congruent within this world.

When we evaluate an expression,

we end up with some value that is a member of some residue class.

We typically replace this value with a particular member of the class

known as the class representative.

We could actually pick the class representative at random, but

that would make our lives needlessly complicated.

Instead, the normal convention is to use the smallest non-negative integer of

each class as the class representative.

This convention is known as the least residue system.

This is not always the case.

For instance, if you're familiar with two's compliment representation for

signed integers, this is merely a modular world in which

half of the class representatives are negative.

3:44

If two integers, a and b, are in the same congruence class,

then they have the same remainder when written using our defining relationship.

By subtracting it, we get the very useful result that two integers are congruent

mod-N if their difference is an integer multiple of the modulus.

We indicate the congruents of two numbers with the congruent sign

which looks like a three-barred equal sign.

And with the modulus written to the right in parenthesis, essentially is a note,

indicating what module or world these two integers happen to be congruent in.

This is like saying that the two numbers are equal, but congruent and

equal are not the same thing.

Again, 11 and 12 are not equal, but they are congruent modulo 13.

Like the divisibility expression, this is a predicate claim and not an operation.

There's no mathematical operator here, so no operation gets performed.

If we want to actually reduce a number to its class representative,

we use the mod operator.

Here mod is a binary operator, and

it has two operands, the dividend on the left and the divisor on the right.

Sometimes we use the percent sign because this is the remainder operator supported

in most high level programming languages.

Here, we do use the equal sign because the expression on the left

evaluates to the exact same value as the expression on the right.

Also, note that this is just an integer expression,

there's no mod N world involved.

When working in a mod N world, one approach is to simply ignore the modulus

until the end, and then reduce the final result by the modulus.

However, when working with problems of cryptographic interest,

our modulus alone may have hundreds or even thousands of digits.

And this approach could easily result in our needing to work with numbers having

millions of digits.

While possible in principle, using what are called big number libraries, the speed

associated with such computations is prohibitively slow in practice.

So we need to find a way to speed things up,

while still getting the same final answer.

One of the simplest and most powerful techniques is simply to

reduce the computation by the modulus after every step of the computation.

For addition and subtraction, our defining relationship requires that the residue of

the sum of two integers is simply the sum of the residues.

Similarly, for multiplication, our defining relationship requires that

the residue of the product of two integers is simply the product of the residues.

One thing to keep in mind is that even if we perform reductions along the way, we

still need to perform a final reduction at the end because any operation, other than

mod itself, has the potential to yield a value other than the class representative.

6:23

Notice that we haven't said anything about division.

Let's make the assumption that division is defined in a modular world.

Operating in a modular world means that we can always replace

any number with any other number in the same residue class

since all such members are congruent in that world.

So, let's say that we have 15 divided by 3 in a mod 6 world.

The concept of congruency requires that 15 divided by 3 be congruent

to 3 divided by 3 since 15 and 3 are both congruent to 3 mod 6.

But this requires that 5 be congruent to 1 mod 6, which we know is not true.

Since all members of a residue class must be congruent, and

here we have an example where they aren't, we have a contradiction.

We therefore conclude that our assumption that division is

defined in a modular world must be incorrect.

This is a critically important point.

We are easily tempted into performing division on those integers expressions

that produce energy results without realizing that in doing so,

we may well make it so that we can't later performing modular reduction and

expect the results to be valid.

7:39

What about exponentiation?

Well, this has to be allowed since exponentiation is merely repeated

multiplication.

It turns out that we have to be a bit careful here.

To demonstrate that this is the case,

consider the case of 3 raised to the 14th power reduced mod 7.

If we perform all of the arithmetic before reducing the result, we get 2.

But if we reduce the exponent mod 7,

the work becomes trivially easy, it just happens to be wrong.

Because of Euler's totient theorem,

it turns on that in a mod-7 world, the exponents live in a mod-6 world.

With this in mind, we can perform the correct reduction of the exponent and

easily get the correct result.

Don't worry about knowing how to figure out what world the exponents live in,

we'll explore that in depth in a future lesson.

The fact that the exponents do live in a different modular world is the basis for

most common public key encryption schemes in use today, and

that serve as the cornerstone of today's e-commerce.

So let's see if we can use the little bit that we've learned so

far to answer some seemingly tough questions.

We know that n factorial is the product of all positive integers less than or

equal to n.

After evaluating n factorial for

anything other than very small values of n, we have a number with lots of digits.

For instance, 50 factorial has 65 digits.

If we were to sum up all of the digits,

we would end up with a much smaller number having two or three digits.

If we sum up the digits in that number, we get yet a smaller number.

If we continue doing this, we eventually get to a single digit number.

What is that number?

9:18

You might want to pause the video here and ponder this.

As you might have discovered, the answer is 9 because any factorial of 6 or

more has both 3 and 6 as factors and hence is divisible by 9.

We have a widely known divisibility rule that if you sum up all of the digits in

the number and the result is divisible by 9, then the number is divisible 9.

We can continue this process until we have a single digit number, and

the only two single digit numbers divisible by 9 are 0 and 9.

But we can't add single digit numbers and get 0, unless all of them happen to be 0.

So, the only possible answer is 9.

You might be arguing that this has nothing to do with modular arithmetic, but

that's only because you were never shown where that divisibility rule comes from.

Consider an n digit number.

If that number is divisible by 9, then its residue mod 9 must be 0.

We can write this number as a sum, in terms of the individual digits,

di, multiplied by the weight associated with that digit's place,

10 raised to the ith power.

We can perform the mod 9 reductions where convenient,

which means that we can reduce the 10 mod 9 to get 1.

Since 1 raised to any power is 1,

it goes away leaving us with the familiar result that for

a number to be divisible by 9, then the sum of its digits must be divisible by 9.

We can generalize this to an arbitrary number base by noting that the base,

B, is congruent to 1 mod B- 1.

Hence in base B, a number is divisible by B-1

provided the sum of its digits is divisible by B-1.

We have lots of divisibility rules.

For instance, a number is divisible by 6 if it is even and

also divisible by three while it is divisible by 2 if the last digit is even.

Others included being divisible by 8 if the last three digits are divisible by 8,

or it being divisible by 5 if the last digit is either a 0 or a 5.

The first of these rules, the one for divisibility by 6 works in any number base

while the rest of them only work in base 10 or

possibly in specific other bases by coincidence.

You might spend some time pondering why some rules are base specific and

others aren't.

The answer isn't too mysterious.

11:41

But how do we determine if a number is divisible by 7 or

19 without actually performing the division?

And doing so in a way that is independent of the number base being used?

These rules seem haphazard and unique to each divisor, and

we don't have a one size fits all divisibility rule.

Can we use modular arithmetic to find one?

Let's first look at a way to build up a value from its digits,

starting with the most significant first.

We'll use the base 10 value 5,432 as a simple example.

Start by initializing a running sum to 0, and then add the first digit.

Of course, if we were doing this by hand, we'd skip this step.

But we want to develop an algorithm that can be implemented easily in a program.

If there are any more digits, we multiply the running sum by the base and

add the next digit.

We keep doing this until we have added the final digit.

To see if this number is divisible by d, we merely reduce the running sum by d

as frequently as we want, making sure that we do it at least once at the very end.

Notice that if our divisor is less than or equal to the base, we can reduce

both the individual digits and the number base itself by d right up front.

Do you see how if the divisor is equal to the base we immediately get our familiar

rule, that a number is divisible by 10 if the last digit is 0.

This technique is more powerful than it might appear.

First, it is a simple algorithm that lends itself to

a simple implementation in a program.

Second, regardless of how big the number is the largest our running sum can

ever get is less than the product of the base and the divisor.

If we are working in base two, ie binary like most computers do,

then we never have to work with any value greater than twice the divisor.

This means that however many bits are required to store the divisor,

we only need one additional bit to be able to store our running sum.

Thus we have a very spaced efficient algorithm.

13:39

Finally, the speed of the algorithm is order n,

where n is the number of bits needed to represent the original value,

which is order log v, where v is the original value itself.

Thus, we have a very time efficient algorithm.

Now, no one is claiming that this is as efficient as looking at

the last digit to determine if a number is even or odd.

Special case algorithms are almost always faster than general purpose ones, but

as general purpose algorithms go, this one's pretty good.

14:09

In this lesson, we've taken a whirlwind tour of the basics of modular arithmetic.

We started with the defining relationship that everything is based on, and

developed a notion of residue and congruence classes.

We made the distinction between modular congruence and modular reduction.

And showed that addition, subtraction, and

multiplication are allowed modular operations while division is undefined.

We also saw that modular exponentiation is valid,

but that the exponents do not live in the same modular world.

Finally, we used our fledgling knowledge of modular arithmetic to develop

a powerful technique for determining if one number is divisible by another.

Looking ahead in the remainder of this module, we'll look at the analog to

division, which is the notion of multiplicative inverses, and

learn how to find them, at least when they exist.

Later, we will be devoting an entire module to modular exponentiation,

such as its importance