b (mod n)Modular arithmetic is simply arithmetic that is restricted to a finite set of elements. For our purposes, that set of elements will be the set of all non-negative integers less than some integer n (greater than 1) where n is called the modulus of the set. This is just a fancy way of saying that our set consists off all the integers from zero up to (but not including) n.
It is pretty common to refer to this set, and operations performed on it, as being in the "modulo n world", often shortened to just "mod n world".
For instance, the mod 11 world would consist of the set {0,1,2,3,4,5,6,7,8,9,10}.
The normal arithmetic operations, such as addition, subtraction, multiplication, and exponentiation, that we are already very comfortable with have their direct equivalents in a mod n world. Division, on the other hand, is an undefined operation in modular arithmetic. There is also a new operation, called reduction, that we have available to us - the name might not be familiar, but you will soon see that the operation itself is an old friend.
Most people were introduced to the concept of multiplication and division early in their grade school career (second or third grade) and probably learned them before being introduced to fractions or decimals - they initially only worked with integers. Since we are once again restricting ourselves to just integers, in some respects we are also falling back on the earliest definitions of multiplication and division that we ever worked with.
For instance, you might dimly recall when, after mastering multiplication as being nothing more than repeated addition, you were introduced to division. They might have asked something like, "What is 30 divided by 5?" After letting you sit there with a vacant stare for a few seconds, they explained that this meant, given a group of 30 items, how many groups of 5 could be removed from it. The answer, of course, was 6. Somewhere around this time it was probably pointed out that division was "the opposite" of multiplication - that another way of phrasing the same question was, "The result of 30 divided by 5 is simply the number that we need to multiply 5 by in order to get 30." While it would probably be several more years before this was explained in more rigor, you had just been introduced to the concept of a multiplicative inverse.
This new operation, division, was a new concept and took some getting used to but, soon, you had mastered it, or so you had thought. Up to that point every division problem you had been given had an integer answer and you may not have even wondered if anything else was possible. But eventually, someone asked you something like, "What is 30 divided by 7?" You probably had a bit of a panic attack as your knowledge of what multiplication and division were up to this point failed to yield an answer. But then they explained the concept of a remainder - that the answer had two parts to it. If, after removing as many full groups of 7 from the initial group of 30 as possible, there are any items left over you call that the remainder. You probably wrote the answer something like:
30 / 7 = 4 r 2
At this point they probably started labeling the different parts of the equation: the 30 was called the dividend, the 7 the divisor, the 4 the quotient, and the 2 the remainder. One of the rules you probably learned was that the remainder had to be less than the divisor since otherwise you could have, and should have, used a larger quotient.
As you can see, this type of division is a very old friend and, if you think about it, you actually use the concept of a remainder fairly often in day-to-day life. For example, you have been given 30 tickets for amusement park rides that need to be distributed among 7 people. Without even thinking about it one of the first questions that would probably come to mind is, "How many tickets are going to be left over?" The answer, of course, is 2.
A more mathematical way of stating this would be, "What is the remainder of 30 divided by 7?" Notice that this particular question doesn't ask how many tickets each person gets. We may not care and we don't necessary need to figure that out, even to find the remainder. For instance, if we have 72154 tickets to distribute to 1000 people, how many will be left over. By inspection you can tell that the answer is 154.
In modular arithmetic, we are going to frequently be asking this same question, we will just be using slightly different terminology.
Our new way of saying, "What is the remainder of 30 divided by 7?" is, "What is the residue of 30 reduced modulo 7?" This is frequently shorted even further to just, "What is 30 mod 7?"
As an expression, this would be written as
30 mod 7 = 2
Most programming languages support the reduction operator (almost always called the modulo operator or modulo division operator).
In C, it is the percent sign:
m = 30 % 7; // C statement that will store the value 2 in the variable m.
In Excel, the function MOD() is available. The following formula would store a result of 2 in a cell:
= MOD(30,7)
A more general way of looking at modular reduction is to consider the following definition:
The residue, r, of an integer, a, modulo n, written as
r = a mod n
is that value of r such that
0 ≤ r < n
and
a = k*n + r
Notice that one thing this definition does is make this operation very well defined for any integer a, even negative ones (we are still restricting n to be an integer greater than 1). A practical way of thinking of this is that a number's residue in a mod n world is obtained by simply adding or subtracting n as many times as necessary to obtain a result that is within the mod n world.
We have already determined that 30 mod 7 is 2. But so is 44 mod 7 and -5 mod 2. Does this mean that 30, 44, and -5 are all equal? No, they aren't "equal", but for nearly all uses in a mod 7 world they are equivalent. We say that they are "congruent modulo 7".
In fact, our claim that our mod n world only has n elements is not really true. Every integer belongs to this world. All of the integers that are congruent modulo n to each other are said to form a congruence class modulo n (also known as an equivalence class). If we know the behavior of one member of the class, then we know the behavior of every member of the class. Every integer belongs to exactly one of just n such classes. We can pick any member of a class to server as the class representative for that class. The class representative is also known as the residue of the class. We then define our modulo n world by building up a complete set of residues modulo n and then defining how all of our available operations operate over that set.
Technically, we could have chosen any of the integers from each congruence class to serve as the residue for that class. But then we would have had to be more abstract in defining our reduction operation: reducing an element modulo n simply means to replace the element with the residue of the congruence class that the element is a member of.
For our purposes, however, life is simply much easier if we define the residues to be the first n non-negative integers. Much simpler.
Notice the differences between the following two statements:
a = b mod n
a
b (mod n)
The first is an expression that invokes the mod operator (modulo reduction operator) and evaluates to the residue of the congruence class to which b belongs. Unless a is also equal to this same residue, the statement is false even if a and b belong to the same congruence class.
The second merely states that a and b belong to the same congruence class without respect to whether either of them happen to be the residues of that class.
From a practical standpoint, notice that the first expression shows "mod" as being an operator with two operands, one to the left of it and one to the right of it. The congruence expression, on the other hand, places the "mod n" in parentheses and you can think of it as simply being a note written off to the right of the expression indicating what what modulus applies. If you try to interpret the latter as an operator, you will immediately see that you are missing an operand.
This can be a pretty confusing distinction, especially since it is easy to be pretty sloppy with the notation and still get your point across.
Here are some examples that might make things a bit clearer:
5 (mod 7) 12 (mod 7) (9 mod 7) - (12 mod 7) (mod 7)Any integer that is evenly divisible by the modulus will have a residue of zero since if
a = kn
then
a = k*n + 0
and, by definition, the residue of a is therefore 0.
As in normal arithmetic, zero (or any other element of the congruence class containing zero) is the identity element and exhibits the following behavior.
a + 0
a (mod n)
There are a few different ways to define addition, some of which are very abstract. Since we will not be doing anything that relies on a formal definition, it is adequate to state that addition in modular arithmetic works the same as in ordinary arithmetic.
Given the expression
c = (a + b) mod n
we could, of course, evaluate it directly. But we can also invoke the definition of a residue as follows:
a = kan + ra
b = kbn + rb
Where ka and kb are appropriate integers and ra and rb are the residues of a and b respectively. Hence
c = ( kan + ra + kbn + rb) mod n
c = ( (ka+ kb)n + (ra + rb) ) mod n
Since (ka+ kb) is simply another integer, we have
c = (ra + rb) mod n
Even though ra and rb are both residues (i.e, less than n) their sum may or may not be. So we still have to perform a final modulo operation.
We also have, by definition,
ra = a mod n
rb = b mod n
Combining all of this, we get the following property of modular addition:
(a + b) mod n = ((a mod n) + (b mod n)) mod n
In a loose analogy to the distributive properly of multiplication over addition, we can think of the modulo operator being distributable over addition with the exception that we must retain the original modulo operator in place. Perhaps it would be more accurate to describe it as 'replicating' over addition, but we will use the term 'distribute' - just remember to perform the final reduction.
Aside
For those that are interested, one formal way to define addition that is pretty easy to follow is along the following lines:
The complete set of residues modulo-n are ordered (the order is arbitrary). We could define a set of residues as:
complete set of residues: {C, R, Y, P, T, O}
where we have just picked five symbols at random (they look random, don't they?). One of them is picked as being the "identity element" (we'll pick the 'Y' - we've picked something other than the one at the beginning of the list just to highlight that it doesn't matter) and, by definition,
a + Y
We define a second operation, the successor operator, such that for each element of the set, the successor operator returns the next element in the set. It is for this reason that the set must be ordered. We'll use the apostrophe as the successor operator and, from this, we see:
C' = R; R' = Y; Y' = P; P' = T; T' = O
The operator can be cascaded, hence R'' = (R')' = Y' = P and C'''' = R''' = Y'' = P' = T.
But what about O'? What is that? You've probably already guessed that O' = C. But what may not be obvious is that this one single difference is the sole difference between ordinary arithmetic (over the integers) and modular arithmetic. In ordinary arithmetic the set of "residues" is the complete set of integers which continues to infinity in both directions. As a result, the successor operator always returns an item further to the right in the list. In modular arithmetic, the successor to the end of the set is the beginning of the set. This wrap-around characteristic is what results in the existence of the congruence classes since.
Now we can define addition as follows:
a + b' = (a + b)'
For instance, let's say we want to add P + C. We need to write this in the form above which would be
P + C = P + O'
The chain from this to our answer is then
P + O' = (P + O)' = (P + T')'
(P + T')' = (P + T)'' = (P + P')''
(P + P')'' = (P + P)''' = (P + Y')'''
(P + Y')''' = (P + Y)'''' = P''''
This last occurs due to the definition of our identity element. We can now walk up the sequence:
P'''' = (P')''' = (T)''' = (T')'' = (O)'' = (O')' = (C)' = C' = R
Hence, we have
P + C = R
If this mathematical world was one that we were going to be spending a lot of time in, then this would simply be a "fact" that we would memorize (just as we memorized that 7 + 8 is 15 a very long time ago) and our calculators would return R when you added P and C.
What if we wanted to replace the arbitrary symbols we chose for this world and replace them more familiar integers? That is easy to do, as long as we make sure that the third element in the sequence remains our identity element and that the ones before and after it are properly ordered.
complete set of residues: {C, R, Y, P, T, O} => {-2, -1, 0, 1, 2, 3}
Our expression would then get translated as
P + C = R => 1 + -2 = -1
Which is what we would expect.
The definition of the additive inverse under modular arithmetic is essentially the same as for normal arithmetic.
The additive inverse of a is written as -a. Notice that, up to this point, we have not defined subtraction. The horizontal line in from of the a is not a minus sign or a subtraction operator. It is the "negative sign", also known as the "unary negation operator". For the moment, think of -a and being a distinct symbol that can't be broken up.
by definition, the sum of a number and it's additive inverse is congruent to the additive identity element. In other words, -a is the additive inverse of a if and only if
a + -a
0 (mod n)
Since we can add arbitrary multiples of the modulus to either side of the equation, we can rewrite this as
a + -a
n (mod n)
The definition of subtraction under modular arithmetic is identical to its normal arithmetic counterpart - namely subtracting a number is the same as adding its additive inverse.
a - b = a + -b
Going back to the definition of the additive inverse, we can quickly derive the more common and useful expression for finding "negative numbers" in a modulo-n world.
0
kn (mod n)
0 + -a
kn + -a (mod n)
-a
kn + -a (mod n)
-a
kn - a (mod n)
Usually, when we want to find the negative of a number, we use the above relationship with k = 1.
-5 mod 7 = (7 - 5) mod 7 = 2
-1 mod n = (n - 1) mod n = n-1
Not surprisingly, the modulo operator distributes over subtraction just as it does addition
(a - b) mod n = ((a mod n) - (b mod n)) mod n
Continuing the theme of few surprises, modular multiplication has the same identity element as ordinary multiplication and the rules are identical.
(a)(1)
a (mod n)
A very similar development can be used to show that the modulo operator replicates over multiplication.
Given the expression
c = (ab) mod n
we could, of course, evaluate it directly. But we can also invoke the definition of a residue as follows:
a = kan + ra
b = kbn + rb
Where ka and kb are appropriate integers and ra and rb are the residues of a and b respectively. Hence
c = ( ( kan + ra )( kbn + rb) ) mod n
c = ( (kakb)n2 + (rakb + rbka)n + (rarb) ) mod n
We can then replicate the modulo operator over the sum of terms yielding
c = ( ((kakb)n2 mod n ) + ((rakb + rbka)n mod n) + ((rarb) mod n) ) mod n
Since the first two terms contain n as a factor their residues are zero, leaving
c = ( (rarb) mod n) ) mod n
The second modulo operation is redundant and can be removed.
c = (rarb) mod n
We also have, by definition,
ra = a mod n
rb = b mod n
Combining all of this, we get the following property of modular addition:
(ab) mod n = ((a mod n)(b mod n)) mod n
The definition of a multiplicative inverse in modular arithmetic is the same as in ordinary arithmetic. The multiplicative inverse of a is written as a-1 and, by definition, the product of a number and it's multiplicative inverse is congruent to the multiplicative identity element.
(a)(a-1)
1 (mod n)
While the definition is the same, there are few other similarities. In ordinary arithmetic, multiplicative inverses are intimately tied to the operation of division. However, in modular arithmetic there is no division operation.
To find the multiplicative inverse, consider the definition both of the inverse and of modulo reduction.
(a)(a-1)
1 (mod n)
(a)(a-1) = (kn + 1)
In ordinary arithmetic, the set of integers doesn't permit multiplicative inverses while in the set of real numbers every number except zero has a multiplicative inverse. Modular arithmetic exists somewhere in between. Except for zero, which never has a multiplicative inverse, all other elements may or may not have one.
Example:
7-1
4 (mod 9)
because
(7)(4) = 28 and 28
1 (mod 9)
However, 6 has no multiplicative inverse in a modulo 9 world because no number, when multiplied by 6, will reduce to 1.
Why not? What determines whether a number does or does not have a multiplicative inverse?
Let's consider the case where a number has a factor in common with the modulus, if this common factor is c, then the number can be written as a = cb and the modulus can be written as n = cm, where b and m represent the remaining factors in each that are not shared by the other. We can therefore write our defining expression as:
(a)(a-1)
1 (mod n)
Now multiply both sides by m (the factors shared by a and n).
(mcb)(a-1)
m (mod n)
However, since n = cm, the factor mcb is a multiple of n and hence the left side is congruent to zero. Hence, if m is not congruent to zero, the relation is false and that means that the original expression is false - the conclusion being that there is no value for a-1 which can serve as the multiplicative inverse for a.
Under what conditions can the statement be true? Only if m is congruent to zero. We know m can't be zero, since that would make n also equal to zero. Nor can it be larger than n since c must be an integer and this would result in n being greater than n. The only other alternative is for it to be equal to n, which means that c must be exactly equal to 1. But since c is the factor shared by a and n and, if it is 1, then they share no factors in common - they are relatively prime.
The conclusion is that any non-zero a has a multiplicative inverse modulo n if and only it is relatively prime to n.
Modular exponentiation obeys all of the normal rules of ordinary exponentiation. Particularly:
abac
a(b+c)
(mod n)
and
(ab)c
abc
(mod n)
Like the other operations, it is also permissible to take the modulo operator "inside" since
a2 mod n = ((a)(a)) mod n
a2 mod n = ((a mod n)(a mod n)) mod n
a2 mod n = (a mod n)2 mod n
One thing that we can't do is reduce the exponent modulo n. We can, however, reduce it modulo the m where m is the number of positive integers less than n that are relatively prime to n.
ae
ae mod m
(mod n)
The proof of this, as well as the development of the how to find m given n, is present in much more detail in a separate page devoted to modular exponentiation.
The simplest way (conceptually, at least) to evaluate an expression that involves modular arithmetic is to evaluate the expression normally and then, where necessary, reduce the result modulo n. For example:
a = ( ((42 + 20) - 45)*6 + 50 ) mod 7
a = ( ((16 + 20) - 45)*6 + 50 ) mod 7
a = ( (36 - 45)*6 + 50 ) mod 7
a = ( (-9)*6 + 50 ) mod 7
a = ( -54 + 50 ) mod 7
a = ( -4 ) mod 7
a = 3
In fact, technically this is the only correct way to evaluate this expression because all of the addition, subtraction, multiplication, and exponentiation operations are the normal ones. Their is a single modulo operator and it is not invoked until the expression in parentheses to the left of it is evaluated.
The properties developed above can significantly streamline the evaluation of modular arithmetic expressions. In this section we'll attempt to demonstrate some of the ways they can be exploited. More than anything, the purpose of these examples is to make you aware of some of the games that can be played. It's surprising how easy it can be to work with quite large numbers using only pencil and paper and while doing most of the math in your head.
Because the modulo operator distributes over addition, subtraction, and multiplication identically, we can simply reduce any piece of an expression that uses only these operators as we see fit.
We'll use the same expression that was used for the brute force example,.
a = ( ((42 + 20) - 45)*6 + 50 ) mod 7
First, evaluate the exponential since we haven't looked at how it behaves - that will come later. Of course, you don't need to explicitly write out the distribution of the mod operator. That is done here only to highlight what is being done. Any time you see a number that can be reduced, feel free to do so - with the exception of exponents, the rules are different for them.
a = ( (((16 mod 7) + (20 mod 7)) - (45 mod 7))*6 + (50 mod 7) ) mod 7
a = ( ((2 + 6) - 3)*6 + 1 ) mod 7
a = ( 5*6 + 1 ) mod 7
a = ( (30 mod 7) + 1 ) mod 7
a = ( 2 + 1 ) mod 7
a = 3
An often overlooked trick is to expand the expression being evaluated such that portions of it vanish. For instance
a = ((19)(17)) mod 30
The two factors are already residues, so it might appear that we simply have to multiply 19 by 17 and reduce the result. But what if we exploit the fact that 30 has several factors and that we can get those factors from either number and that the residues of the resulting terms vanish.
a = ((20 - 1)(15 + 2)) mod 30
a = ((20)(15) + (-1)(15) + (20)(2) + (-1)(2)) mod 30
The first term is divisible by 30 and thus vanishes, leaving
a = (-15 + 40 + -2) mod 30
The 40 can be reduced to 10, but doing so would leave us with a negative result - it will be easier to just go ahead and evaluate the expression without further reductions until, if necessary, the very end.
a = 23 mod 30
a = 23
Performing addition and subtraction is fairly easy for most people - and it is fairly easy for most processors. As a rule, you expect that algorithms that exchange multiplication operations for addition operations and, especially, ones that avoid division operations are more efficient both for humans and for computers. That's not always true and some hardware implementations are specifically optimized to perform multiplication efficiently.
Where that is not the case, especially when you are evaluating things by hand, exploit the fact that it is easy to perform multiplication by integer multiples of the number base - you just shift the decimal point.
For instance, if you had to evaluate
a = 372634 mod 212
You could immediately recognize that you can subtract 212*1000 = 212000 from a.
a = 160634 mod 212
Multiplying large numbers by single digit numbers, especially 2 or 3, is pretty easy as well. So, exploiting that, you might subtract 212*200 = 42400
a = 118234 mod 212
You could then subtract 212*30 = 6360
a = 111874 mod 212
Since we have already the '424' from a prior step, we can easily see that we can multiply it by 2 and subtract off 848
a = 111026 mod 212
Since 5*212 = 1060, we can subtract 106000 to get
a = 5026 mod 212
At this point a good choice would be 212*20 = 4240, but adding 212 first makes it even easier
a = ((5026 + 212) - 4240) mod 212
a = (5238 - 4240) mod 212
a = 998 mod 212
We can get rid of most of the rest of it by subtracting off another 848 leaving
a = 150 mod 212
which can't be reduced and thus our final answer is
a = 372634 mod 212 = 150
This technique permits hand reduction of values very quickly. All of the above work was performed by inspection, with all computations done mentally without even the use of pencil and paper.
This technique can also be highly formalized and turned into a cookbook algorithm that lends itself to either hand or computer implementation.