C: Elementary Number Theory

Here we review some basic number theoretic definitions and results. For the most part, we will just state the results. For a more detailed treatment, the student is referred references ,, or given in the bibliography. Unless otherwise stated in this appendix, all lower case letters, $a$, $b$, $c$, etc. will be integers. Recall that we use $\mathbb{N}$ to denote the set of natural numbers (also known as the positive integers) and we use $\mathbb{Z}$ to denote the set of all integers, i.e., $$\nonumber \mathbb{N}= \{ 1,2,3, \dots \}$$ and $$\nonumber \mathbb{Z}= \{ \dots, -3,-2,-1,0,1,2,3,\dots \}.$$

Definition C.1:

Let $a,b \in \mathbb{Z}$. We say $b$ divides $a$ and we write $b\ \vert\ a$ if there is an element $c \in \mathbb{Z}$ such that $a=bc$. We write $b \ \not \vert \ a$ if $b$ does not divide $a$.

If $b \ \vert \ a$ we also sometimes say that $b$ is a factor of $a$ or that $a$ is a multiple of $b$. To tell if $b$ divides $a$ where $b \neq 0$, we simply divide $a$ by $b$ and see if the remainder is 0 or not. More generally, we have the following fundamental result.

Lemma $\PageIndex{1}$ (The Division Algorithm)

For any integers $a$ and $b$ with $b \neq 0$ there exists unique integers $q$ and $r$ such that $$\nonumber a = bq+r, \qquad 0 \le r < |b|.$$

Definition C.2:

The number $r$ in the above Lemma is denoted by $a \bmod b$.

For example we have

$$\nonumber 17 \bmod 5 = 2 \qquad \mbox{ since \quad $17 = 3 \cdot 5 + 2$ \ and \ $0 \le 2 < 5$}$$ and $$\nonumber (-17) \bmod 5 = 3 \qquad \mbox{ since \quad $-17 = (-4) \cdot 5 + 3$ \ and \ $0 \le 3 < 5$}.$$

Definition C.3:

An integer $p$ is said to be prime if $p \ge 2$ and the only positive factors of $p$ are $p$ and 1.

Definition C.4:

Let $a$ and $b$ be integers, at least one of which is non-zero. The greatest common divisor of $a$ and $b$ is the greatest positive integer, $\gcd(a,b)$, that divides both $a$ and $b$. We define $\gcd(0,0)=0$.

Definition C.5:

If $a$ and $b$ are non-zero integers, the least common multiple of $a$ and $b$ is the smallest positive integer, $\text{lcm}(a,b)$, that is a multiple of both $a$ and $b$. If $a=0$ or $b=0$, we define $\text{lcm}(a,b) = 0$.

An important property of primes is given by the following lemma.

Lemma $\PageIndex{2}$

If $p$ is prime and $p | ab$ then $p | a$ or $p | b$.

Perhaps the most fundamental result concerning integers is the following theorem, which is sometimes called The Fundamental Theorem of Arithmetic.

Theorem $\PageIndex{3}$

If $n \ge 2$ is an integer, then there exists a unique list of primes $p_1, p_2, \dots, p_k$ such that the following two conditions hold:

1. $p_1 \le p_2 \le \cdots \le p_k$,
2. $n = p_1 p_2 \cdots p_k$

For example, if $n=72$ the unique list of primes is 2, 2, 2, 3, 3.

Now fix a positive integer $n$. Recall that $\mathbb{Z}_n = \{ 0, 1, \dots , n-1 \}$ and that multiplication and addition in $\mathbb{Z}_n$ are defined by

$a + b =$ remainder when the ordinary sum of $a$ and $b$ is divided by $n$, and

$a \cdot b =$ remainder when the ordinary product of $a$ and $b$ is divided by $n$.

To facilitate the proof that these two binary operations are associative, we temporarily denote addition in $\mathbb{Z}_n$ by $\oplus$ and multiplication in $\mathbb{Z}_n$ by $\odot$. This way we can use $+$ and $\cdot$ for ordinary addition and multiplication in $\mathbb{Z}$. Thus we have $$\begin{aligned} a \oplus b &=&(a + b) \bmod n \\ a \odot b &=& (ab) \bmod n\end{aligned}$$

Theorem $\PageIndex{4}$

Let $n$ be a positive integer. Define $f: \mathbb{Z}\to \mathbb{Z}_n$ by the rule $f(a) = a \bmod n$. Then

$$\begin{align} f(a + b) = f(a) \oplus f(b) \label{C1}\end{align}$$

and

$$\begin{align} f(a \cdot b) = f(a) \odot f(b). \label{C2} \end{align}$$

Proof Let $r_1 = f(a)$ and $r_2 = f(b)$. This implies that $$a = nq_1 + r_1, \quad 0 \le r_1 < n$$ and $$b = nq_2 + r_2, \quad 0 \le r_2 < n$$ Hence $$a+b= nq_1 + r_1 + nq_2 + r_2 = n(q_1+q_2) + r_1+r_2$$ Now $$f(a) \oplus f(b) = r_1 \oplus r_2 = r$$ where $$r_1 + r_2 = qn + r, \quad 0 \le r < n$$ Hence $$a+b=n(q_1+q_2+q) + r, \quad 0 \le r < n$$ and it follows that $$f(a+b)=(a+b) \bmod n = r,$$ and we conclude that $$f(a+b) = r = f(a) \oplus f(b).$$ This proves (C.1). The proof of (C.2) is similar and left to the interested reader.

Corollary $\PageIndex{5}$

The binary operations $\oplus$ and $\odot$ on $\mathbb{Z}_n$ are associative.

Proof Using the notation in the theorem, we have for $a,b,c \in \mathbb{Z}_n$: $f(a) = a$, $f(b) = b$ and $f(c) = c$. Hence $$\begin{aligned} (a \oplus b) \oplus b &=& (f(a) \oplus f(b)) \oplus f(c)\\ &=& f(a+b) \oplus f(b) \\ &=& f( (a+b)+c)\\ &=& f(a + (b+c)) \\ &=& f(a) \oplus f(b+c) \\ &=& f(a) \oplus( f(b) \oplus f(c)) \\ &=& a \oplus (b \oplus c)\end{aligned}$$ This proves that $\oplus$ is associative on $\mathbb{Z}_n$. The proof for $\odot$ is similar and left to the interested reader.