Section 15 Modular Arithmetic

We will require the package pracma, which you may recall from linear algebra, contains “practical math applications.” It has implementations of modular arithmetic and the GCD algorithms.

require(pracma)

15.1 Integer division and GCD

The mod function computes the remainder after division by \(n\) idivide gives the quotient. Thus, for example,

mod(68,15)

## [1] 8

idivide(68,15)

## [1] 4

Since \(68 = 15 \cdot 4 + 8\).

The greatest commond divisor GCD of two integers is computed with the gcd(m,n) command. For example,

gcd(70,42)

## [1] 14

gcd(68,15)

## [1] 1

telling us that \(gcd(70,42) = 14\) and \(gcd(68,15) = 1\), meaning that 68 and 15 are relatively prime.

The Extended GCD gives a little more information that can be quite useful in this course. If \(d = gcd(a,b)\) then there exist integers \(s,t \in \mathbb{Z}\) such that \[ d = s a+ t b. \] Furthermore, \(d = \gcd(a,b)\) is the smallest positive integer of the form \(s a + t b\). It follos that \(a\) and \(b\) are relatively prime if and only if it is possible to write \(1 = s a + t b\) for some \(s\) and \(t\).

You can find a proof of this fact in Chapter 0. We can use it here:

gcd(70,42,extended=TRUE)

## $g
## [1] 14
## 
## $c
## [1] -1
## 
## $d
## [1] 2

gcd(68,15,extended=TRUE)

## $g
## [1] 1
## 
## $c
## [1] 2
## 
## $d
## [1] -9

Telling us that \[ \begin{align*} 14 & = (-1) 70 + (2) 42 \\ 1 & = (2)68 + (-9) 15 \end{align*} \] As we can confirm with

2*68 - 9*15

## [1] 1

15.2 Addition Mod n: \(\mathbb{Z}_n\)

We can generate the finite cyclic group \(\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}\) easily as follows:

n = 12
G = 0:(n-1)  # generates an integer sequence from 0 to n-1.
G

##  [1]  0  1  2  3  4  5  6  7  8  9 10 11

And then we can add all of these elements mod n and make the Cayley table as follows:

n=6
G = 0:(n-1)
T = mod(outer(G,G,"+"),n)  # the outer sum computes a table of sums i + j
rownames(T) = G
colnames(T) = G
T

##   0 1 2 3 4 5
## 0 0 1 2 3 4 5
## 1 1 2 3 4 5 0
## 2 2 3 4 5 0 1
## 3 3 4 5 0 1 2
## 4 4 5 0 1 2 3
## 5 5 0 1 2 3 4

Even better, we can write a little function to do this.

CyclicCayley <- function(n,op="+") {
  G = 0:(n-1)
  T = mod(outer(G,G,op),n)
  rownames(T) = G
  colnames(T) = G
  return(T) 
  }

Then

CyclicCayley(5)

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

and

CyclicCayley(15)

##     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
## 0   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
## 1   1  2  3  4  5  6  7  8  9 10 11 12 13 14  0
## 2   2  3  4  5  6  7  8  9 10 11 12 13 14  0  1
## 3   3  4  5  6  7  8  9 10 11 12 13 14  0  1  2
## 4   4  5  6  7  8  9 10 11 12 13 14  0  1  2  3
## 5   5  6  7  8  9 10 11 12 13 14  0  1  2  3  4
## 6   6  7  8  9 10 11 12 13 14  0  1  2  3  4  5
## 7   7  8  9 10 11 12 13 14  0  1  2  3  4  5  6
## 8   8  9 10 11 12 13 14  0  1  2  3  4  5  6  7
## 9   9 10 11 12 13 14  0  1  2  3  4  5  6  7  8
## 10 10 11 12 13 14  0  1  2  3  4  5  6  7  8  9
## 11 11 12 13 14  0  1  2  3  4  5  6  7  8  9 10
## 12 12 13 14  0  1  2  3  4  5  6  7  8  9 10 11
## 13 13 14  0  1  2  3  4  5  6  7  8  9 10 11 12
## 14 14  0  1  2  3  4  5  6  7  8  9 10 11 12 13

15.3 Multiplication Mod n: \(U(n)\)

The group of units mod \(n\) is the set \[ U(n) = \{1 \le k < n \mid \gcd(k,n) = 1\} \] of integers that are relatively prime to \(n\). As you show in PS1.2, \(U(n)\) is group under multiplication mod \(n\). That is, you show that it is closed under multiplication and that every number that is relatively prime to \(n\) has a multipliciative inverse mod \(n\).

The functions below will give us \(\mathbb{Z}_n\) and \(U_n\).

Cyclic <- function(n) { 0:(n-1) }
Units <- function(n) { (1:(n-1))[gcd(1:(n-1),n)==1] }

For example,

Cyclic(10)

##  [1] 0 1 2 3 4 5 6 7 8 9

Units(10)

## [1] 1 3 7 9

We can multiply these by writing a MultTable function that uses the outer product

MultTable <- function(G,n,op="*") {
  T = mod(outer(G,G,op),n)
  rownames(T) = G
  colnames(T) = G
  return(T)
  }

And we try it out:

MultTable(Cyclic(10),10)

##   0 1 2 3 4 5 6 7 8 9
## 0 0 0 0 0 0 0 0 0 0 0
## 1 0 1 2 3 4 5 6 7 8 9
## 2 0 2 4 6 8 0 2 4 6 8
## 3 0 3 6 9 2 5 8 1 4 7
## 4 0 4 8 2 6 0 4 8 2 6
## 5 0 5 0 5 0 5 0 5 0 5
## 6 0 6 2 8 4 0 6 2 8 4
## 7 0 7 4 1 8 5 2 9 6 3
## 8 0 8 6 4 2 0 8 6 4 2
## 9 0 9 8 7 6 5 4 3 2 1

MultTable(Units(10),10)

##   1 3 7 9
## 1 1 3 7 9
## 3 3 9 1 7
## 7 7 1 9 3
## 9 9 7 3 1

MultTable(Units(2),2,op="*")

##   1
## 1 1

MultTable(Units(3),3,op="*")

##   1 2
## 1 1 2
## 2 2 1

MultTable(Units(5),5,op="*")

##   1 2 3 4
## 1 1 2 3 4
## 2 2 4 1 3
## 3 3 1 4 2
## 4 4 3 2 1

MultTable(Units(7),7,op="*")

##   1 2 3 4 5 6
## 1 1 2 3 4 5 6
## 2 2 4 6 1 3 5
## 3 3 6 2 5 1 4
## 4 4 1 5 2 6 3
## 5 5 3 1 6 4 2
## 6 6 5 4 3 2 1

MultTable(Units(11),11,op="*")

##     1  2  3  4  5  6  7  8  9 10
## 1   1  2  3  4  5  6  7  8  9 10
## 2   2  4  6  8 10  1  3  5  7  9
## 3   3  6  9  1  4  7 10  2  5  8
## 4   4  8  1  5  9  2  6 10  3  7
## 5   5 10  4  9  3  8  2  7  1  6
## 6   6  1  7  2  8  3  9  4 10  5
## 7   7  3 10  6  2  9  5  1  8  4
## 8   8  5  2 10  7  4  1  9  6  3
## 9   9  7  5  3  1 10  8  6  4  2
## 10 10  9  8  7  6  5  4  3  2  1

Suppose that we want to know the order of 5 in U(22). We could look at the Cayley table and keep multiplying by 5 until we get to 1.

MultTable(Units(22),22,op="*")

##     1  3  5  7  9 13 15 17 19 21
## 1   1  3  5  7  9 13 15 17 19 21
## 3   3  9 15 21  5 17  1  7 13 19
## 5   5 15  3 13  1 21  9 19  7 17
## 7   7 21 13  5 19  3 17  9  1 15
## 9   9  5  1 19 15  7  3 21 17 13
## 13 13 17 21  3  7 15 19  1  5  9
## 15 15  1  9 17  3 19  5 13 21  7
## 17 17  7 19  9 21  1 13  3 15  5
## 19 19 13  7  1 17  5 21 15  9  3
## 21 21 19 17 15 13  9  7  5  3  1

Or we can take the powers of 5 mod 22. Here are the first 10 powers of 5. We see that |5| = 5 in U(22).

5^(0:10)

##  [1]       1       5      25     125     625    3125   15625
##  [8]   78125  390625 1953125 9765625

mod(5^(0:10),22)

##  [1]  1  5  3 15  9  1  5  3 15  9  1