# Elementary Number Theory

## Numbers

A number is a mathematical object used to count, measure, and label.

**Natural Numbers**: $\mathbb{N} = \{0, 1, 2, 3, \dots \}$.**Integer Numbers**: $\mathbb{Z} = \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \} = \mathbb{Z}^- \cup 0 \cup \mathbb{Z}^+$.**Rational Numbers**: $\mathbb{Q} = \{ \frac{a}{b} | a,b \in \mathbb{Z} \text{ and } b \not= 0 \}$.**Real Numbers**: The limit of a convergent sequence of rational numbers, i.e. $\mathbb{R} = \{ \pi, e, \sqrt{2}, \dots \}$.**Complex Numbers**: $\mathbb{C} = \{a + bi | a,b \in \mathbb{R} \text{ and } i = \sqrt{i} \}$.

Therefore, we have $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{Q}$.

## Basis Representation

We use everyday the decimal system of notation. The number *ten* is said to be the * base* of decimal notation.

**Example**: In decimal system $196$ stands $1 \cdot 10^2 + 9 \cdot 10^1 + 6 \cdot 10^0 $.

#### Theorem (Basis Representation Theorem)

Let $k$ be any integer larger than 1. Then, for each positive integer $n$, there exists a *unique* representation

\begin{align*} n = a_s \cdot k^s + a_{s-1} \cdot k^{s-1} \cdot \dots \cdot a_1 \cdot k + a_0, \end{align*}

where each $a_i$ is non-negative and less than $k$, and where $s$ is the number of digits of representation; and it is called the * representation of $n$ to base $k$* . We denote this representation as $(a_s a_{s-1} \dots a_1 a_0)_k$.

Let \begin{align*} a_s \cdot k^s + a_{s-1} \cdot k^{s-1} \cdot \dots \cdot a_1 \cdot k + a_0 \end{align*} be the representation of $n$ in base $k$. Then each number of each digit must be less than the base $k$: \begin{align*} 0 \leq a_i < k \text{ where } 0 \leq i \leq s. \end{align*}

**Example**: What is the representation of $383$ to base $4$?

**1. Method**: For each step we try to find a number which is base of $4$, but less then $383$.

\begin{align*} \begin{split} 383 &= 256 \cdot 1, \text{Remainder: 127} \\ 127 &= 64 \cdot 1, \text{Remainder: 63} \\ 63 &= 16 \cdot 3, \text{Remainder: 15} \\ 15 &= 4 \cdot 3, \text{Remainder: 3} \\ 3 &= 1 \cdot 3, \text{Remainder: 0} \end{split} \end{align*}

Thus, $11333$ is the representation of $383$ in base $4$, and we denote it $383 = (11333)_4$.

**2. Method**: In each step we divide the number (or quotient of last step) by $4$, and the remainder gives us the number of representation of digit:

\begin{align*} \begin{split} 383 / 4 &= 95, \text{Remainder: 3} \\ 95 / 5 &= 23, \text{Remainder: 3} \\ 23 / 4 &= 5, \text{Remainder: 3} \\ 5 / 4 &= 1, \text{Remainder: 1} \\ 1 / 4 &= 0, \text{Remainder: 1} \end{split} \end{align*}

Thus, $11333$ is the representation of $383$ in base $4$, and we denote it $383 = (11333)_4$.

For an algorithmic perspective how it works, see this page.

## Divisibility

### Definition

If $a, b \in \mathbb{Z}$ we say that *$a$ divides $b$*, denoted $a | b$, iff there is an integer $k$ such that $ak = b$. We say that *$a$ does not divide $b$*, denoted $a \nmid b$, if there is no $k \in Z$ such that $ak = b$.

**Example:** $2 | 8$ but $3 \nmid 8$.

#### Lemma

- If $a | b$ and $b | c$, then $a | c$.
- If $a | b$ and $a | c$, then $a | sb + tc$ for all $s$ and $t$.

*Proof.*

- Since $a | b$, there exists $k$ such that $ak = b$; and since $b | c$, there exists $l$ such that $bl = c$. Therefore, $c$ can be written as $c = bl = (ak)l = a(kl)$. Thus, $a | c$.
- Since $a | b$, there exists $k$ such that $ak = b$; and since $a | c$, there exists $l$ such that $al = c$. So, $$sb + tc = s(ak) + t(al) = (sk + tl)a.$$ Therefore, $sb + tc = ma$ where $m = sk + tl$. Thus, $$a | sb + tc.$$

$\blacksquare$

### Euclid's Division Lemma

#### Theorem (Euclid's Division Lemma)

For any integers $a$ and $b$ where $b \not= 0$, there exist *unique* integers $q$ and $r$ such that $$a = b \cdot q + r, $$ where $0 \leq r < |b|$.

More formally, $$\forall a, b \in \mathbb{Z}, b \not= 0: \exists ! q, r \in \mathbb{Z}: a = b \cdot q + r \wedge 0 \leq r < |b|.$$

We call

- $a$ is the
**dividend**, - $b$ is the
**divisor**, - $q$ is the
**quotient**, - $r$ is the
**remainder**.

### The Greatest Common Divisor

#### Definition

If $a, b \in \mathbb{Z}$, a *common divisor* of $a$ and $b$ is an integer that divides both them. The *greatest common divisor*, denoted $gcd$, of $a$ and $b$ is the product of all common divisors of both them. Let $$\gcd(a,b) = \max\{ k \in \mathbb{Z}: k | a \text{ and } k | b \}.$$

**Example:** Let $a = 6$ and $b = 27$, then $\gcd(6, 27) = 3$.

#### Properties of the Greatest Common Divisor

- $\gcd(ka, kb) = k \cdot \gcd(a, b)$ for all $k > 0$.
- $(d | a \text{ } \mathtt{AND} \text{ } d | b) \text{ } \mathtt{IFF} \text{ } d | \gcd(a, b).$
- If $\gcd(a, b) = 1$ and $\gcd(a, c) = 1$, then $\gcd(a, bd) = 1$.
- If $a | bc$ and $\gcd(a, b) = 1$, then $a | c$.
- For any $a \in \mathbb{Z}$, $\gcd(a, 0) = \gcd(0 , a) = a$.
- $\gcd(0,0) = 0$.
- For any $a, b \in \mathbb{Z}$, we have $$\gcd(a,b) = \gcd(b,a) = \gcd(\pm a, \pm b) = \gcd(a, b-a) = \gcd(a, b+a).$$

### Euclid's Division Algorithm

#### Theorem (Euclidean algorithm)

Suppose $a$ and $b$ are integers and $b \not= 0$. The Euclid's Algorithm computes the greatest common divisor of $a$ and $b$ by using the division lemma such that $a = bq + r$ and $0 \leq r < |b|$. More algorithmically $$\gcd(a,b) = \gcd(b, rem(a, b)),$$ where $r = rem(a,b)$. Since it is a recursive algorithm we have a sequence of computations (equations) as follows:

\begin{align*} \begin{split} a &= b q_0 + r_0 \\ b &= r_0 q_1 + r_2 \\ r_0 &= r_2 q_2 + r_3 \\ \vdots \\ r_{k-2} &= r_{k-1} q_k + r_k \\ r_{k-1} &= r_k q_{k+1} + 0 \end{split} \end{align*}

It follows from the previous formula that the **assertion** $ 0 < r_k < r_{k-1} < \dots < r_3 < r_2 < r_0 < b$ holds. Hence, $\gcd(a, b) = r_k$.

*Proof.* The proof consists of two parts.

- Start with proving that $r_k$ is indeed a greatest common divisor of $a$ and $b$: $$r_k | r_{k-1} \Rightarrow r_k | \underbrace{r_{k-1} q_k + r_k}_{r_{k-2}} \Rightarrow \dots \Rightarrow r_k | \underbrace{r_0 q_1 + r_1}_{b} \Rightarrow r_k | \underbrace{b q_0 + r_0}_{a} \Rightarrow r_k | a.$$ Thus, $r_k | a$ and $r_k | b$.
- The second part is to show that there exists a common divisor $t \in \mathbb{Z}$ such that $t | a$ and $t | b$ implies $t | r_k$. Suppose $t | a$ and $t | b$, then $$t | \underbrace{a - b q_0}_{r_0} \Rightarrow t | r_1 \Rightarrow \dots \Rightarrow t | r_k.$$

$\blacksquare$

For an algorithmic perspective how it works, see this page.

**Example:** Find the greatest common divisor of $2863$ and $1057$ by using Euclidian Algorithm.

\begin{align*} \begin{split} 2863 &= 2 \cdot 1057 + 749 \\ 1057 &= 1 \cdot 749 + 308 \\ 749 &= 2 \cdot 308 + 133 \\ 308 &= 2 \cdot 133 + 42 \\ 133 &= 3 \cdot 42 + 7 \\ 42 &= 6 \cdot 7 + 0 \end{split} \end{align*}

Thus, $\gcd(2863, 1057) = 7.$

#### Theorem (Linear Combination)

If $k = \gcd(a, b)$, then $k = sa + tb$ for some $s, t \in \mathbb{Z}$.

*Proof.* From Lemma above we already know that every linear combination of $a$ and $b$ is divisible by any common factor of $a$ and $b$. From Euclid's Division Algorithm we conclude that $$r_{k-1} = r_k q + r_{k+1};$$ thus, $$(a s_{k-1} + b t_{k-1}) - (a s_k + b t_k) = r_{k+1}.$$ We can rewrite that as follows $$(s_{k-1} - s_k) a + (t_{k-1} - t_k) b = r_{k+1}.$$ Hence, $s_{k+1} = s_{k-1} - s_k$ and $t_{k+1} = t_{k-1} - t_k$ are solutions for a general equation $a s_i + b t_i = r_i$ when $i = k + 1$. This formula is established for $i = 1, 2, \dots, n-1$, by the principle of mathematical induction. In particular, if $i = n-1$, we get $a s_{n-1} + b t_{n-1} = r_{n-1} = \gcd(a,b).$

$\blacksquare$

## Prime Numbers

### Definition

A *prime* is a number greater than $1$ that is divisible only by itself and $1$. A number other than $0, 1,$ and $-1$ that is not a prime is called *composite*.

More formally, $$ \exists p, \forall k \in \mathbb{Z}, k \not= p, -p, 0, 1, -1 : p | p \wedge 1 | p \wedge k \nmid p. $$

The set of all prime numbers denoted by $\mathbb{P}$.

#### Theorem

Let $p \in \mathbb{P}$. If $p | a \cdot b$, then $p | a$ or $p | b$.

*Proof.*

**Case 1:**If $p | a$, then the proof is done.**Case 2:**Let $p \nmid a$, then $\gcd(p, a) = 1$, means that $\exists e, f \in \mathbb{Z}$ such that $ep + fa = 1$. It follows that $$b = b \cdot 1 = b \cdot (ep + fa) = \underbrace{bep}_{\text{multiple of }p} + \underbrace{bfa}_{\text{multiple of }p}.$$ Therefore, $p | b$.

$\blacksquare$