Introduction
Modarithmetic
is the central mathematical concept in cryptography. Almost any cipher from the Caesar Cipher
to the RSA Cipher use it. Thus, I will show you here how to perform Mod
addition, Mod subtraction, Mod multiplication, Mod Division and Mod
Exponentiation. It is a very easy concept to understand as you will see. Use this page as a reference page and open it whenever
you encounter any
modcalculations or modterminology that leave questions behind. So
let's start:
What
is meant by Mod, Modulus and Modular Arithmetic?
“Modulus”
(abbreviated as "mod") is the Latin word for “remainder, residue” or more in “what is left after parts of
the whole are taken”. Thus, "modular" or "mod
arithmetic" is really "remainder arithmetic". More precise:
We are looking for the integer that occurs as a remainder (or the
"leftover") when one integers is divided by another integer.
Let's do three examples:
Example
1:
When 7
is divided by 3 it leaves a remainder of 1. Think of $1 as a left over
after $7 are equally split among 3 people. Surely, there is a mathematical
notation for mod arithmetic: Instead of writing 7 = 3*2 + 1 where 1 is the
integer remainder we will write:
7 mod 3 =
1
which reads as: "7 modulo 3 is 1" and 3 is called the
"modulus".
Sure, this notation does not reveal the $2 that every person gets as his
share. True, however, we are solely interested in the left over part, the
remainder of $1 in our example.
Example 2:
When 8 is divided by 3 it leaves a remainder of 2. Thus, we
write:
8 mod 3 = 2.
Example
3:
When 9
is divided by 3 it leaves no remainder. Thus, we write:
9 mod 3 = 0.
Figure 1:
Arithmetic MOD 3
can be performed on a clock with 3 different times: 0, 1 and 2.
Computations
involving the modulus to determine remainders are called “Modular
Arithmetic”. It was first studied by the German Mathematician Karl
Friedrich Gauss (17771855) in 1801. You may have heard this anecdote about Gauss when
he went to school: His Mathematics teacher tried to keep the bored genius
busy, so he asked him to add up the first 100 integers hoping that he would keep him
quiet for a little while. However, young Karl promptly
responded “5050 and the formula for the sum of the first n integers is
n*(n+1) / 2”. Do you know why?
Great,
we have the principle of Mod Arithmetic straight: To find the remainder
simply divide the larger integer by the smaller integer. This surely works
for large numbers as well: I.e. 365 MOD 7 = 1 (since 365 = 52*7 +1) .
What is the usage of Mod arithmetic?
365 MOD 7 = 1 tells
us that if Christmas will fall on Thursday and we don't have a leap year it will fall on a Friday next year. The same for your birthday
and any other day as well: every week day will fall on the following
weekday the next year. Notice again that we
only care about the remainder 1 and not the completed 52 weeks in a year.
In fact if a year would consist of only 358 or 351 or 15 or 8 days, we would
still have the
same "shift by 1" effect. Apparently, solely the
length of each week (called the modulus) determines the "shift
by 1". What does 366
MOD 7 = 2 explain for leap years? Shift by 2
days.
Congruent
numbers
Integers
that leave the same remainder when divided by the modulus m are somehow
similar, however, not identical. Such numbers are called
"congruent" . For instance, 1 and 13 and 25 and 37 are
congruent mod 12 since they all leave the same remainder when divided by
12. We write this as 1 = 13 = 25 = 37 mod 12. However, they are not
congruent mod 13. Why not? Yield a different
remainder when divided by 13.
Find
5 numbers that are congruent to
1) 7 mod 5
2,12,17,3,10
2) 7 mod 25
32,57,82,18,43
3) 17 mod 25.
42,67,92,8,33
Modular
Arithmetic is also called Clock Arithmetic
The classical example for mod arithmetic is clock arithmetic:
Look at the 12hour clock in your room. You see 12 numbers on the clock.
Here, the modulus is 12 with the twelve remainders 0,1,2,..11. So, when you give
the time you actually give a remainder between 0 and 11. Again, the modulus m=12 is
in charge of these reminders. What time is it 50 hours after midnight? It
is 2 (a.m.) since 50 hours equal 2 full days and 2 hours.
Reduce the following:
1) 40 mod
12
4 2) 50 mod 12
2 3)
50 mod 24
2
4) 40 mod 24
16
5) 100 mod 33
1
6) 1000 mod 33
10
In Modular Arithmetic, we add, subtract, multiply,
divide and exponentiate as
follows:
A) Mod Addition Let's start simple: What time is it
10 hours after 11:00? It is 11+10 = 21 o'clock, and 21 minus the modulus 12 leaves a
remainder of 9, thus 9 o'clock. What time is it 22 hours after 11:00? It is 11+22 = 33 and
subtracting the
modulus 12 repeatedly (which is also called "dividing") yields again 9. Ignoring a.m. and p.m.,
we are performing mod arithmetic on the clock. Let's write the two examples in mod notation:
11+10 = 21 mod 12 = 9 and 11 + 22 = 33 mod 12 = 9.
How to perform Mod Addition:
First add the two numbers,
Secondly, divide the sum by the modulus to compute the remainder.
In "8hourland" where a day lasts only 8 hours, we would add 12
and 9 as follows:
First, 12+9 = 21,
secondly 21 divided by the modulus 8
leaves a remainder of 5 since 21=2*8+5.
How many different remainders does "8hourland" have?
Click
here for a modular clock.
B) Mod Subtraction
Subtraction is performed in a similar fashion:
First subtract,
secondly compute the remainder.
Example 1: 25  8 = 17 MOD 12 = 5 Example 2: 50  11 = 39 MOD 12 = 3 What if we obtain a negative answer? Say it is 2 o'clock
in New York, what time is it in L.A.? Turning the hand on a clock 3 hours
backwards shows that it is 11 o'clock: 2 
3 = 1 MOD 12 = 11
Thus, if the answer is negative, add the modulus you get a positive number. That
number must be between 0 and the modulus.
Example 3: 3  50 = 47 MOD 12 = 1 since  1 + 12 =11.
Example 4: 14  77 = 63 MOD 12 = 9 since 63 + 12 + 12 + 12 + 12 + 12 +
12 = 9. Example 5: 50  11 = 39 MOD 15 = 6 since 39 + 15 + 15 + 15 = 6
C) Mod MultiplicationSince multiplication of positive numbers is repeated
addition it can be reduced to the above mod addition.
How do we compute 5 * 8 MOD 12?
First we multiply: 5 * 8 = 40
secondly we find the remainder: 40 MOD 12 = 4.
A useful shortcut: A mod expert would find the answer to 123 *
62 mod 12 immediately. It is 6. How does she know? Without being a Gauss genius, she
computes 123 mod 12 = 3 and 62 mod 12 = 2 and multiplies those two answers. To
verify this: 123*62 mod 12 = 7626 mod 12 = 6. This computation aid is true for
addition and subtraction as well. Therefore, we may write them as:
3 Computation
Rules for Mod Arithmetic 
1) a + b mod m = (a mod m) + (b mod m) 
2) a  b mod m = (a mod m)  (b mod m) 
3) a * b mod m = (a mod m) * (b mod m) 
Compute the following:
1) 73 + 58 = x mod 12
11 2)
1411  285 = x mod 141
139 3) 74 * 93 = x mod 13
5
4) 33 * 266 = x mod 26
16
5) 2590 * 5253= x mod 26 16
6) 133 * 5202 = x mod 26
6
D) Mod DivisionDivision is the inverse operation of multiplication. This means
that every division question can be answered by answering a "find the missing
number" multiplication question.
I.e. Since 5*8 = 4 MOD 12 dividing by 5 yields
8 = 4/5 MOD 12.
Thus, if I had asked you:
Compute 4/5 MOD 12,
the answer is apparently 8.
Example 1:
To
compute 5 / 7 mod 12, we introduce an x
x = 5 / 7 mod 12 to multiply both sides by 7.
7x = 5 mod 12.
We find x by testing the 12
different remainders 0, 1, ...11.
Trial and error yields x=11 since
7 * 11 mod 12 = 77 mod 12 = 5.
Do these problems:
1) 7 / 5 = x mod 12 11 2) 7 / 11 = x mod 12
5 3) 29 / 7 = x mod 12
11 4) x * 7 = 8 mod 12
8 5)
7
* x = 9 mod 12
3 6) x * 7 = 5 mod 12
11
A Better Division Method
If the modulus is small as above, trial and error will find the answer. But
what if the modulus is large, i.e.
x * 8 = 19 mod
131 ?
Testing each remainder would take a long time. Surely, we could have a computer
do the testing for us, and we would confirm the found answer by performing the
Mod multiplication. Luckily, all this is not necessary as there exists a
straightforward method to perform Mod Division:
To divide i.e. 5 by 7 mod 12, we
first rewrite it as we did above by multiplying both sides by 7: x * 7 = 5 mod
12
To isolate x, we simply multiply both sides by the inverse of 7 mod 12, which is
by chance 7 itself since 7 * 7 mod 12 = 49 mod 12 = 1. Now, we multiply both
sides by 7 which yields x on the left and 7 * 5 mod 12 = 35 mod 12 = 11 on the
right. Therefore,
x = 11 mod 12 or 5/7 = 11 mod 12. Done we are. Looking back at this
method, the only tricky part is how to find the inverse. If we had to do trial
and error, we would not gain anything in comparison to our previous method. It
is the extended version of the Euclidean Algorithm that allows us to find the
inverse mod m in an efficient manner. Click
here for an explanation of the Extended Euclidean Algorithm.
I
also created a Javascriptdemonstration of the Extended Euclidean Algorithm here
which allows you to understand the mechanics involved quickly.
Of course, you don't have to practice this Algorithm, a computer will do this
for us. You do the trial and error method to find multiplicative inverses.
Afterwards, check your answers here:
1) 5 mod 12
5 2) 5 mod 11
9 3)
5 mod 13
8 4) 7 mod
26 15 5) 11 mod 26
19 6) 15 mod 26
7
Try to solve the following 4 challenging problems.
Hint: Let a be 2, 3, 4, etc., compute the inverse a^{1} in each case
and find a pattern.
7) Find a^{1} mod 2a1.
2
8) Find a^{1} mod 2a+1.
2a 1
9) Find a^{1} mod a^{2}1.
a
10) Find a^{1} mod a^{2}+1.
a^{2}+1a
Using the found inverses, now perform the following Mod divisions
yourself. First rewrite the equations as we did in example 1, then compute.
11) 7 / 5 = x mod 12
11 12) 7 / 5 = x mod 11
8 13) 7 / 5 = x mod 13
4
14) 3 / 7 = x mod 26
19
15) 9 / 11 = x mod 26 15
16) 11 / 15 = x mod 26 25
Some Mod Divisions have no
Solution
Unlike the division of real numbers, mod division does not always yield an
answer. The reason for that is that the modmultiplication does not always yield
all possible remainders less than the modulus. Let's investigate this fact. For
example: Using a modulus of m=6, we set up a multiplication table that
displays the multiplications of the remainders 0,1,2,3,4
and 5.
* mod 6 
0 
1 
2 
3 
4 
5 
0 
0 
0 
0 
0 
0 
0 
1 
0 
1 
2 
3 
4 
5 
2 
0 
2 
4 
0 
2 
4 
3 
0 
3 
0 
3 
0 
3 
4 
0 
4 
2 
0 
4 
2 
5 
0 
5 
4 
3 
2 
1 
Two Observations: 1) Some divisions have no
answer
The rows created by the remainders 0,2,3,4 do not contain all six remainders.
Consequently, some divisions have no answer. I.e. consider division by 2:
4 / 2 = 2 mod 6 since 2 * 2 = 4 mod 6.
2 / 2 = 1 mod 6 since 1 * 2 = 2 mod 6.
However, 3 / 2 = x mod 6 has no answer x since there exists no
remainder x such that 2 * x yields 3 mod 6.
Also, 5 / 2 mod 6 has no answer. Why not? In fact no odd integer could
possibly be divided by 2 mod. If, however, we use a modulus of 7 any odd (and
any even) integer less than 7 can be divided by 2. Explain why by using the
multiplication for mod 7 below. 2) Some divisions
have many
answers
I.e. 4 / 2 = 2 mod 6
since 2 * 2 = 4 mod 6,
also 4 / 2 = 5 mod 6
since 2 * 5 = 4 mod 6. Even seemingly odd divisions like
0/3 or even worse 0/0 are legal mod 6. Both have the answer 2. Explain
this.
If we don't limit us to the six
remainders as answers, we actually find an infinite number of answers. Notice
that also 2*8, 2*11, 2*14, 2*17, ... yield 4 mod 6. Consequently, when dividing
4 by 2 mod 6 8,11,14,17,...are correct answers as well. Thus, don't be surprised if your partner finds a different answer
than you. It might be just as correct as yours.
Exercise: Give five answers to 3 / 3 mod 6. Is the obvious answer
"1" correct? Exercise
1:
Create mod multiplication table using modulus 6,7,8 on paper. Afterwards, verify
their correctness by creating these tables at the right. Exercise
2:
For
encryption purposes, we prefer to have unique answers. By choosing the modulus
in a certain way, can we assure unique answers? How shall we choose the modulus?
Come up with a guess why division by 1 and 5 yields unique answers mod 6 (when restricting us to the
six remainders 0,1,2,3,4 and 5). Observe from your tables created in exercise 1 the following facts:
a) Division by 1,3,5 and 7 yields unique
answers mod 8, b) division by 1,2,4,5,7 and 8 yields unique answers mod 9,
c) division
by 1,2,3,4,5 and 6 yields unique answers mod 7.
Before you continue
reading write down your guess when mod division yields unique answers and when
not.
Answer:
If
the number we are dividing by is relative prime to the modulus (that means their
only common divisor is 1) the divisions yield unique answers. Consequently, if
the modulus is a prime number (hence all integers less than the prime number are
relative prime) all divisions yield unique answers. Example:
If the modulus is m=7, the divisions yield unique solutions.
* mod
7 
0 
1 
2 
3 
4 
5 
6 
0 
0 
0 
0 
0 
0 
0 
0 
1 
0 
1 
2 
3 
4 
5 
6 
2 
0 
2 
4 
6 
1 
3 
5 
3 
0 
3 
6 
2 
5 
1 
4 
4 
0 
4 
1 
5 
2 
6 
3 
5 
0 
5 
3 
1 
6 
4 
2 
6 
0 
6 
5 
4 
3 
2 
1 
Perform
the following divisions. Which one has multiple answers between 0 and the
modulus? Find them if they exist. Which division has a unique answer? Which
division has no answer?
1) 7 / 4 = x mod 12
(or 7 = 4*x mod 12) No answer. 2) 6 /
9 = x mod 12 (or 6 = 9*x mod 12)
x=2. 3) 7 / 5 = x mod 13
(or 7 = 5*x mod 13) x=4.
4) 3 / 13 = x mod 26 (or 3 = 13*x mod 26) No
answer.
5) 4 / 10 = x mod 26 (or 4 = 10*x mod 26) x=3.
6) 12 / 10 = x mod 29 (or 12 = 10*x mod 29) x=7.
E) Mod Exponentiation
In the encryption process of the
RSA Cipher the plain message is raised to the power of e mod m, where e and m
(commonly a 200 digit number) make up the public key. To account for huge
numbers, one of our goals in this section is to learn some shortcuts when
performing mod exponentiation.
Since mod exponentiation is repeated multiplication, it can be reduced to the above mod
multiplication.
How do we compute 3^{4} MOD 12?
First we multiply: 3 * 3 * 3 * 3 = 81,
secondly we find the remainder: 81 mod 12 = 9. Compute the following: 1)
4^{3} mod 12
4 2) 4^{4} mod 12
4 3) 5^{3} mod 12
5 4)
2^{7} mod 20
8 5) 11^{5} mod 10
1
Don't worry if you did not get the last one.
However, if you did get 1, congratulations. You figured out already the shortcut
that can be used to compute large powers. To compute 115 mod 10, we compute (11
mod 10) = 1 and multiply that answer 5 times by itself which yields the answer
1. Using this shortcut, the answer to 125 mod 10 is 2 since 12 mod 10 = 2 and 25
mod 10 = 32 mod 10 = 2.
Shortcut
1: Instead of first computing the (large) power and secondly finding the
remainder, it is easier to find the remainders of smaller powers and mod
multiply them to get the final answer.
Compute the following: 1)
14^{3} mod 12
8 2) 24^{4} mod 12
0 3) 37^{16} mod 12
1 4)
82^{7} mod 20
8 5) 163^{5} mod 10
3
There is a fast way to
compute 2377 mod 24 . Since 23 = 1 mod 24, we may write (1)77 mod 24 which
simplifies to 1 mod 24. To get a positive answer, we add 24 to get 23 as the
final answer.
Shortcut
2: If the base is a little less than the modulus, then rewrite the base as a
small negative number which when exponentiated yields a smaller answer then the
original power.
Compute the following: 1)
11^{3} mod 12
11 2) 15^{4} mod 17
16 3) 54^{16} mod 55
1 4)
82^{7} mod 84
40 5) 16^{5} mod 19
4
6) Powers such as 1234567^{6 }would yield an overflow on your
calculator. However, performing modular arithmetic using the modulus m=1234569 we are
able to compute the answer 64. Why?
Answer: 1234567 = 2 mod 1234569. Thus, (2)^{6} =
64 MOD 1234569 We
conclude the Mod Exponentiation with one last shortcut. There
is a fast way to compute 2^{11} mod 15. Since 2^{11} = ((2^{2})^{2})^{2
}* 2^{3} , we compute 2^{11} mod 15 as (2^{4})^{2}
* 2^{3} mod 15 =((2^{4})^{2} mod 15 ) * (2^{3}
mod 15 ) = 1 * 8 mod 15 = 8. Check: Dividing 2048 by 15 leaves a remainder of 8.
Correct. Shortcut
3: (Repeated Squaring) To compute a^{n}, divide the exponent n by the greatest power of
2 that is less than n. This yields an exponent e and a remainder r. Finally,
compute a^{e} * a^{r}. To compute a^{e}, use
shortcuts if necessary. a^{r} is a fairly small number.
Compute the following: 1)
3^{11} mod 12
3. Since 3^{2} = 9, 3^{4}=(9)^{2} = 81 = 9 mod 12.
Also: 3^{8}=(3^{4})^{2}=(9)^{2} = 81 = 9 mod
12. Since, 3^{3 }= 27 = 3 mod 12, 3^{11} = 3^{8} * 3^{3} =
9 * 3 = 27 = 3 mod 12. 2) 4^{11} mod 12
4. Since 4^{2} =4, 4^{4}=4^{8}=4. 4^{8} * 4^{3}
= 4. 3) 4^{17} mod 17
4)
5^{13} mod 17 3. Since 5^{2}=8,
5^{4} = 13 = 4, 5^{8} = 16 =1, 5^{13} = 1 * 4 * 5
=20 5) 3^{33} mod 17
3. Since 3^{2} = 9, 3^{4} = 4, 3^{8} =
1, 3^{16 }=1, 3^{32} = 1 6) 16^{5} mod 19
4. Since 16 = 3, 16^{2} = 9, 16^{4} = 81
= 5.
A computation
challenge: 7) 2^{130}
mod 17 4. Since
2^{4} =1, 2^{8}=2^{16}=...=2^{128} =1.
8) 2^{269} mod 19 10.
Since 2^{4} = 3, 2^{8} =9, 2^{16} =
5,...
9) 3^{333} mod 15 3.
Since 3^{5} = 3, ...
