Modular Arithmetic
Modular Arithmetic
Due Monday by 11:59pm Points 100 Submitting a file upload File Types pdf
Submit Assignment
Complete the following activities:
1. List all possible numbers mod 13.
2. Reduce the following according to the given modulus:
a. 15 mod 2
. 35 mod 9
c. -12 mod 5
d. 66,792 mod 253
e XXXXXXXXXXmod 15
3. Add or subtract the following in the given modulus:
a. 5 mod 9 + 8 mod 9
. 5 mod 9 - 8 mod 9
c. 25 mod XXXXXXXXXXmod 30
d. 12 mod XXXXXXXXXXmod 15
e. 6 mod XXXXXXXXXXmod 10
4. Create the addition table mod 10.
5. Multiply the following in the given modulus:
a. 3 mod 7 X 5 mod 7
. -2 mod 3 X 2 mod 3
c. 13 mod 26 X 4 mod 26
6. Create the multiplication table mod 7.
7. Create the multiplication table mod 10.
Lesson 16: Modular Arithmetic: Fa19INT359_1001_WB, Integrative
In this lesson you will be developing a math skill for use in the next lesson. Modular arithmetic is
actually something that you use every day without thinking about it. We'll be able to make art from its
addition and multiplication tables!
Modular Arithmetic
1. Understand how modular numbers work and are used.
2. Perform addition and multiplication in different moduli.
3. Create addition and multiplication tables in different moduli .
1. Lesson Materials (below).
2. What is Modular Arithmetic from Kahn Academy (Link
(https:
www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-
modular-arithmetic) )
3. Modular Addition and Subtraction from Kahn Academy (Link
(https:
www.khanacademy.org/computing/computer-
science/cryptography/modarithmetic/a/modular-addition-and-subtraction) )
4. Modular Multiplication from Kahn Academy (Link
(https:
www.khanacademy.org/computing/computer-
science/cryptography/modarithmetic/a/modular-multiplication) )
Think about how we tell time. A normal analog clock face has only 12 hours marked on it, and we
change the hour every 60 minutes and the minute every 60 seconds. When the hours get past 12, we
start back over at 1. If the time is 10:00 am and someone tells you to call them in 5 hours, you add the
5 hours to 10:00 and you get 3:00 pm (but then you don't call because really, who calls anymore?).
Unless you've been in the military or to a foreign country it doesn't even enter your mind to add 5
hours to 10:00 and call it 15:00! Of course, military clocks run on a 24 hour time scale so you would
get the same effect every 24 hours. Adding 5 hours to 22:00 (10:00 pm) in military time gives you 3:00
(which is 3:00 am).
16 Modular Arithmetic
Introduction
Objectives
Readings
Lesson Materials (4 parts)
Part 1: Modular Arithmetic Introduction
This is how numbers work in modular arithmetic. To count in modular arithmetic, you start at 0 and
then count up by integers until you get to the number chosen as the modulus. When you reach the
modulus, you start over at 0. The symbol for modular arithmetic is where is a positive
integer less than , is the modulus, and the symbol "mod" stands for the word modulus. For the 24
hour clock, the modulus would be 24 and so the numbers would have to be from 0 to 23. You can
visualize this as a clock face with 24 hours marked, like this:
Note that the spot where 12 would be on a 12 hour clock has 0 instead because midnight on a 24 hour
clock is 0:00. The minute after 23:59 is 0:00 so there is no mark for the number 24. The way you say
that in modular arithmetic is . The strange three-lined equals sign means "is
equivalent to" because 24 is not *equal* to 0, it is just equivalent to 0 if I only have 24 numbers! So
out loud you would say "24 is equivalent to 0 mod 24."
For any other number larger than 24, you just keep counting around the clock face. Let's try 35. You
know that if you go around the clock face by 24, you get back to 0 so for 35 you start at the 0 and keep
counting like this:
Counting past the 24 (the 0 on the clock) until you get to 35, you land on the 11. This means that
. You could also say if you need to emphasize the
modulus at work. This works with negative numbers as well. If you want to decide what
is you just count backwards on the clock, like this:
and so .
For a different modulus, you can just use a clock face with a different number of marks on it. For
example, if the modulus is 5 then the clock face would only have the numbers 0 to 4 on it. Then we
could determine like this:
Counting around the 5 hour clock face 11 times, you land on the number 1 and so you can say
.
In practice, you don't want to have to draw a clock *every time* you want to do modular arithmetic.
This method, while effective, is time and space consuming. It would be very difficult to use with a high
number or a high modulus (can you imagine doing something like this way?!).
There is a different way though. Notice when you did you found that .
But also , ! Similarly and you found that . So maybe
instead of the clock, we could use that if the number is the same as or larger than the modulus, we
subtract, if the number is negative then we subtract it from the modulus? But then what about
which you calculated as equivalent to 1? Note that in that case you counted around the
clock face twice and then went one more. Try dividing 11 by 5 and you get 2 with remainder 1! That
is, twice around the clock face and then one more. This is the answer we are looking for and lets us
make a more precise definition of the symbol .
Definition: Let
, and be
integers with
.
Then
means that is
the remainder
when is
divided by .
There's more than one way to use this definition. I'll show both in the next example:
Example:
Calculate
.
First
Method:
Long
Division.
Divide 58
y 4 using
long
division
and find
the
emainder
is 2.
Therefore
.
Second
Method:
Nearest
Multiple.
Note that
56 is the
next
number
smaller
than 58
that is
evenly
divisible
y 4. 58-
56=2 and
so
.
Since the long division algorithm is only defined for positive numbers, we'll need an extra step for
negative numbers. They work like this:
Example:
Calculate
.
First
Method:
Long
Division.
Divide 79
y 12 using
long
division and
find the
emainder
is 7. Since
the 79 is
actually
negative,
this
emainder
is -7 and so
Now that
you have a
number
that is
closer to 0
than 12,
you can
subtract 12-
7=5 and so
. Since
equivalence
works in the
same way
as equality
you can
say
.
Second
Method:
Nearest
Multiple.
Note that
-84 is the
next
number
smaller
than -79
that is
evenly
divisible by
12. -79-
(-84)=5 and
so
.
Another way to look at modular numbers can be found at this link:
https:
medium.com/i-math/intro-to-modular-arithmetic-34ad9d4537d1 (https:
medium.com/i-
math/intro-to-modular-arithmetic-34ad9d4537d1)
This video gives some simple examples and shows another way to look at modular numbers.
What is Modular Arithmetic - Introduction to Modular Arithmetic - Cryptography - Lesson 2
(https:
youtu.be/Eg6CTCu8iio)
(https:
youtu.be/Eg6CTCu8iio)
This video shows how to convert positive numbers:
How to Convert a Positive Integer in Modular Arithmetic - Cryptography - Lesson 3
(https:
youtu.be/LcUKSu-1Adw)
(https:
youtu.be/LcUKSu-1Adw)
And this video shows how to convert negative numbers:
How to Convert a Negative Integer in Modular Arithmetic - Cryptography - Lesson 4
(https:
youtu.be/2
eCUMBYgk)
(https:
youtu.be/2
eCUMBYgk)
It's interesting to note that these videos are all from *crypotgraphy* lessons. Cryptography is the
mathematical study of codes and how to hide messages and other information. Modular arithmetic is
used in most modern cryptographic algorithms because it makes them very secure, so modular
arithmetic is what keeps your passwords safe!
Addition and subtraction using modular numbers works essentially like you want it to according to the
following theorem:
Modular
Addition
and
Part 2: Modular Addition and Subtraction
Subtraction
Theorem:
Let , ,
and be
integers.
Then
and
.
The proof of this theorem is given in the website linked in the readings for this lesson. What this
theorem means is that if you want to add or subtract two numbers in a given modulus, you are allowed
to just add or subtract the numbers and then find the equivalent of the result in the given modulus.
This is useful for numbers where the sum or difference is not a number between 0 and the modulus.
Example:
Calculate
The first
thing here
is to avoid
the
mistake of
adding
the
moduli.
The
moduli are
just telling
you the
numbers
are the
same type
so they
can be
added.
We can't
add
numbers
that are in
different
moduli.
According
to the
theorem,
all you
have to
do here is
add the 6
and the 3,
and
educe
the result
mod 7,
like this.
So you
can write
Subtraction works just the same way.
Example:
Calculate
Again, the
moduli
don't
change
here and
we cannot
subtract
number in
different
moduli.
The