Integer Arithmetic

1. Division Algorithm

---

(Def)
Let $a, b\in Z$ and $b \ne 0$.
$b \mid a$ if $\exists \in Z$ s.t. $a = bc$ and
$b \nmid a$ otherwise.

---

(Division Algorithm)
For $a, n \in Z$ and $n > 0$, $\exists!q, r \in Z$ s.t. $a = n \times q + r, 0 \leq r \le n.$
If $r = 0$, then $n \mid a$.

---

(Greatest Common Divisor)
(Def)
The greatest common divisor of a and b is the largest integer that can divide both integers.

(Note)
$ a = b \times q + r, 0 \leq r \le n$
Fact 1: $gcd(a, 0) = a$
Fact 2: $gcd(a, b) = gcd(b, r)$

2. Euclidean Algorithm

(Note)
When $gcd(a, b) = 1$, we say that a and b are relatively prime.

Example
Q : Find the greatest common divisor of 2740 and 1760.
A : 20

3. Extended Euclidean Algorithm

Given two integers $a$ and $b$, we often need to find other two integers, $s$ and $t$, such that

$$a \times s + b \times t = gcd(a, b).$$

The extended Euclidean algorithm can calculate the $gcd(a, b)$ and at the same time calculate the value of $s$ and $t$.

Input : $a$, $b$
Output : $s$, $t$, $gcd(a, b)$ such that $as + bt = gcd(a, b)$

Considier $r_j = r_{i+1} \cdot q_{j+1} + r_{j+2}\quad(\,j = 0, \ldots, n - 2)$
and $r_{n+1} = r_n \cdot q_n + 0$ in Euclidean Algorithm

Define $s_0 = 1, t_0 = 0, s_1 = 0, t_1 = 1$

$$\begin{cases} s_j = s_{j-2} - q_{j-1} \cdot s_{j-1} \\ t_j = t_{j-2} - q_{j-1} \cdot t_{j-1} \quad \text{for}\,(\,j = 2, \ldots, n) \end{cases}$$ $$\Rightarrow r_j = s_ja + t_jb \quad (\,j = 0, \ldots, n)\\ r_n = gcd(a, b)$$

pf)

$$r_0 = s_0a + t_0b = a \\ r_1 = s_1a + t_1b = b$$

Suppose that $r_j = s_ja + t_jb \quad (\,j = 2, \ldots, k - 1)$

$$\begin{align} r_k & = r_{k-2} - r_{k-1} \cdot q_{k-1} \\ & = (s_{k-2}a + t_{k-2}b) - q_{k-1}(s_{k-1}a + t_{k-1}b) \\ & = (s_{k-2} + s_{k-1} \cdot q_{k-1})a + (t_{k-2} + t_{k-1} \cdot q_{k-1})b \\ & = s_ka + t_kb \end{align}$$

Example
Q : Given a = 161 and b = 28, find gcd (a, b) and the values of s and t.
A : $gcd (161, 28) = 7$, $s = −1$ and $t = 6$.

4. Linear Diophantine Equation

Given $ax + by = c$ for $a, b, c \in Z$,
find $x, y \in Z$

Let $d = gcd(a, b).$
By Extended Euclidean Algorithm, we can find $s$ and $t$ s.t. $as + bt = d$

1) Particular solution:

$x_0 = \left(\frac{c}{d}\right) s \quad $ and $\quad y_0 = \left(\frac{c}{d}\right) t$

2) General solutions:

$$d = gcd(a, b) \\ ax + by = ax_0 + by_0 = c \\ a(x - x_0) = b(y_0 - y) \\ \frac{a}{d}(x - x_0) = \frac{b}{d}(y_0 - y) \\ gcd(\frac{a}{d}, \frac{b}{d}) = 1 \\ \therefore \frac{a}{d} \mid y_0 - y, \quad \frac{b}{d} \mid x - x_0$$

$x = x_0 + \left(\frac{b}{d}\right)k \quad $ and $\quad y = y_0 - \left(\frac{a}{d}\right)k,\quad k \in Z$