$\mathfrak{Mini}$ $\mathbb{Wiki}$

4. February 2018 current version   

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

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

Proof.

  1. 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$.
  2. 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.

  1. 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$.
  2. 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$

This website uses cookies. By using the website, you agree with storing cookies on your computer. Also you acknowledge that you have read and understand our Privacy Policy. If you do not agree leave the website.More information about cookies