Definition (Book Definition 1.7.1)

Given integers $a$ and $b$, and a natural number $n$, we say that "$a$ is congruent to $b$ modulo $n$" and we write $$ \begin{align*} a \equiv b \bmod n \quad \text{or} \quad a \equiv_n b \end{align*} $$ if $a - b$ is divisible by $n$ or $n \ | \ a - b$. So there exists some $t \in \mathbf{Z}$ such that $a - b = tn$

Example: $(1 \bmod 7) = (8 \bmod 7) = 1$. Therefore, $1 \equiv_7 8$.

Definition

For each integer $a$, write $$ \begin{align*} [a] &= [a]_n = \{x \in \mathbf{Z} \ | \ x \equiv a \bmod n\} \subseteq \mathbf{Z} \\ &= \{ a + ny \ | \ y \in \mathbf{Z} \} \end{align*} $$ The set $[a]$ is called the residue class or congruence class of $a$ modulo $n$.

Example: $[2]_6 = \{2 + 6y \ | \ y \in \mathbf{Z}\} = \{ ...,-10,-4,2,8,14,20,... \}$
$[2]_6 = [8]_6 = [-10]_6 = [602]_6 = ....$

The Remainder Function

Another important definition that we need is the following

Definition

$rem_n \ : \ \mathbf{Z} \rightarrow \{0,1,2,...,n-1\}$ is the remainder function after dividing by $n$.
$rem_n(a) = r$ is the unique remainder of $a \div n$ such that $0 \leq r < n$ and $a = qn + r$ for some $q \in \mathbf{Z}$. Note that $a - r$ is divisible by $n$ or $a \equiv_n r$.

It’s important to note that the remainder is in the same congruence class as $a$. In fact $[a]_n \cap \{0,...n-1\} = \{r\}$. Usually the remainder $r$ is the standard/canonical name for the congruence class. So for example, we usually don’t write $[602]_6$ but write $[2]_6$. But we don’t have to put it in canonical form.

Properties of Congruence

Congruence is an equivalence relation. The following properties show this.

Lemma (Book 1.7.2)

Properties of Congruence:

Reflexive: For all $a \in \mathbf{Z}$, $a \equiv a \bmod n$.
Symmetric: For all $a, b \in \mathbf{Z}$, $a \equiv b \bmod n$ if and only if $b \equiv a \bmod n$.
Transitive: For all $a, b, c \in \mathbf{Z}$, if $a \equiv b \bmod n$ and $b \equiv c \bmod n$, then $a \equiv c \bmod n$.

Proof (book)
For $(a)$, $a - a = 0$ is divisible by $n$. For $(b)$, if $a - b$ is divisible by $n$, then $b - a$ is also divisible by $n$ and vice versa. For $(c)$, if $a - b$ is divisible by $n$ and $b - c$ is divisible by $4n$, then $(a - b) + (b - c) = a - c$ is also divisible by $n$. $\ \blacksquare$

Based on these properties, we have the following proposition

Proposition (Book Lemma 1.7.3)

For $a, b \in \mathbf{Z}$, the following are equivalent:

$a \equiv b \bmod n$.
$[a]_n = [b]_n$.
$\text{rem}_n(a) = \text{rem}_n(b)$.
$[a]_n \cap [b]_n \neq \emptyset$.

Proof (Book):
$(a) \implies (b)$:
Suppose $a \equiv b \bmod n$. We want to show that $[a]_n = [b]_n$.
$[a]_n \subseteq [b]_n$: Let $c \in \mathbf{Z}$. If $c \equiv a \bmod n$, then $c \equiv b \bmod n$ by Lemma 1.7.2 (c). Therefore $[a]_n \subseteq [b]_n$.
$[b]_n \subseteq [a]_n$: If $c \equiv b \bmod n$, then $c \equiv a \bmod n$ and so $[a] = [b]$ as required.

$(b) \implies (c)$:
By definition, $\text{rem}_n(x)$ is the unique element of $[x]$ that lies inside $\{0,1,...,n-1\}$. So if $[a]_n=[b]_n$, then it must be the same element.

$(c) \implies (d)$:
$(d)$ is an immediate application of $(c)$

$(d) \implies (a)$: Suppose that $[a]_n \cap [b]_n \neq \emptyset$. Let $c \in [a]_n \cap [b]_n$. Then $a \equiv c \bmod n$ and $b \equiv c \bmod n$. But this implies that $a \equiv b \bmod n$. $\ \blacksquare$

Modular Arithmetic

The following lemma establishes how modular arithmetic is done.

Proposition (Book Lemma 1.7.5)

Let $a, a', b, b'$ be integers with $a \equiv a' \bmod n$ and $b \equiv b' \bmod n$. Then $$ \begin{align*} a + b &\equiv a' + b' \bmod n \\ ab &\equiv a'b' \bmod n \end{align*} $$

Proof
[TODO]

We can now use these modular arithmetic properties to define algebraic structures on a set.

Definition

$$ \begin{align*} \mathbf{Z}_n &= \{ \text{ set of congruence classes mod } n \} \\ &= \{ [a]_n \ | \ a \in \mathbf{Z} \} \\ &= \{ [0]_n, [1]_n,...,[n-1]_n \ | \ a \in \mathbf{Z} \} \\ \end{align*} $$

So now we can use the operations we defined previously to turn this set into a commutative ring.

Definition

Define operations $+$, $\cdot$ on $\mathbf{Z}_n$ by $$ \begin{align*} [a]_n + [b]_n &= [a + b]_n \\ [a]_n[b]_n &= [ab]_n \end{align*} $$

$(\mathbf{Z}_n,+,\cdot)$ is commutative ring with identity while $(\mathbf{Z}_n,\cdot)$ is a commutative monoid. $[1]$ is the identity element.

Only some elements $[a] \in \mathbf{Z}_n$ have a multiplicative inverse. (such that $[a][b] = [1] = [b][a]$). The question is when do we have a multiplicative inverse? The answer is in the following proposition.

Proposition

Let $n \geq 1, a \in \mathbf{Z}$. Then $[a]$ has a multiplicative inverse in $\mathbf{Z}$ if and only if $gcd(a,n) = 1$.

Proof
Suppose that $gcd(a,n)=1$. Then there exists $r, s \in \mathbf{Z}$ such that $ar + ns = 1$. Re-writing this equation, we observe that

$$ \begin{align*} ar + ns = 1 &\Longleftrightarrow ar = 1 + (-s)n \quad \text{ (so $ar$ and 1 differ by a multiple of $n$)}\\ &\Longleftrightarrow ar = 1 \bmod n \\ &\Longleftrightarrow [a][r] = 1. \ \blacksquare \\ \end{align*} $$

We will use $\phi(n) = \{x \in \mathbf{Z}_n \ | \ x \text{ has a multiplicative inverse}\} \in \mathbf{Z}_n$.
$(\phi(n))$ is a commutative group.

Binomial Theorem

Next we have the binomial theorem which we need to prove a proposition which will then lead to Fermat’s Little Theorem.

Theorem (Binomial Theorem)

$a, b \in \mathbf{R}, n \in \mathbf{N}$. Then $$ \begin{align*} (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \end{align*} $$ where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for $a \leq k \leq n$

Proof
Use Pascal’s Identity: $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$… TODO

As a consequence of the binomial theorem, we have the next proposition

Proposition

Let $p$ be prime. For all $a, b \in \mathbf{Z}$: $$ \begin{align*} (a + b)^p \equiv a^p + b^p \bmod p \end{align*} $$

First observe that $(a+b)^5 = a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5$. So those middle terms all have coefficients divisible by 5. Therefore, they’ll go away if we apply mod $5$. This happens when $p$ is prime.

Proof
Using the binomial theorem, we can first expand the sum $(a+b)^p$ as follows

$$ \begin{align*} (a + b)^p &= \sum_{k=0}^{n} \binom{p}{k} a^{p-k} b^k \\ &= a^{p} + \binom{p}{1} a^{p-1} b + \binom{p}{2} a^{p-2} b^2 + ... + b^k \\ \end{align*} $$

What we need to show is that $\binom{p}{k} \equiv 0 \bmod p$ if $0 < k < p$. If we show this, then what’s left is the first and last terms only. Observe that

$$ \begin{align*} \binom{p}{k} &= \frac{p!}{k!(p-k)!} \\ \binom{p}{k} k! (p-k)! &= p! \\ \end{align*} $$

$p! = p(p-1)...1$. So $p \ | \ p!$. But $p! = \binom{p}{k} k! (p-k)!$ so $p$ divides this whole product. Since $p$ is prime, then $p$ must divide one of the factors. Now observe that $p$ can’t divide $k!$ since $k < p$. $p$ doesn’t divide $(p - k)!$ either since $p - k < p$. Therefore, $p$ must divide $\binom{p}{k}$ as desired. $\ \blacksquare$.

A consequence of this proof is Fermat’s Little Theorem

Fermat's Little Theorem

Next, we will prove Fermat’s Little Theorem.

Theorem

Let $p$ be prime, $a \in \mathbf{Z}$

$a^p \equiv a \bmod p$
If $p \nmid a$, then $a^{p-1} \equiv 1 \bmod p$

Proof of (1)

By Induction on $a$ for $a \geq 1$.
Base Case ($a = 1$): $1^p \equiv 1 \bmod p$ and so we're done.

Inductive Case ($a > 1$): Assume it is true for $a$. We will show that it is true for $a+1$.

$$ \begin{align*} (a + 1)^p &\equiv a^p + 1^p \quad \text{(By the previous proposition)} \\ &\equiv a + 1 \quad \text{(By the inductive hypothesis)} \end{align*} $$

Note that if $a = 0$, then $0^p = 0$.
For $a \leq 0$, we can use downward induction.

By Induction on $a$ for $a < 0$.
Base Case ($a = -1$): We need to show that $(-1)^p \equiv -1 \bmod p$. $p$ is prime so we have two cases. If $p = 2$, then $(-1)^2 = 1 = -1 \bmod 2$. If $p$ is odd, then $(-1)^p = -1$.

Inductive Case ($a < -1$): We want to show that $a^p \equiv a$ implies $(a - 1)^p = a - 1$.

Proof of (2)
We are given that $a \nmid p$. From part (1), we know that $a^p \equiv a \bmod p$. So $p \ | \ a^p - a = a(a^{p-1} - 1)$. But since $p$ is prime and since it doesn’t divide $p$, then it must divide $a^{p-1} - 1$.

Two-Prime Fermat

There is a more generalized version of Fermat’s Little Theorem. We will use Fermat’s theorem to prove it.

Theorem

Let $p, q$ be distinct primes and let $n = pq$. Let $m$ be $$ \begin{align*} m = lcm(p-1, q-1) = \frac{(p-1)(q-1)}{gcd(p-1,q-1)} \end{align*} $$ If $a \in \mathbf{Z}$, $h \in \mathbf{N}$ such that $h \equiv 1 \bmod m$, then $a^h \equiv a \bmod n$

Proof
We know that $h \equiv 1 \bmod m$ so $h = 1 + tm$ for some $t \in \mathbf{Z}$. We want to show that $a^h \equiv a \bmod n$. In other words, we want to show that $n \ | \ a^h - a$ which means that $pq \ | \ a^h - a$. We can write $a^h - a$ as follows

$$ \begin{align*} a^h - a &= a^{1+tm} - a \\ &= a(a^{tm} - 1). \end{align*} $$

Therefore, want to show that $pq$ divides $a(a^{tm} - 1)$. Lecture 5 Proposition (Corollary 1.6.17 in the book) states that if $a$ and $b$ are relatively prime, $a \ | \ n$ and $b \ | \ n$, $ab \ | \ n$. We’re given that $p$ and $q$ are distinct primes so they are relatively prime. So the goal is to prove that $p$ divides $a(a^{tm} - 1)$ and $q$ divides $a(a^{tm} - 1)$ to conclude that the product $pq$ divides $a(a^{tm} - 1)$.

To start, we want to show that $p \ | \ a(a^{tm} - 1)$. But since $p$ is prime, then it will have to divide $a$ or $a^{tm} - 1$. So we need to show that either $p \ | \ a$ or $p \ | \ a^{tm} - 1$. So suppose that $p \nmid a$. We claim that $p \ | \ a^{tm} - 1$. Recall that $m = lcm(p-1, q-1)$. So $m$ is a multiple of $p-1$ and we can write $m = (p - 1)s$ for some $s \in \mathbf{N}$. So now we can write $a^{tm}$ as follows

$$ \begin{align*} a^{tm} &= a^{ts(p-1)} \\ &= (a^{p-1})^{ts}. \end{align*} $$

Since we assumed that $p \nmid a$. Then we can use Fermat’s Little Theorem (part 2) to conclude that $a^{p-1} \equiv 1 \bmod p$. Now we can use modular arithmetic to simplify the original expression.

$$ \begin{align*} (a^{p-1})^{ts} &\equiv 1^{ts} \bmod p \text{ (because } a^{p-1} \equiv 1 \bmod p) \\ &\equiv 1 \bmod p. \end{align*} $$

This implies that $a^{tm} - 1$ must be divisible by $p$ as we wanted to show. So $p$ divides the product $a(a^{tm} - 1)$. With a similar argument, we can show this for $q$.

RSA Cryptosystem

This encryption method is based on the two prime fermat theorem. It is widely used to encrypt many of the transactions that happen on the internet.

Symmetric Encryption: We have some plain text ($x \in \mathbf{Z}_n$) that we want to encrypt. We have a function that takes a key ($e \in \mathbf{Z}$) to encrypt the plain text and turn it to encrypted text ($y \in \mathbf{Z}_n$). To decrypt it back, we have to use the same key again to turn it to plain text. The flaw in this method is that the encryption and decryption keys are the same and will need to be shared somehow. That’s why we have an alternative:

Asymmetric Encryption: This is the same proces except that now we have a decryption key $(d \in \mathbf{Z})$. So now we have a pair of keys $(e, d)$. You will broadcast $e$ so that anyone can encrypt a message and send it to you, but you are the only with the decryption key. The goal here is to design the pair such that one one can deduce $d$ from $e$. So how to design such a pair?

One way to implement this idea is the following (RSA):

Pick a prime number $p,q$ large (100s of digits)
$n = pq$
$m = lcm(p-1,q-1)$
Choose $1 < d, e < m$ such that $de \equiv 1 \bmod m$. You can first pick $d$ and then you can pick a multiplicative inverse of $d$ to be $e$ using the Euclidean Algorithm.

So now, you take the plain test $x$ and raise it to the $e$th power. $x^e$ is the encrypted text. $e$ is the encryption key. The output $y = x^e$ is the encrypted text. To decrypt it, raise the encrypted text to the $d$th power so $y^d = x^{ed}$ and so now we have the following equation

$$ \begin{align*} x^{ed} \equiv x \bmod pq \end{align*} $$

This is Two-prime Fermat.

References

MATH417 by Charles Rezk
Algebra: Abstract and Concrete by Frederick M. Goodman