Elementary Number Theory

• Divisibility
  primes, division algorithm, greatest common divisor, fundamemtal theorem of arithmetic
• Congruences
  congruence, residue classes, Euler’s theorem
• Application (Public-key encryption)
  RSA, modular arithmetics, square and multiply, Euclidean algorithm, prime number generation, CRT
• Application (Key exchange)
  groups, subgroups, cyclic groups, Discrete logarithm, Diffie-Hellman key exchange

Divisibility

Notation:$\mathbb{N}=\left\{0,1,2,\dots\right\};\,\mathbb{Z}=\left\{0,\pm 1,\dots\right\};\,\mathbb{Q}=\left\{\frac{b}{a}:\, a,b\in\mathbb{Z},\, a\neq 0\right\}$(rational); $\mathbb{R}=\left\{a.b_1b_2\dots,\,a,b_1,b_2,\dots\in\mathbb{Z}\right\}$(real)

Definition: Let $a\in\mathbb{Z}\setminus\left\{0\right\}$ and let $b\in\mathbb{Z}$.

• $a$divides$b$: there is an integer $c\in\mathbb{Z}$ such that $b=ac$
• $a$ is a divisor of $b$; $b$ is a multiple of $a$
• $a\mid b$: $a$ divides $b$; $a\nmid b$: $a$ does not divide $b$
• $n\in\left\{2,3,\dots\right\}$ is a prime if the only positive divisors of $n$ are $1$ and $n$
• If $n\in\left\{2,3,\dots\right\}$ is not a prime, then $n$ is called a composite
• Example: $n$ is composite iff $\exist a,b\in\left(1,n\right)\cap\mathbb{Z}$ such that $n=ab$

Theorem (Fundamental Theorem of Arithmetic):
Every integer $n>1$ can be uniquely written as $n=p_1^{e_1}\dots p_r^{e_r}$, where $p_1<\dots<p_r$ are primes and $e1,\dots,e_r\geq 1$.

FTA Proof

Existence: by mathematical induction on the integer $n$

• $n=2$: $2=2^1$ is a product of prime powers
• Induction hypothesis: suppose there is an integer $k>2$ such that the theorem is true for all integers $n$ such that $2\leq n<k$
• Prove the theorem is true for $n = k$
  • $n=k$ is a prime
    • $n=k$ is a product of prime powers
  • $n=k$ is composite
    • There are integers $n_1,n_2$ such that $1<n_1,n_2<n$ and $n=n_1n_2$
    • By induction hypothesis, $n_1=p_1^{\alpha_1}\dots p_r^{\alpha_r}$ and $n_2=q_1^{\beta_1}\dots q_s^{\beta_s}$
      • $p_1,\dots,p_r,q_1,\dots,q_s$ are primes; $\alpha_1,\dots,\alpha_r,\beta_1,\dots,\beta_s\geq 1$
    • $n=n_1n_2=p_1^{\alpha_1}\dots p_r^{\alpha_r}\cdot q_1^{\beta}\dots q_s^{\beta}$ is a product of prime powers

Division Algorithm

The Well-Ordering Property: Every non-empty subset of $\mathbb{N}$ has a least element.

THEOREM (Division Algorithm):
Let $a,b\in\mathbb{Z}$ and $b>0$. Then there are unique $q,r\in\mathbb{Z}$ such that $0\leq r<b$ and $a=bq+r$.

• Existence: Let $S=\left\{a-bx:\,x\in\mathbb{Z}\text{ and }a-bx\geq 0\right\}$. Then
  • $S\neq\emptyset$ and $S\subseteq\mathbb{N}$
    • $S$ has a least element, say $r=a-bq\geq 0$
    • If $r\geq b$, then $r-b=a-b(q+1)\in S$ and $r-b<r$.
      • The contradiction shows that $0\leq r<b$.
• Uniqueness: Suppose that $q’,r’\in\mathbb{Z},\,0\leq r'<b$ and $a=bq’+r’$
  • Recall that $a=bq+r,\,0\leq r<b$
    • Then $b\left(q-q’\right)=r’-r\in(-b,b)$
      • It must be the case that $q=q’$ and thus $r=r’$

Ideal

$bq’+r’=bq+r$
$b\left(q’-q\right)=r-r’\in(-b,b)$

DEFINITION: Let $I \subseteq \mathbb{Z}$ be nonempty. $I$ is called an ideal of $\mathbb{Z}$ if:

• $a, b \in I \implies a + b \in I$; and
• $a \in I, r \in \mathbb{Z} \implies ra \in I$.
  • Example: $d\mathbb{Z} = {0, \pm d, \pm 2d, \dots}$ is an ideal of $\mathbb{Z}$ for all $d \in \mathbb{Z}$.

THEOREM: Let $I$ be an ideal of $\mathbb{Z}$. Then $\exists d \in \mathbb{Z}$ such that $I = d\mathbb{Z}$.

• If $I = \{0\}$, then $d = 0$.
• Otherwise, let $S = \left\{a \in I :\,a > 0\right\}$.
  • $S \subseteq \mathbb{N}$ and $S \neq \emptyset$.
  • due to the well-ordering property, $S$ has a least element, say $d \in S$.
    • $d\mathbb{Z} \subseteq I$:
      • $d \in I \implies dr \in I$ for any $r \in \mathbb{Z}$.
    • $I \subseteq d\mathbb{Z}$:
      • $\forall x \in I,\,x = dq + r,\,0 \le r < d$.
      • $r = x – dq \in I,\,0 \le r < d$.
      • $r = 0$ (otherwise, there is a contradiction)
      • $x = dq \in d\mathbb{Z}$.

DEFINITION: Let $I_1, I_2$ be ideals of $\mathbb{Z}$. Then the sum of $I_1$ and $I_2$ is defined as $I_1 + I_2 = \left\{x + y :\, x \in I_1, y \in I_2\right\}$

THEOREM: If $I_1, I_2$ are ideals of $\mathbb{Z}$, then $I_1 + I_2$ is an ideal of $\mathbb{Z}$.

• $\forall a, b \in I_1 + I_2,\, a + b \in I_1 + I_2$
  • $\exists x_1, x_2 \in I_1,\,y_1, y_2 \in I_2$ such that $a = x_1 + y_1;\,b = x_2 + y_2$
  • $a + b = (x_1 + x_2) + (y_1 + y_2) \in I_1 + I_2$
• $\forall a \in I_1 + I_2,\,r \in \mathbb{Z},\,ra \in I_1 + I_2$
  • $\exists x \in I_1,\,y \in I_2$ such that $a = x + y$
  • $ra = (rx) + (ry) \in I_1 + I_2$

EXAMPLE:$3\mathbb{Z} + 5\mathbb{Z} = \mathbb{Z};\,4\mathbb{Z} + 6\mathbb{Z} = 2\mathbb{Z}$

• $3\mathbb{Z} + 5\mathbb{Z} \subseteq \mathbb{Z}$: this is obvious
• $\mathbb{Z} \subseteq 3\mathbb{Z} + 5\mathbb{Z}$:
  • For every $n \in \mathbb{Z},\,n = 3 \cdot (2n) + 5 \cdot (-n) \in 3\mathbb{Z} + 5\mathbb{Z}$

Greatest Common Divisor

DEFINITION: Let $a, b \in \mathbb{Z}$ and at least one of them is nonzero.

• common divisor: an integer $d$ such that $d\mid a, d\mid b$
• greatest common divisor$\gcd(a, b)$: the largest common divisor
  • relatively prime:$\gcd(a, b) = 1$

THEOREM: Let $a, b \in \mathbb{Z}$ and at least one of them is nonzero. Then $a\mathbb{Z} + b\mathbb{Z} = \gcd(a, b)\mathbb{Z}$.

• ${a, b} \neq {0} \implies a\mathbb{Z} + b\mathbb{Z} \neq {0}$
• There exists $d \in \mathbb{Z} \setminus {0}$ such that $a\mathbb{Z} + b\mathbb{Z} = d\mathbb{Z}$. W.l.o.g., $d > 0$.
  • $d$ is a common divisor of $a, b:\,a \cdot 1 + b \cdot 0 \in d\mathbb{Z}$
  • $d$ is greatest: Suppose that $d’$ is a common divisor of $a, b$
    • $d’|a,\,d’|b$
    • $a\mathbb{Z} + b\mathbb{Z} = d\mathbb{Z} \implies d = as + bt$ for some integers $s, t$
    • $d’\mid d$ and thus $d’ \leq d$

THEOREM (Bézout): There exist $s,t\in\mathbb{Z}$ such that $\gcd(a,b)=as+bt$.