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

Â