•    0. Code
•    1. Modular Equivalence & Reduction
•    2. Modular Addition
•    3. Modular Addition Tables
•    4. Modular Multiplication
•    5. Modular Multiplication Tables
•    6. Modular Powers
•    7. Modular Power Tables
•    8. The Order of a Number
•    9. Multiplicative Inverse
•    10. Quadratic Residues

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

>	restart; with(plots):

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] :=  k-1; od;     for k from 1 to n do  A[3,   k] :=  `__`; od;          for i from 1 to m-3 do           for j from 1 to n do                A[i+3,j] :=  (n*(i-1)+j-1)  ;   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] :=  k-1; od;     for k from 1 to n do  A[k+3, 1] :=  k-1; 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] :=  k-1; od;     for k from 1 to n do  A[k+3, 1] :=  k-1; 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-1)*(j-1)) 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] :=  k-1; 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] :=  (i-1)^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.

>

17 mod 5;

>	irem( 17, 5);

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!

>	ModTable(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.

>	ModTable(4);

>	ModTable(13);

 

    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

>	2 + 3;  % = % mod 7;

>	(5 + 3);  % = % mod 7;

>	(5 + 2);  % = % mod 7;

    3. Modular Addition Tables

We can make addition tables modulo a number. Note that 0 + k = k.

>	ModAddTable(3);

>	ModAddTable(4);

>	ModAddTable(5);

>	ModAddTable(11);

    4. Modular Multiplication

Modular multiplication is simply multiplying two integers - then reduce modularly.

>	3*4; % mod 13;

>	3*5; % mod 13;

>	6*5; % mod 13;

 

    5. Modular Multiplication Tables

We can make multiplication tables too.

>	ModMultTable(2);

>	ModMultTable(5);

>	ModMultTable(11);

>	ModMultTable(15);

 

    6. Modular Powers

Similar to products, we can find modular powers, by find the power, then reducing modularly.

>	3^2; % mod 17;

>	3^3; % mod 17;

>	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.

>	ModPowTable(3);

>	ModPowTable(5);

>	ModPowTable(7);

>	ModPowTable(12);

 

    8. The Order of a Number

Please take a moment to look for some patterns in this table.

>	ModPowTable(5);

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 non-zero numbers at some point - but that point varies. The minimal exponents that give
                           1 are : 1, 4, 4, 2 ... all divisors of p-1 = 5-1 = 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.       

>	with(numtheory):

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 :

>	ModPowTable(7);

Find the order of the numbers 1 through 10 mod 11 :

>	ModPowTable(11);

What if n is not a prime number?

>	ModPowTable(6);

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 non-zero 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.

>	ModPowTable(8);

For 9, the relatively prime numbers are 1, 2, 4, 5, 7, and 8.

>	ModPowTable(9);

 

    9. Multiplicative Inverse

In the world of real numbers, every non-zero 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.

>	4 * (1/4);

>	(2/41) * (41/2);

>	(.0125) * 80;

>	-31 * (-1/31);

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",

>

3;

>	3*5 ;% = % mod 7;

How can we better understand this process? A quick consideration of the numbers mod 7 once again  :

>	ModPowTable(7);

Since n = 7 is prime, every non-zero 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.

>	h := order(3, 7);

>	3^(h-1); % mod 7;

>	3*5; % mod 7;

Find the reciprocal of 5 mod 11.

>	h := order( 5, 11);

>	5^(h-1); % mod 11;

>	5*9; % mod 11;

Find the reciprocal of 8 mod 17.

>	h := order( 10, 17);

>	10^(h-1); % mod 17;

>	10*12; % 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.

>	h := order( 8, 15);

>	8^(h-1); % mod 15;

>	8*2; % mod 15;

    10. Quadratic Residues

Just looking at the squares of integers mod 5, what is the set of values?

>	ModPowTable(5);

The only non-zero 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 :

>

x^2 = 4;

>	2^2 mod 5; 3^2 mod 5;

So the square roots of 4 mod 5 are 2 and 3.

What are the quadratic residues mod 7?

>	ModPowTable(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?

>	ModPowTable(9);

>

 

          2002 Waterloo Maple Inc & Gregory Moore, all rights reserved.