Number Theorem 1st note

$a,b,c$: integers; $m,n$: positive integers; $\mathbb{Z}$: set of integers; $\mathbb{N}$: set of positive integers; $\mathbb{R}$: set of real numbers; $\mathbb{C}$: set of all complex numbers.

Theorem 1.1

If $a,b \in {\mathbb{Z}}$ with $b > 0$, then there is a unique pair of integers $q$ and $r$ such that $a = qb + r$ and $0 \leq r < b$.

Pf

The set $S = \left\{ a - nb~|~n \in {\mathbb{Z}} \right\}$ contain some non-negative integers, so $S \cap {\mathbb{N}}$ has a least element, say $r = a - qb \geq 0$ for some integer $q$. Then it's easy to see that such an $r$ is our desired.

Rmk 1.2

We can replace $b > 0$ by $b \neq 0$, then we require $0 \leq r < |b|$.

Def 1.3

If $r = 0$, we say that $b$ divides $a$, denote $b|a$. In this case we also say that $b$ is a factor of $a$, or $a$ is a multiple of $b$. According to this, every integer divides $0$.

Ex 1.4

If $n$ is a square, then $n$ leaves a reminder $0$ or $1$ after divides by $4$.

$n = 2k,n^{2} = 4k^{2};n = 2k + 1,n^{2} = 4k^{2} + 4k + 1$

Prop 1.5

If $c$ divides $a_{1},\ldots,a^{k}$, then $c$ divides any $\mathbb{Z}$-linear combination of $a_{1},\ldots,a_{k}$.

Def 1.6

If $d|a$ and $d|b$, we say that $d$ is a common divisor of $a$ and $b$. All common divisors of $a$ and $b$ are clearly bounded (unless $a = b = 0$). So there is a unique greatest common divisor of $a$ and $b$, denote by $\gcd(a,b)$.

Lemma 1.7

If $a = qb + r$ then $\gcd(a,b) = \gcd(b,r)$

Pf

Use Prof 1.5 and notice that $r = a - qb$.

We can use Lemma 1.7 repeatedly to compute $\gcd(a,b)$ for any integer $a$ and $b$.

After ruling out a few trivial cases, we may assume $a > b > 0$. By division algorithm, we write $a = q_{1}b + r_{1}$. If $r_{1} = 0$, then $d = b$ and we are done. Otherwise we write $b = q_{2} \cdot r_{1} + r_{2}$. If $r_{2} = 0$, then $d = r_{1}$ and we are done. Continue in this fashion, we reach the least two steps $$\begin{aligned} r_{n - 3} & = q_{n - 1} \cdot r_{n - 2} + r_{n - 1} & \text{ with } & 0 < r_{n - 1} < r_{n - 2} \\ r_{n - 2} & = q_{n - 1} \cdot r_{n - 1} + r_{n} & \text{ with } & r_{n} = 0 \end{aligned}$$

Theorem 1.8 (Euclid's algorithm)

In the above calculation we have $\gcd(a,b) = r_{n - 1}$.

Ex 1.9

Calculate $\gcd(1817,2024) = 23$.

Rmk 1.10

The result extends to any Euclidean ring. For example, the polynomial ring ${\mathbb{Q}}\lbrack x\rbrack$.

Theorem 1.11 (Bezout's identity)

If $a,b \in {\mathbb{Z}}$ not both $0$, then there exists integers $u$ and $v$ such that $\gcd(a,b) = u \cdot a + v \cdot b$.

Pf

Euclid's algorithm + induction

Start from $\gcd(a,b) = r_{n - 1} = r_{n - 3} - q_{n - 1} \cdot r_{n - 2}$, then eliminate $r_{n - 2}$ using $r_{n - 2} = r_{n - 4} - q_{n - 2} \cdot r_{n - 3}$. Working backwards this way until we reach $r_{n - 1} = au + bv$ for some $u,v \in {\mathbb{Z}}$.

Extended these results to $h$ numbers [Exercise 1.11] using the identity [Exercise] $$\gcd(a_{1},\ldots,a_{k}) = \gcd(\gcd(a_{1},a_{2}),a_{3},\ldots,a_{k})$$

Corollary 1.13¹

Suppose that $\gcd(a,b) = d$. Then an integer $c$ is of the form $ax + by$ for some $x,y \in {\mathbb{Z}}$ if and only of $c$ is a multiple of $d$. In particular. $d$ is the least integer of this form.

Pf

"$\Rightarrow$" $c = ax + by = d \cdot a' \cdot x + d \cdot b' \cdot y = d(a' x + b' y)$

"$\Leftarrow$" $c = kd\overset{\text{Bezout }}{=}k(au + by) = a(ku) + b(kv)$

Def 1.14

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

More generally, a set of integers $\left\{ a_{1},a_{2},\ldots,a_{k} \right\}$ are coprime if $\gcd(a_{1},a_{2},\ldots,a_{k}) = 1$.

They are called mutually coprime if $\gcd(a_{i},a_{j}) = 1$ for $i \neq j$. (mutually coprime $\Rightarrow$ coprime)

Corollary 1.15

$\gcd(a,b) = 1$ iff $ax + by = 1,\exists x,y \in {\mathbb{Z}}$.

Corollary 1.16

For coprime $a,b \in {\mathbb{Z}}$, we have that

If $a|c$ and $b|c$, then $ab|c$
If $a|bc$, then $a|c$.

Pf

Using corollary 1.15 $\begin{cases} ax + by = 1 \\ c = ae,c = bf \end{cases},acx + bcy = c \Rightarrow abfc + baey = c \Rightarrow ab|c$

$2$ is similar.

Def 1.17

If $a|c$ and $b|c$, we say that $c$ is a common multiple of $a$ and $b$. The set of all positive common multiples of $a \neq 0$ and $b \neq 0$ is clearly non-empty and bounded below. So there is a unique least common multiple of $a$ and $b$, denoted by $l.c.m(a,b).$

Theorem 1.18

Let $d = \gcd(a,b)$ and $m = l.c.m(a,b)$. Then $$d \cdot m = a \cdot b$$

Pf

Let $a = de$ and $b = df$, then $\frac{a \cdot b}{d} = def$ is common multiple of $a,b$. To show it is the least consider Bezout identity $d = au + bv$.Supp. $a|c,b|c$, $$\frac{c}{def}\frac{= (cd)}{ab}\frac{= \left( c(au + bv) \right)}{ab} = \frac{c}{a} \cdot u + \frac{c}{b} \cdot v \in {\mathbb{Z}}$$

HW: 1.17, 18, 19, 20, 21, 22, 25

Theorem 1.19 (Application to linear Diophantine equation)

Let $a,b$ and $c$ be integers with $a$ and $b$ not both $0$, let $d = \gcd(a,b)$. Then the equation $ax + by = c$ has an integer solution $x,y$ iff $c$ is a multiple of $d$. In this case, there are infinitely many solutions given by $x = x_{0} + \frac{bn}{d},y = y_{0} - \frac{an}{d},(n \in {\mathbb{Z}})$, where $x_{0},y_{0}$ is any particular solution.

Pf

The existence of solution is guaranteed by Corollary 1.13. These solutions are easy to verify. We remain to show they are the only solutions. If $(x,y)$ is any solution, then $\frac{a}{d}\left( x - x_{0} \right) = - \frac{b}{d}\left( y - y_{0} \right),\frac{b}{d}~|~\frac{a}{d}\left( x - x_{0} \right)$ but $\frac{b}{d},\frac{a}{d}$ are coprime, then by Corollary 1.16 ......

Steps to solve linear-Diophantine equation $ax + by = c$

use Euclid's algorithm to find $d = \gcd(a,b)$
If $d|c$, using the method in proof of Bezout's identity to find a particular solution $\left( x_{0},y_{0} \right)$. Otherwise, no solution.
Finally use Theorem 1.19 to find the general solution.

原文缺少1.12 ↩