# C: Elementary Number Theory

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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.

This page titled C: Elementary Number Theory is shared under a not declared license and was authored, remixed, and/or curated by W. Edwin Clark via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.