Number Theory

Basics of number theory

In this section, we’ll introduce the basic concepts of number theory, which are later used to determine the properties of algebraic structures. We denote the set of integers by the symbol

$\mathbb{Z} = \{\cdots,-2,-1,0,1,2,\cdots\}$. The following statements hold for the usual addition, subtraction, and multiplication:

Lemma 1: closure property

Let a, b ∈ $\mathbb{Z}$.

Then, the following hold:

1. $a+b \in \mathbb{Z}$
2. $a-b \in \mathbb{Z}$
3. $a \cdot b \in \mathbb{Z}$

This means that the common addition, subtraction, and multiplication operations yield an integer as a result. We say that the set of integers is closed under these operations (we’ll learn this concept in detail in the next lessons).

In contrast, the division of two integers a and b isn’t necessarily yielding an integer as a result, thus, the integers aren’t closed with respect to the division. For example, we can’t divide $3$ by $2$ because $\frac{3}{2} \notin \mathbb{Z}$. As a consequence, we need a fundamental concept of divisibility in number theory.

Divisibility

Let a,b ∈ Z with b ≠ 0. We say that $b$ divides $a$, or $a$ is divisible by $b$, if there exists an $n$ ∈ Z such that: $a=n⋅b$

If b divides a, we write $b \mid a$, otherwise, we write $b \nmid a$.

Example: It holds that $13 \mid 39$, since $39 = 3 *13$ . On the other hand, $13 \nmid 40$.

The following lemma states some elementary divisibility properties.

Lemma 2: properties of divisibility

Let $a, b , c \in \mathbb{Z}$⧵{0}.
Then:

1. If $a \mid b$, then $ac \mid bc$, and vice versa.
2. Transitive property: If $a \mid b$ and $b \mid c$, then $a \mid c$.
3. If $n \mid a$ and $n \mid b$, then $n \mid (a+b)$ and $n \mid (a-b)$.

Proof:

1. Since $a \mid b$, there exists an $n \in \mathbb{Z}$ such that $b=n \cdot a$. It follows that $b \cdot c=n \cdot a \cdot c=n \cdot(a \cdot c)$ and hence $a c \mid b c$. For the reverse direction, we observe that $a c \mid b c$ requires an $n \in \mathbb{Z}$ so that $b \cdot c=n \cdot(a \cdot c)=n \cdot a \cdot c$. Since $c \neq 0$, it follows that $b=n \cdot a$ and hence $a \mid b$.
2. $a \mid b$ and $b \mid c$ imply that there exist $m, n \in \mathbb{Z}$ so that we can write $b=m \cdot a$ and $c=n \cdot b$, respectively. It follows that $c=n \cdot b=n \cdot m \cdot a=$ $(n \cdot m) \cdot a$, and thus $a \mid c$.
3. $n \mid a$ and $n \mid b$ imply the existence of $m_{1}, m_{2} \in \mathbb{Z}$ so that $a=m_{1} \cdot n$ and $b=m_{2} \cdot n .$ This yields $a \pm b=m_{1} \cdot n \pm m_{2} \cdot n=\left(m_{1} \pm m_{2}\right) \cdot n$ and hence $n \mid(a \pm b)$.

Greatest common divisor

A positive integer $n$ $\in$ $\mathbb{N}$ is called a common divisor of two integers $a$ and $b$, if $n$ divides both of them. The greatest common divisor of a and b is the largest integer $n$ such that $n \mid a$ and $n \mid b$ and is denoted by $gcd(a, b)$.

Note: Especially, $gcd(1, n) = 1$ and $gcd(0, n) = n$.

Example: $gcd(48, 72) = 24$ since $24 \mid 48$ and $24 \mid 72$, and there’s no larger number than $24$, which fulfils this property.

Prime numbers:

Let $p$ be a positive integer $p \geq 2$. Then, $p$ is said to be a prime if its only divisors are $1$ and $p$ itself, i.e.,

$$gcd(a,p) = 1$$

for all $0 \le a < p$.

Note: $1$ is a prime number because 1 can be divided by 1 and the number itself, which is also 1.

Example:

All the primes smaller than $20$ are $2, 3, 5, 7, 11, 13, 17, 19$. For example, $6$ is not a prime since $6 = 2 \cdot 3$, and hence, $2$ and $3$ are divisors of $6$.

Theorem 1: fundamental theorem of arithmetic

Every positive integer $n \ge 2$ can be represented as a product of prime powers

$$n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}=\prod_{i=1}^{k} p_{i}^{\alpha_{i}}$$

This factorization is unique apart from the rearrangement of the prime powers.

Note: The greatest common divisor of two numbers $a$ and $b$ can be computed by determining their prime factorizations, whereas the greatest common divisor is the product of all common prime powers of $a$ and $b$. This is depicted in the above figure using the prime factorization tree.

Example:

Consider the two numbers $48$ and $72$. Their prime factorizations are given by $48=2^{4} . {3}$ and $72 = 2^3 . 3^2$ . We observe that a and b have common prime powers $2^3$ and $3$, and therefore $gcd(a, b) = 2^3 . 3 = 24$.

Theorem 2: there are infinitely many primes

Proof:

Suppose that there’s a complete finite list of primes $p_{1}, p_{2}, \cdots, p_{k}$. We construct the two integers $n_{1} = p_{1} \cdot p_{2} \cdots p_{k}$ and $n_{2} = p_{1} \cdot p_{2} \cdots p_{k}+1$. By the fundamental theorem of arithmetic, every integer is a product of primes divisible by at least one prime. Since $n_{1}$ is a product of all primes, there’s a prime $p$ such that $p \mid n_{1}$ and $p \mid n_{2}$. According to Lemma 2: properties of divisibility, $p \mid n_{1}$ and $p \mid n_{2}$ imply that $p \mid (n_2 - n_1)$. Hence, $p \mid (p_{1} \cdot p_{2} \cdots p_{k} + 1 - p_{1} . p_{2} \cdots p_{k} )=1$, which means that $p$ divides 1. But this isn’t possible since $p$ is a prime, and therefore $p \geq 2$. Thus, a list of finite primes can’t exist as $p$ will not be a member of it.

Relatively prime (or coprime)

Two integers $a$ and $b$ are said to be relatively prime (or coprime) if $gcd(a, b) = 1$.

Example:

We consider the following two cases:

1. $21$ and $22$ are relatively prime, since $21 = 3 \cdot 7$ and $22 = 2 \cdot 11$. Thus, they have no common prime factors, and therefore $gcd(21, 22) = 1$.
2. $21$ and $24$ are not relatively prime, since $21 = 3 \cdot 7$ and $24 = 2^3 \cdot 3$, and therefore $gcd(21, 24) = 3$.

Lemma 3: Bézout’s identity

For any nonzero integers $a, b \in \mathbb{Z}$, let d be the greatest common divisor $d = gcd(a, b)$. Then, there exist $x, y \in \mathbb{Z}$ such that

$$ax+by = d$$

Corollary 1

Two integers $a, b \in \mathbb{Z} \setminus \begin{Bmatrix} 0 \end{Bmatrix}$ are co-prime if and only if there exist $x, y \in \mathbb{Z}$ such that

$$ax+by = 1$$

Proof:

Two integers $a, b$ are relatively prime if and only if $gcd(a, b) = 1$. Then, it’s a direct consequence of Bézout’s lemma that there exists $x, y \in \mathbb{Z}$ such that $ax+by = gcd(a,b) = 1$.

Lemma 4

Let $a , b \in \mathbb{Z} \setminus \begin{Bmatrix} 0 \end{Bmatrix}$ and $n\in \mathbb{N}$. If $a$ and $b$ are coprime to $n$, then it’s also its product $a\cdot b$, i.e., if $gcd(a, n) = gcd(b, n) = 1$, then $gcd(ab, n) = 1$.

Proof:

Suppose that $gcd(a, n) = gcd(b, n) = 1$. As discussed earlier , there exist $s, t, x, y \in \mathbb{Z}$ such that $as + nt = 1$ and $bx + ny = 1$, and thus, in total

$$(as + nt)(bx + ny) = 1$$

It follows that

$$a b s x+a n s y+b n t x+n n t y=a b \cdot s x+n \cdot (a s y+b t x+n t y)=1.$$

Here, $sx \in \mathbb{Z}$ and $(a s y+b t x+n t y) \in \mathbb{Z}$.

By applying again the corollary discussed earlier, we conclude that $gcd(ab, n) = 1$.

Lemma 5

Let $a, b \in \mathbb{Z}$, and let $d = gcd(a, b)$. Then, the two integers $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime, i.e., $gcd ( \frac{a}{d} , \frac{b}{d} ) = 1$.

Proof:

According to the fundamental theorem of arithmetic , we define $a$ and $b$ as a product of prime powers, i.e., $a = \prod_{i=1}^{k} p_{i}^{\alpha_{i}}$ and $b = \prod_{i=1}^{l} p_{i}^{\beta_{i}}$. Then, $d=gcd(a,b)=\prod_{s=1}^{t} p_{s}^{\gamma{s}}$, whereas $p_{s}^{\gamma{s}}$ are the common prime powers of $a$ and $b$. As a consequence, the two integers $\frac{a}{d}$ and $\frac{b}{d}$ have no common prime powers, and hence $gcd( \frac{a}{d} , \frac{b}{d} ) = 1$.