Modular Arithmetic.mws
High School Modules > Advanced Topics
Modular Arithmetic
An exploration of modular arithmetic  adding, multiplying, powers, orders, residues.
[Directions : Execute the Code Resource section first. Although there will be no output immediately, these definitions are used later in this worksheet.]
0. Code
Warning, the name changecoords has been redefined
> 
ModTable := proc(n)
local A,i,j,k,m;
m := floor( n*3/2 + 3);
A := array( [seq( [ seq(` `, j = 1..(n) ) ], i = 1..m) ]);
A[1,1] := cat(`mod `,n);
for k from 1 to n do A[2, k] := k1; od;
for k from 1 to n do A[3, k] := `__`; od;
for i from 1 to m3 do
for j from 1 to n do
A[i+3,j] := (n*(i1)+j1) ; od;od;
print(A);
end proc:

> 
ModAddTable := proc(n)
local A,i,j,k;
A := array( [seq( [ seq(` `, j = 1..(n+3) ) ], i = 1..(n+3)) ]);
A[1,1] := n; A[2,2] := `+`;
for k from 1 to n do A[1,k+3] := k1; od;
for k from 1 to n do A[k+3, 1] := k1; od;
for k from 0 to n do A[2,k+3] := `__`; od;
for k from 0 to n do A[k+3, 2] := ``; od;
for i from 1 to n do
for j from 1 to n do
A[i+3,j+3] := (i + j 2) mod n ; od;od;
print(A);
end proc:

> 
ModMultTable := proc(n)
local A,i,j,k;
A := array( [seq( [ seq(` `, j = 1..(n+3) ) ], i = 1..(n+3)) ]);
A[1,1] := n; A[2,2] := `*`;
for k from 1 to n do A[1,k+3] := k1; od;
for k from 1 to n do A[k+3, 1] := k1; od;
for k from 0 to n do A[2,k+3] := `__`; od;
for k from 0 to n do A[k+3, 2] := ``; od;
for i from 1 to n do
for j from 1 to n do
A[i+3,j+3] := ((i1)*(j1)) mod n ; od;od;
print(A);
end proc:

> 
ModPowTable := proc(n)
local A,i,j,k;
A := array( [seq( [ seq(` `, j = 1..(n+2) ) ], i = 1..(n+2)) ]);
A[1,1] := cat(`mod `,n); A[1,2] := `powers :`; A[2,1] := `k :`;
for k from 1 to n do A[1,k+2] := k; od;
for k from 1 to n do A[k+2, 1] := k1; od;
for k from 1 to n do A[2,k+2] := `__`; od;
for k from 1 to n do A[k+2, 2] := ``; od;
for i from 1 to n do
for j from 1 to n do
A[i+2,j+2] := (i1)^j mod n ; od;od;
print(A);
end proc:

1. Modular Equivalence & Reduction
Modular arithmetic, or clock arithmetic, reduces all positive integers to a set of remainders. This is done relative to some fixed integer n. For example, lets consider numbers "modulo 5". This means any integer is equivalent to the remainder of that number divided by 5. In this context, we don't care about the quotient, only the remainder.
This is called "clock arithmetic" sometimes because it works similar to the way a clock works  cycling through the same numbers.
> 
for k from 1 to 25 do k,` mod 12 is `, k mod 12; od;

> 
for k from 1 to 19 do k,` mod 5 is `, k mod 5; od;

You can see that the results at right goes through the same 5 numbers : 0, 1, 2, 3, and 4  like a clock with only 5 hours ( and that starts at 0 rather than 1).
A regular clock shows the same time 12 hours later as it does 24, 36, 48, 60, 72, ... hours later.
> 
3 mod 12;
15 mod 12;
27 mod 12;
39 mod 12;

Here are the numbers from 0 to 69, mod 7. Basically its a remainder chart. For any number in the body of the table, you can look at the top row to see what its remainder would be modulo 7. All of the numbers in each column are all equivalent mod 7!
Here are the numbers from 0 to 23, mod 4. Again, all of the numbers in each column can be reduced to the remainder in the top row.
2. Modular Addition
When adding two numbers, and the result is less than n (the modular base), then the numbers simple add. However, if the result
3. Modular Addition Tables
We can make addition tables modulo a number. Note that 0 + k = k.
4. Modular Multiplication
Modular multiplication is simply multiplying two integers  then reduce modularly.
5. Modular Multiplication Tables
We can make multiplication tables too.
6. Modular Powers
Similar to products, we can find modular powers, by find the power, then reducing modularly.
> 
for k from 1 to 12 do
'3'^k = 3^k mod 17;
od;

7. Modular Power Tables
We can easily create tables of the powers. The numbers along the right column are the integers. The powers are in the top row.
8. The Order of a Number
Please take a moment to look for some patterns in this table.
A few observations :
1
.
(of course), this is why the first column of the table (under 1) matches the original numbers.
2.
a bit more surprising  the last column of the table (under 5) matches the original numbers too.
This is true modulo a prime number.
3.
for all nonzero numbers at some point  but that point varies. The minimal exponents that give
1 are : 1, 4, 4, 2 ... all divisors of p1 = 51 = 4. ( 1^1 = 1,
=1,
= 1,
= 1).
The smallest positive integer h, for which k to the h is one, is called the
order
of k mod p
. We can find the order directly using a Maple command.
Warning, the protected name order has been redefined and unprotected
> 
order(2,5); order(4,5);

> 
for k from 1 to 5 do `order of `, k, ` is `, order(k,5); od;

5 fails because that is congruent to zero mod 5.
Find the order of the numbers 1 through 6 mod 7 :
Find the order of the numbers 1 through 10 mod 11 :
What if n is not a prime number?
Many of the numbers never become one by raising them to powers. Which numbers do have this property? And what distinguishes them?
The only numbers which can be raised to one, are 1 and 5. The numbers 2, 3, and 4 never become one. The distinction is that 1 and 5 are relatively prime to 6, while 2, 3, and 4 have a gcd greater than one.
Lets look at some other examples. What nonzero integers less than 8 are relatively prime to 8? 1, 3, 5, and 7. We would expect to see that these can be raised to powers that make them one.
For 9, the relatively prime numbers are 1, 2, 4, 5, 7, and 8.
9. Multiplicative Inverse
In the world of real numbers, every nonzero number has a multiplicative inverse. Given a number a, there is a number b, such that ab = 1. Often we call b the
reciprocal
of a.
In the modular world, we don't have fractions so this is not possible. However, under what conditions are there other integers which serve the same purpose as being multiplicative inverses?
For example, take the number 3, mod 7. Is there an integer such at 3*b = 1 (mod 7)? Yes, 5 is the "reciprocal of 3 mod 7",
How can we better understand this process? A quick consideration of the numbers mod 7 once again :
Since n = 7 is prime, every nonzero number 1,2, 3, 4, 5, 6 has an order  an exponent h, such that k^h = 1. This leads to an interesting idea. Given any such number k, multiplying by
gives
= 1.
Using this idea we can find the inverse for 3 mod 7.
Find the reciprocal of 5 mod 11.
Find the reciprocal of 8 mod 17.
When n is not prime, not every number has an inverse. However, those numbers relatively prime to the modular base do.
Find the reciprocal of 8 mod 17.
10. Quadratic Residues
Just looking at the squares of integers mod 5, what is the set of values?
The only nonzero squares are 1 and 4. These are called the quadratic residues  what is left after the multiples of 5 are boiled off, so to speak.
Only these numbers have modular square roots. For example there are two solutions to the equation :
So the square roots of 4 mod 5 are 2 and 3.
What are the quadratic residues mod 7?
The residues mod 7 are 1, 2 and 4. What are the square roots of 2?
The residues mod 9 are 1, 4, 7. What are the square roots of 7?
2002 Waterloo Maple Inc & Gregory Moore, all rights reserved.