MAT 115

Fall 2001
Chris Christensen
Class notes

Multiplication Modulo n

For multiplication modulo n (as for addition and subtraction), we can either
reduce modulo n and then multiply (and, perhaps, have to again reduce
modulo n), or we can first multiply and then reduce the product modulo n.

For example,

23  3  3  3  9  4mod 5 or 23  3  69  4mod5 .

Here is the table for multiplication modulo 5.

0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

More interesting, perhaps, is the table for multiplication modulo 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

Notice that although neither 3 nor 2 is congruent to 0, the product

3  2  0mod 6 . This is not something we encounter when working in the
real numbers. We call 3 and 2 zero divisors modulo 26. Two integers are

1
called zero divisors modulo n if neither of them is congruent to 0 modulo n
but their product is congruent to 0 modulo n.

Division Modulo n

We can approach division in a manner that is similar to subtraction. We

thought of subtraction as "just adding the (additive) inverse;" we can think
of division as "just multiplying by the (multiplicative) inverse." The
multiplicative inverse of a number m is denoted m 1 and is the number that
when multiplied by m results in 1. For example, in the real numbers, the
1 1
multiplicative inverse of 3 is 3  .
3

Inverses modulo n are more problematic.

Look back at the table for multiplication modulo 5. 1  1  1 ; so, 11  1 .

2  3  1 ; so, 21  3 and 31  2 . 4  4  1 ; so, 41  4 . 0 has no
multiplicative inverse. (0 has no multiplicative inverse in the real numbers
either.)

Now look at the table for multiplication modulo 6. 1  1  1 ; so, 11  1 .

5  5  1 ; so, 51  5 . But, 0 has no multiplicative inverse, and the zero
divisors 2, 3, and 4 have no multiplicative inverses.

So, we can only sometimes undo multiplication. Because in cryptology,

when we encipher we want an inverse process to decipher, we must be
careful using multiplication modulo n for enciphering.

Solving Linear Congruences Modulo n

In algebra, we learn to solve linear equations; e.g.,

3x  8  26

3 x  18

x6

2
(We call 3x  8  26 a linear equation because the variable x appears only to
the first degree – there are not squares, cubes, or higher powers of x. This
should remind us of the equation of a line y  mx  b .)

We can mimic this process for modular arithmetic provided we only use
multipliers that have (multiplicative) inverses.

For example, we can solve

2 x  3  1mod5

2 x  2mod5

2 x  3mod5

3  2 x  3  3mod5

x  9mod5

x  4 mod5

because 3 is the inverse of 2 modulo 5.

Of course, because the only possible values of x are 0, 1, 2, 3, or 4; we could

just try all of the possibilities until we found a solution (or not).

Sometimes we are forced into trying all possible solutions. Consider solving
the linear congruence 4 x  2mod 6 . We saw above that 4 does not have a
multiplicative inverse modulo 6. So, our usual method of solution will not
work. That does not mean that there is no solution. If we try all the
possibilities (0, 1, 2, 3, 4, and 5), we see that there are two solutions 2 and 5.

Notice that

3 x  4mod 6

has no solution.

The mathematical area known as number theory discusses solutions of such

congruences (and many other interesting properties of the integers).

3
 Solving Pairs of Linear Congruences Modulo n

A system of two linear congruences can be solved in the same manner as we

use to solve a system of two linear equations provided that the only
multipliers we encounter during solution have inverses.

For example, modulo 5 we can solve the system of linear congruences

3 x  4 y  2

2 x  2 y  3

Multiply the second congruence by 2.

3 x  4 y  2

4 x  4 y  6

Subtract the first congruence from the second.

x4

Substitute x  4 into the first congruence.

3 4  4 y  2

And, solve the linear congruence for y.

12  4 y  2

4 y  10

4y  0

Because 4 is the inverse of 4,

4 4y  40

y0

4
Bow check that the pair x  4 and y  0 is a solution to the pair of linear
congruences.

Just like in the case of a single congruence, if our method of solution does
not work, that does not mean that there is no solution. Try all possible
solutions. How many possible solutions would we have to try?

Positive Integer Exponents Modulo n

Recall that positive integer exponents correspond to repeated

multiplications.

23  2  2  2

477  47  47  47  47  47  47  47

m n  m  m  ...  m
n factors

Recall that when we multiply modulo n we can either first reduce modulo n
and then multiply or we can first multiply and then reduce modulo n. For
exponentiation, it makes most sense to reduce as much as possible along the
way.

Consider the following example.

If we first multiply and then reduce modulo 2,

25978331465407812

 6748737057265974929346496089961

 1mod 2

But, if we first reduce modulo 2,

25978331465407812  12  1mod 2

5
 Carl Friedrich Gauss (1777 – 1855)

The idea of modular arithmetic was introduced by the mathematician Carl Friedrich
Gauss in his 1801 book Disquisitiones Arithmeticae (Investigations in Arithmetic).

Gauss was born into a family which, like many others of the time, had recently moved
into town, hoping to improve its lot from that of impoverished farm workers. One of the
benefits of living in Brunswick was that the young Carl could attend school. There are
many stories about Gauss’ early developing genius. At the beginning of the school year,
to keep his 100 pupils occupied, the teacher, J. G. Buttner, assigned them the task of
summing the first 100 integers. He had barely finished explaining the assignment when
the 9 year old Gauss wrote the single number 5050 on his slate and deposited it on the
teacher’s desk. Gauss had noticed that the sum in question was simply 50 times the sum
101 of the various pairs 1 and 100, 2 and 99, 3 and 98, ... and had performed the required
multiplication in his head. Impressed by his young student, Buttner arranged for Gauss to
have special textbooks, to have tutoring by his assistant Martin Bartels (1769 - 1836),
who himself later became a professor of mathematics in Russia, and to be admitted to a
secondary school where he mastered the classical curriculum.

In 1791, the Duke of Brunswick granted Gauss a stipend which enabled him first to
attend the Collegium Carolinium, a new science oriented academy funded by the
Brunswick government to train bureaucrats and military officers, then to matriculate at
the University of Gottingen in neighboring Hanover, which already had a reputation in
the sciences, and finally to continue his research back in Brunswick while receiving a
Ph.D. from the local University of Helmstedt. Not only did Gauss publish his researches
in number theory in 1801, with the book being dedicated to his patron the Duke, but he
also developed at the same time a new method for calculating orbits which enabled
several asteroids to be discovered. The Duke’s patronage lasted until the Duke was killed
in battle against France in 1806 and the duchy was occupied by the French army.
Fortunately for science, the French general had been given explicit orders to look out for
Gauss’ welfare. Thus Gauss was able to stay in Brunswick until he accepted a position at
Gottingen the following year as professor of astronomy and director of the observatory.
Gauss remained at Gottingen for the remainder of his like, doing research in pure and
applied mathematics as well as astronomy and geodesy.

Gauss was never particularly happy with teaching classes, because most of the students
were uninterested in, and not well prepared for, mathematics, but he was willing to work
privately with any actively interested student who approached him. Compared to his
predecessor Euler and to his French contemporary Cauchy, Gauss ultimately published
little, his collected works occupy only (?) 12 volumes. Nevertheless, his mathematical
papers are of such profundity that they have influenced the progress of the subject to the
present. A History of Mathematics: An Introduction by Victor J. Katz page 588.

6
Exercises

11. Multiply.

11a. (5  2) mod3
11b. (3  4) mod8
11c. (50  37) mod 2
11d. (33  91) mod 2
11e. (12  15) mod 26

12. Determine the following powers.

12a. 54 mod 26
12b. 57 234 mod 2
12c. 7 4 mod5
12d. (2)5 mod 6
12e. 44126 mod 2

13. Find the multiplicative inverses of 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25
modulo 26.

14. Find the multiplicative inverses of 1, 2, 3, 4, 5, 6 modulo 7.

15. 0, 1, 2, 3, 4, 5, 6, 7 is a complete set of representatives modulo 8.

15a. Find the additive inverse of each number modulo 8.

15b. For each number that has a multiplicative inverse modulo 8, find
that multiplicative inverse.
15c. For each nonzero number that does not have a multiplicative
inverse modulo 8, show that it is a zero divisor.

7
16. Solve, if possible.

16a. 15 x  4  2mod 26
16b. 4 x  3  2mod 5
16c. 6 x  2  3mod8
16d. 5 x  4  3mod8

17. Solve, if possible.

2 x  y  5
17a.  mod 26
9 x  y  4

3x  2 y  5
17b.  mod 7
5 x  4 y  6

 3x  2 y  1
17c.  mod5
4 x  3 y  2