Number Theory

$ \def\ZZ{\mathbb{Z}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} $

Mod (Remainder) Operation

For numbers $a$ and $n$, the mod operation $a \bmod n$ returns the remainder $r$ when you divide $a$ by $n$. More formally,

$a \bmod n$ is a positive integer $r$ with $0 \le r \le n-1$ such that there is some integer $q$ with $a = qn + r$.

Examples:

$0 \bmod 5 = 0$.
$10 \bmod 5 = 0$.
$14 \bmod 5 = 4$.
$-1 \bmod 5 = 4$.

Equivalence in mod $n$

For two numbers $a$ and $b$, if $a \bmod n = b \bmod n$, we write $$ a = b \pmod n.$$

From now on, we will be mainly concerned with the remainders. Any other number will be reduced to (and treated as) its equivalent remainder.

Modular Multiplication: Take Mod As Early As Possible

The following holds:

$a \cdot b \bmod n = (a \bmod n) \cdot (b \bmod n) \bmod n$.

Since $a \bmod n$ is smaller than $a$, computations will be much simpler if you take the mod operation as early as possible.

Examples:

$34 \cdot 58 \bmod 11 = 1 \cdot 3 \bmod 11 = 3$
$102345 \cdot 12334 \bmod 10 = 5 \cdot 4 \bmod 10 = 0$

Multiplicative Inverse in mod $n$

We say $b$ is an inverse of $a$ in $\bmod n$ if it holds $$a \cdot b = 1 \pmod n$$

We write $b = a^{-1} \bmod n$.

Examples:

$3^{-1} \bmod 5$ is $2$, since $3 \cdot 2 = 1 \pmod 5$.
$2^{-1} \bmod 15$ is $8$, since $2 \cdot 8 = 1 \pmod {15}$.

Quick check

What is $4^{-1} \bmod 7$?
```
2
```
What is $2^{-1} \bmod 4$?
```
There is no inverse. 
```

Important: Please remember this.

$a^{-1} \bmod n$ exists only if $gcd(a, n) = 1$.

Notation: $\ZZ_n^*$

$\ZZ_n^*$ is a set containing the positive integers $a$ where satisfying the following conditions:

The integer $a$ must be such that $1 \le a \le n-1$, and
the integer $a$ must be such that $gcd(a, n) = 1$.

We say $a$ and $n$ are relatively prime (or coprime) if $gcd(a,n) = 1$.
Following the above note about the existence of inverses, all the numbers in $\ZZ_n^*$ have their inverses (in $\bmod n$).

Examples

$\ZZ_5^* = \{1, 2, 3, 4\}$

$\ZZ_{15}^* = \{1, 2, 4, 7, 8, 11, 13, 14\}$.

Quick Check

What is $\ZZ_{10}^*$?

{1, 3, 7, 9}

Modular Exponentiation

Naturally, we can think about modular exponentiation as follows: $$a^b \bmod n = \underbrace{a \cdot a \cdots a}_{\mbox{b times}} \bmod n.$$

Example 1

In Python, we use pow(a, b, n) to compute $a^b \bmod n$ quickly. Consider the following code:


for i in range(1, 21):
  print(pow(2, i, 5), end=" ")

The output is as follows:

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

Observation

We see a cycle.
1. The length of the cycle is 4.
2. The cycle ends in 1.
Why is the length of the cycle 4? This is really $|\ZZ_5^*|$.

Example 2

We saw that $\ZZ_{10}^*$ has 4 numbers in itself. This means that the length of the cycle should be 4, right?


for i in range(1, 20):
  print(pow(3, i, 10), end=" ")

The output is as follows:

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

This is actually true!

Example 3

Let's check if this is true for every number smaller than 10.


for a in range(10):
  print("a=", a, ":", end=" ")
  for i in range(1, 21):
    print(pow(a, i, 10), end=" ")
  print()

The output is as follows:

a= 0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a= 1 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
a= 2 : 2 4 8 6 2 4 8 6 2 4 8 6 2 4 8 6 2 4 8 6
a= 3 : 3 9 7 1 3 9 7 1 3 9 7 1 3 9 7 1 3 9 7 1
a= 4 : 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6
a= 5 : 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
a= 6 : 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
a= 7 : 7 9 3 1 7 9 3 1 7 9 3 1 7 9 3 1 7 9 3 1
a= 8 : 8 4 2 6 8 4 2 6 8 4 2 6 8 4 2 6 8 4 2 6
a= 9 : 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1

Well, our conjecture is not quite true.

However, let's focus on the number is $\ZZ_{10}^* = \{1, 3, 7, 9\}$.

We see a cycle for each of the numbers in $\ZZ_{10}^*$.
The length of the cyle is 1, 2, 4. Each cycle ends in 1. What is this?
```
They are all factors of 4!
```
In summary for any number $a \in \ZZ_n^*$:
1. The maximum length of the cycle is $|\ZZ_{n}^*|$.
2. Each cycle length can be smaller, but it should be a factor of $|\ZZ_{n}^*|$.

There is Something Special About $|\ZZ_{n}^*|$

Euler, a great mathemacian of all time, named this as Euler's phi function.

Define $\phi(n) := |\ZZ_n^*|$.

What we observed above can be nicely put as follows:

Important: Please remember this --- Euler's Thereom

For any $n$ and any $a \in \ZZ_N^*$, we have $$a^{\phi(n)} \bmod n = 1.$$

Note: If $a \not \in \ZZ_N^*$, this theorem doesn't apply!

This can be easily verified because:

Since $a \in \ZZ_n^*$, we will see a cycle ending in a 1.
The length of a cycle is a factor of $\phi(n)$.
So, $a^{\phi(n)} \bmod n$ will circle around (possible some more times depending on the cycle length) and eventually end in a 1.

Computing $\phi()$

It turns out that computing the function $\phi$ is pretty easy:

If $p$ is a prime number, $\phi(p) = p-1$.
If $p$ and $q$ are distinct prime numbers, $\phi(p \cdot q) = (p-1)\cdot (q-1)$.

Examples

Consider $\ZZ_5^*$. We know $\phi(5) = 4$.

$2^4 \bmod 5 = 16 \bmod 5 = 1$.
$3^4 \bmod 5 = 81 \bmod 5 = 1$.
$4^4 \bmod 5 = 4^2 \cdot 4^2 \bmod 5 = 1 \cdot 1 \bmod 5 = 1$.

Consider $\ZZ_{15}^*$. We know $\phi(15) = 8$.

$2^8 \bmod 15 = 2^4 \cdot 2^4 \bmod 15 = 1 \cdot 1 \bmod 15 = 1.$
$3^8 \bmod 15 = 6$. Note $3 \in \ZZ_{15}^*$, and the Euler's theorem doesn't apply.

Quick Check

What is $3^{61} \bmod 7$?