Modular Arithmetic Concepts and Applications PDF

Presented @ MAN Conference 2016
By
Adetunmbi Emmanuel Olukunle
wiknund@gmail.com, +2348074880378
What is Modular Arithmetic?
Modular Arithmetic: C&A @Adetunmbi 2016
In Mathematics, Modular Arithmetic is a system of

Arithmetic for integers where numbers wrap around
upon reaching a certain value-the modulus (plural
moduli). The modern approach to Modular Arithmetic
was developed by Carl Friedrich Gauss in his book
Diaquisitiones Arithmeticae, published in 1801
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".
For example, for mod 12 numbers

are never bigger than 11
Can you evaluate these?

13 + 23+33+ 43+ + 35 3+ 363 (modulo 37).
1011*32(mod 8) in less than ten seconds.
72016(mod 2017).
On what day of the week falls March 31, 2024.
Examples
18 (mod 7) 4 mod 7, 18-4 is a multiple of 7

20 (mod11) 9 mod 11, 20-9 is a multiple of 9
19 (mod 2) 1 mod 2, 19-1 is a multiple of 2
Exercise One
Which of these statements are true?
(a) 500(mod 7) 6(mod 7)

(b) 75(mod 11) 9(mod 11)
(c) 88(mod 8) 0(Mod 8)
(d) 42(mod 5) 2(mod 5)
Some THEOREMS on Modular

Arithmetic
If a b mod m and b c mod m then a c mod m.
If a b mod m and c d mod m, then

a + c b + d mod m and ac bd mod m
Fermat's Little Theorem
For any prime p and any integer q such that p does
not divide q(p-1) 1 (mod p)
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.
Example 1
Find 111*222 (mod 246).
Well, first multiply 111 by 222 as integers:
we get 111*222 = 24642.
Now we have to divide by 246.
Well by long division 24642 = 246*100 + 42,
so the remainder is 42 when we divide 24642 by
246.Therefore 111*222 (mod 246) 42.
Example 2
Find -11(mod 17).
-11=-1(17)+6. Remainder is 6 so -11(mod 17)6
mod 17.
Alternatively, Since we work in Mod 17,
you can add 17 to the -11 till you obtain a
Positive number, -11+17 = 6 so -11(mod 17) 6
(Mod 17)
Example 3
Confirm that -33(mod 10) 7(mod 10).
-33= -4(10) + 7 ,
OR
-33 +10(mod 10) -23(mod 10) -23+10(mod 10)
-13 + 10(mod 10)
-13 + 10(mod 10) -3(mod 10) -3+10(mod 10)
7(mod 10)
Example 4
Is 5728 1 (mod 29)?
Using Fermat little theorem.
57(mod 29) 28 (mod 29) -1(mod 29)
5728 (-1)28 (mod 29) 1 (mod 29).
MODULAR ADDITION
Addition in Modulo 7
0
Subtraction In Modulo 5
1
Examples
(1)
23 + 32 (mod 7) 55(mod 7), 55 = 7(7) + 6

6(mod 7) OR
23(Mod 7) 2(mod 7) , 32 (mod 7) 4(mod 7)
23+32(mod 7)2+4 (mod 7) 6(mod 7)
(2)
23 32 (mod 5) -9(mod 5), -9 = -2(5) + 1

1 ( Mod 5) OR
233(mod 5) and 32 2(mod 5) so 23-32 3-2(mod 5)
1(mod 5)
Exercise 2
Evaluate the following
234+666(mod 10)
56-65(mod 7)
100 +78(mod 3)
Modular Multiplication
1
10
11
10
11
10
10
10
11
11
10
10
10
10
11
11
10
Other Examples
(1)
(2)
23*32 2*4(mod 7)
1(mod 7)
23*32(mod 35).
Since 23 and 32 are both less than 35, we first
multiply them.
23*32 736 (mod 35), 736 = 21(35) +1,
hence 23*35 1(mod 35)
Exercise 4
Evaluate the following
a) 56*89(mod5)
b) 1011*32(mod7)
c) 79*88(mod 8)
MODULAR DIVISION
Taking 4 2 2 (Mod 5), What is 3 4(mod 5)?

Remember, it can only be positive whole number or no
solution.
Lets solve it!
Let 3/4 = x (mod 5), 4x = 3 (mod 5).
Remember 3 8 (mod 5) and 8 is divisible by 4,
4x 8(mod 5), x=2 (mod 5), x=7(mod 5),
what will be the next possible value of x?
What is the value of 4 3(mod 5)?

Use the same approach
Let 4/3 = y (mod 5),
3y = 4(mod 5).
4 24(mod 5).
3y = 24,
y= 8(mod 5)
What is the next value of y?
MODULAR EXPONENTIATION
First Lets check certain congruencies.
28 (mod 6) 28(mod 12) 28 (mod 24)
34 1(mod 10), 38= (34)2 12(mod 10),

hence, 38 1 (mod 10). So,
what is the value of 31011(mod 10)?
Since 34 1(mod 10),
we express the power 1011 as a product of 4:
1011= 4*252 + 3.
31011 = 34(252) + 3 = 3 4(252) * 33 1252 * 33 (mod 10)
27(mod 10)
7(mod 10)
31011 7 (mod 10)
10116 1(mod 17) by Fermats little theorem

If a (mod n) b(mod n)
then am b m (mod n),

number m
for any natural
What are the values of:
(i) 281 (mod 7)

(ii) 1281(mod 17)
(iii) 1313 (mod 14)
(iv) 3141(mod 5)
(v) (-5)99(mod 8)?
(1)281(mod 7).
The root is 23(mod 7) 1(mod 7).
281= (23)27 mod 7 127(mod 7)
281 1 (mod 7)
(2)1281(mod 17). Since 17 is prime, we can apply
Fermats little theorem, 17-1 = 16, we can express
81 as a product of 16.
81= 16*5 + 1
1281 = 1216(5) + 1 = (1216)5 * 121 15*12 (mod 17)
12(mod 17)
(3) 1313(mod 14), we cannot use Fermats little theorem since 14 is not
prime.
13 (mod14) -1 (mod14). 1313 (-1)13 -1 13 (mod14)
(4) 3141 (mod5) 1(mod5). How?
31 (mod5) 1 (mod5). So 3141 141 (mod5).
(5) (-5)99 (mod8) 3(mod8). -5 (mod8) 3 (mod8),
(-5)99 399(mod8).
But the root 32 1(mod 8) and 399 = 32(49)+1 = 3 2(49)*3.
So
(32)49 * 3 1*3 3 (mod8).
What about 34090 (mod11)? We know that 310 1(mod 11) from Fermats
little theorem. 34090=(310)409 1(mod 11)
Modular Inverses
What is the inverse of 8 (or 8-1 )in modulo 11?
Let the inverse of 8 in Modulo 11 be x, then 8x 1 (mod

11). The possible values are 0 to 10 so, we make a table
of values.
x 0
8x 0
1
8
2
5
3 4 5
2 10 7
6
4
7
1
8
9
9 10
6 3
So, the inverse of 8 in modulo 11 is 7.

We can also solve the equations 8x 5(mod 11), x=2
The table below shows the inverse of numbers in mod 11
10
x-1
10
Not all numbers have inverses in a given modulo. For example 8 has no
inverse in Modulo 10.
Using table of values we can also get the three solutions for 6x + 1 4 (mod 15)
x
6x+1
0
1
1
7
2
13
3
4
4
10
5
1
6
7
7
13
8
4
9
10
10
1
11
7
12
13
13
4
The values of x for which 6x + 1 4(mod 15) are 3, 8 and 13. The inverses of 6x
+1 in mod 15 are 0, 5 and 10.
14
10
Further Examples
1) Copy and complete the following table for multiplication in modulo 11.
Use the table to:
(i) Evaluate (9
5)
(10 10)
(ii) Find the truth set of
I. 10
m =2
II. n
n =4.
1
5
1
1
5
10
10
5
5
9
9
10
10
Solution
1
10
10
10
10
(i) 5*5(mod 11) 3(mod

11), a=3
(ii) 5*9 1(mod 11), b=1
(iii) 5*10 6(mod 11), c=6
(iv)
d= 1
(v) 9*9 4(mod 11), e= 4
(vi) 9*10 2(mod 11), f=2
(vii)
g= 6
(viii)
h= 2
(ix) 10*10 1(mod 11), m=1
Solution
1
10
10
a=3
b=1
c=6
d=1
e= 4 f=2
10
10
g=6
h=2
(a) (9
5)
(10 10)
1
1 1
(b) (i) 10 m =2,
The solution set is m={9}
(ii)n n =4.
The solution set is n={9}
m=1
(2) What if you are to evaluate

13 + 23+33+ 43+ + 35 3+ 363
(modulo 37)?
First, lets divide the series into two:

13 + 23 + 33 + --- + 183 and
193 + 203 + --- + 353 + 363 .
The congruents of the second part are
additive inverses.
193 + 203 + --- + 353 + 363 (-18)3 + (-17)3 +
(-16)3 + --- + (-2)3 + (-1)3.
13 + 23 + 33 + --- + 183 + 193 + 203 + --+ 353 + 363

13 + 23 + 33 + --- + 183 + (-18)3
+ (-17)3 + (-16)3 + --- + (-2)3 + (-1)3
0 (mod 37).
(3) Evaluate 9 * 12-1

(mod 35).
Solution
9 * 12-1 27(mod 35) ,
the inverse of 12 in
mod 35 is 3 so 9*3= 27
Other Theorems
Eulers theorem: If a is relatively prime to n,
then a(n) 1 (mod n). where (n) is the number of

numbers between 1 and n that are relatively prime to n.
328 1 (mod 29), it is close to Fermats little theorem
apart from the part of (n) which is not always equal
to n-1.
Lets try to obtain (n) for several n
10 11 12 13 14 15 16 17 18 19 20
(n)
10 4
12 6
16 6
18 7
So, 56 1(mod 14),

78 1(mod 15), and so on.
The theorem can be used to find modular inverses.
(2) Wilson's Theorem: The number p is a prime

if and only if (p - 1)! -1 (mod p). So, 96! -1
(Mod 97)
Applications of Modular Arithmetic
Modular Arithmetic is referenced in

Number Theory
Group Theory
Ring Theory
Knot Theory
Abstract Algebra
Computer Algebra
Cryptography
Computer Science
Chemistry
Visual & Music Arts
Modulo 97 Arithmetic is used to trap user

input errors in Bank Account Numbers.
Polynomial Factorization in Computer
Arithmetic.
Calculating CAS registry number in
Chemistry.
Apportionment in Law.
Game Theory.
CHECK DIGIT
A check digit is a form of redundancy used to detect error on
identification numbers. With a check digit one can detect
simple errors in the input of a series of characters(usually
digits) such as a single mistyped digit or some permutations of
two successive digits.
A very simple check digit method would be to take the digital
sum mod 10 (but not error of switching digit).
A slightly more complex method is to take a weighted sum of
the digits mod 10. Widely used weights are 1,3,7 or 9 because
they are coprime to 10. Example, the 371 371 371 weight used in
United States Bank Routing Transit Number.
ISBN-10
The ISBN-10 code instead uses mod 11
which is prime. Check the validity of the
ISBN 0-201-53082-1
0*10 + 2*9 + 0*8 + 1*7 + 5*6 + 3*5 + 0*4 +
8*3 + 2*2 + 1*1 (mod 11) 0(mod 11). It is
valid
Universal Product Code

Check whether or not the UPC-A barcode for a
box of tissue which is 03600024147 is valid.
The check digit is 7, our calculation must produce
7 else it is invalid
Add the odd number digits: 0+6+0+2+1+5=14
Multiply the sum by 3: 14*3 =42
Add the even number digits: 3+0+0+4+4=11
Add the product in (ii) and sum in (iii): 42+11 = 53
53(mod 10) 3(mod 10) which is not equal to
zero. So subtract from 10 and that gives 7. Hence,
the UPC is valid
ISBN-13
In Use January, 2007 is equal to the EAN-13
(European Article Number) code found
underneath a books barcode.
Its check digit is generated the same way as
the UPC except that the even digits are
multiplied by 3 instead of the odd digits.
Is this ISBN code 978-0-620-68500-9 valid ?
CAS Registry Number
Chemical Abstract Service Registry Number is a

unique numerical identifier assigned by CAS to
every chemical substance described in open
scientific literature from 1957. The Registry is
updated with an approximate 15000 additional new
substances daily.
The CAS number for water is 7732-18-5, the check
digit is 5 and is calculated as follows
8*1+1*2+2*3+3*4+7*5+7*6= 105. 105mod 10 5
Exercise
What are the check digits for the following substances?
Actinium(III) oxide 12002-61-x
Silver Bromide 7785-23-y
Sucrose 57-50-z
x=8
y=1
z=1
It is also used for Event and Tournament Scheduling.
On what day of the week is June 12, 2098? It is

Thursday, following simple Algorithm and Modulo 7
for days of the week.
What day of the week Game!
Calculation of Golden Number, Pascal's Full Moon

Day and Easter Sunday among others.
When next will Easter Sunday fall in March?
Year 2024, March 31.
How?
Modulo 19,30 and 7 are used to compute this

following certain algorithm.
We can calculate Pascals Full Moon Day using 45(Y mod19 * 11)Mod 30 with little Adjustments .
If Y mod 19 = 5 or 16, add 29
if Y mod 19 = 8 add 30
if the result is over 31,
subtract 31 (and the month is April, instead of
March),where Y is Year AD. The next Sunday after
PFMd is Easter Sunday.
Check for the results obtained for the next 11 years which is good for planning.
YEAR
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
DATE
APRIL 16
APRIL 1
APRIL 21
APRIL 12
APRIL 4
APRIL 17
APRIL 9
MARCH 31
APRIL 20
APRIL 5
MARCH
28
Modular Arithmetic:
C&A
@Adetunmbi 2016
Reference
[1] I. M. Isaacs and M. R. Pournaki, Generalizations of
Fermat's Little Theorem Using Group Theory," Amer.
Math. Monthly 112 (2005), 734-740.
[2] L. Levine, Fermat's Little Theorem: A Proof by
Function Iteration," Math. Mag. 72 (1999), 308-309.
[3] P. A. MacMahon, Applications of the Theory of
Permutations in Circular Procession to the Theory of
Numbers," Proc. London Math. Soc. 23 (1891(2)), 305313.
[4] C. Smyth, A Coloring Proof of a Generalisation of
Fermat's Little Theorem," Amer. Math. Monthly 93
(1986), 469-471.
Connect With Adetunmbi

Check my channel on youtube.com for Math videos on
Ordinary Differential Equations and others.

https://www.youtube.com/channel/UCBXvVT9pakQo3nLDX1x8bVA
wiknund@gmail.com
https://ng.linkedin.com/in/emmanuel-adetunmbi-22b8702b
https://www.facebook.com/emmanuel.adetunmbi
JESUS LOVES YOU.

GIVE HIM A CHANCE TODAY

Modular Arithmetic Concepts and Applications PDF

Uploaded by

Copyright:

Available Formats

Modular Arithmetic Concepts and Applications PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Modular Arithmetic Concepts and Applications PDF

Uploaded by

Copyright:

Available Formats

What is modular arithmetic?

What is modular arithmetic?

What is the modulus?

What is the modulus?

Presented @ MAN Conference 2016

What is Modular Arithmetic?

Modular Arithmetic: C&A @Adetunmbi 2016

In Mathematics, Modular Arithmetic is a system of

Modular Arithmetic: C&A @Adetunmbi 2016

Modulus (abbreviated as "mod") is the

Latin word for remainder, residue or

"mod arithmetic" is really "remainder

For example, for mod 12 numbers

Modular Arithmetic: C&A @Adetunmbi 2016

Can you evaluate these?

Modular Arithmetic: C&A @Adetunmbi 2016

18 (mod 7) 4 mod 7, 18-4 is a multiple of 7

Modular Arithmetic: C&A @Adetunmbi 2016

(a) 500(mod 7) 6(mod 7)

Modular Arithmetic: C&A @Adetunmbi 2016

Some THEOREMS on Modular

If a b mod m and c d mod m, then

Modular Arithmetic: C&A @Adetunmbi 2016

What time is it 10 hours

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

23 + 32 (mod 7) 55(mod 7), 55 = 7(7) + 6

23 32 (mod 5) -9(mod 5), -9 = -2(5) + 1

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Taking 4 2 2 (Mod 5), What is 3 4(mod 5)?

What is the value of 4 3(mod 5)?

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

First Lets check certain congruencies.

28 (mod 6) 28(mod 12) 28 (mod 24)

34 1(mod 10), 38= (34)2 12(mod 10),

10116 1(mod 17) by Fermats little theorem

then am b m (mod n),

Modular Arithmetic: C&A @Adetunmbi 2016

for any natural

What are the values of:

(i) 281 (mod 7)

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Let the inverse of 8 in Modulo 11 be x, then 8x 1 (mod

Modular Arithmetic: C&A @Adetunmbi 2016

So, the inverse of 8 in modulo 11 is 7.

The table below shows the inverse of numbers in mod 11

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

Modular Arithmetic: C&A @Adetunmbi 2016

(i) 5*5(mod 11) 3(mod