带余数除法

1. 带余数除法的概述

对于正整数$a≠0, b$, 也 $\color{Blue}{存在唯一}$ 的一组整数$q, r$, 满足: $b=aq+r$, 其中$0 \le r < |a|$

2. 带余数除法的证明

(1). 存在性

• 若$a|b$, 由整除的定义, $\exists k \in Z$, 使$b = ak$, 取$q=k, r=0$即可
• 若$a不能整除b$, $S = \lbrace b-aq | q \in Z \rbrace$, 调整$q$取值, $S$中必有正整数
  记其中最小的一个为$r$, 下证: $0 < r < |a|$, 否则, $r >= |a|$
  1. 若$r=|a|$: $b-aq = |a|$ => $a|b$, 矛盾!
  2. 若$r>|a|$: $r-|a| = b-aq-|a| = b-a(q \pm 1) \in S$
  但是$r-|a|<r$且$r-|a| \in N^+$, 与$r$为$S$中最小正整数矛盾!

(2). 唯一性: 使用同一法

假设存在$(q, r), (q’, r’)$均满足条件
则$aq+r = aq’+r’$, 不妨设$r \le r’$
1. 若$r = r’$, 则$q = q’$, 自然满足
2. 若$r < r’$, 则$r-r’ = a(q’-q) > 0$ => $a|(r’-r)>0$ => $r-r’ >= |a|$
但是$0 \le r’ < |a|$, $0 \le r < |a|$ => $r’ - r < |a|$, 矛盾!

欧几里得算法

1. 欧几里得算法的概述

(1). 引理：设$a>b, b≠0, a=bq+r (0 \le r < b)$, 则有$(a, b) = (b, r)$
(2). 由辗转相除法求最大公约数

2. 欧几里得算法的证明

(1). 引理的证明
$(a, b) = (a-b, b) = (a-2b, b) = … = (a-qb, b) = (r, b) = (b, r)$

(2). 回到原题
设$a=bq+r (0 \le r < b)$
$b=rq_1+r_1 (0 \le r_1 < r)$
$r=r_1q_2+r_2 (0 \le r_2 < r_1)$
…
$r_{n-2}=r_{n-1}q_n+r_n (0 \le r_n < r_{n-1})$
$r_{n-1}=r_nq_{n+1}+r_{n+1} (0 \le r_{n+1} < r_n)$

显然$a>b>r>r_1>r_2>…>r_{n+1} \ge 0$
由整数的离散性 => 在有限步内, 必有$r_{n+1}=0$
即$r_{n-1}=r_nq_{n+1}$
$\therefore (r_{n-1}, r_n) = r_n$
由引理: $(a, b) = (b, r) = (r, r_1) = (r_1, r_2) = … = (r_{n-1}, r_n) = r_n$

综上所述, 欧几里得算法获证.

Bezout定理

1. Bezout定理的概述

设$d=(a, b)$, 则$\exists x, y \in Z$, 使$xa + yb = d$

2. Bezout定理的证明

(1). 证明

不妨设$a \geq b > 0$
设$a=bq+r (0 \le r < b)$
$b=rq_1+r_1 (0 \le r_1 < r)$
$r=r_1q_2+r_2 (0 \le r_2 < r_1)$
…
$r_{n-2}=r_{n-1}q_n+r_n (0 \le r_n < r_{n-1})$
$r_{n-1}=r_nq_{n+1}+r_{n+1} (0 \le r_{n+1} < r_n)$

显然$a>b>r>r_1>r_2>…>r_{n+1} \ge 0$
由整数的离散型 => 在有限步内, 必有$r_{n+1}=0$
即$r_{n-1}=r_nq_{n+1}$

$(a, b) = r_n = r_{n-2} - r_{n-1}q_n$
$ = r_{n-2} - (r_{n-3} - r_{n-2}q_{n-1})q_n = (1 + q_{n-1}q_n)r_{n-2} - q_nr_{n-3}$
…
$ = xa + yb$

Bezout定理的逆命题: 若$d \in N^+, d|a, d|b, 且\exists x, y \in Z, 使xa + yb = d$, 则有$d = (a, b)$

(2). 逆命题证明

引理: $(a, b)$是形如$xa + yb, (x, y \in Z, xa+yb \in N_+)$中的最小值
引理的证明: 记集合$S = \lbrace xa + yb | x, y \in Z, xa+yb \in N_+ \rbrace$, 显然$S$中有最小值, 记为$l_0 = x_0a + y_0b$
$\forall l \in S, l = xa + yb$, 先证$l_0 | l$
设$l = l_0q + r (0 \le r < l_0)$
则$r = l - l_0q = (xa + yb) - q(x_0a + y_0b) = (x-x_0q)a + (y-y_0q)b = x’a + y’b$
若$r>0$ => $r \in S$ => $r \geq l_0$, 矛盾!
=> $r=0$ => $l_0|l$

下证$l_0 = (a, b)$
1° $(a, b)|a, (a, b)|b$ => $(a, b)|(x_0a + y_0b) = l_0$
2° $a \in S, b \in S$ => $l_0|a, l_0|b$ => $l_0|(a, b)$
1°, 2°综合 => $l_0 = (a, b)$

设满足条件的最小的数为$d$
回到原题, 由引理, 形如$xa+yb (x, y \in Z)$的数一定为$(a, b)$的倍数 => $(a, b)|d$
又$\because d|a, d|b$
两式综合 => $d = (a, b)$

威尔逊定理

1. 威尔逊定理的概述

$p$是一个大于1的整数, 则$p$为素数的充要条件为$(p-1)! \equiv -1 (mod p)$

2. 威尔逊定理的证明

(1). 必要性证明

若$p=2$, 成立
当$p$为奇数时, $\forall a \in {\lbrace 2, 3, … , p-2 \rbrace}$
$\because (a, p) = 1$ $\therefore \lbrace a, 2a, 3a , … , (p-1)a \rbrace 构成mod \, p 的完全剩余系$
=> $唯一存在 b \in \lbrace 1, 2, 3, …, p-1 \rbrace, 使ab \equiv 1 (mod \, p)$
$\because a \neq 1, a \neq p-1$ $\therefore b \neq 1, b \neq p-1$
若$a=b$, 则有$a^2 \equiv 1 (mod \, p)$ => $a=1或p-1$, 矛盾!
可将$2, 3, …, p-2$两两配对得 $2 \times 3 \times … \times (p-2) \equiv 1 (mod \, p)$
$\therefore (p-1)! \equiv -1 (mod \, p)$

(2). 充分性证明

采用反证法
若$p$为合数, $设p_0为p的素因数 (1 < p_0 < p)$
于是$(p-1)! \equiv -1 (mod \, p)$ => $(p-1)! \equiv -1 (mod \, p_0)$
但是$p_0|(p-1)!$ => $(p-1)! \equiv 0 (mod \, p_0)$
矛盾!

综上所述, 威尔逊定理得证.

费马小定理

(1). 费马小定理的概述

如果$p$为质数, $a \in Z$, $(a, p) = 1$, 则有$a^{p-1} \equiv 1 (mod \, p)$

(2). 费马小定理的证明

$\because (a, p) = 1$ $\therefore \lbrace a, 2a, 3a, …, (p-1)a \rbrace 构成mod \, p的完全剩余系$
$\therefore a \times 2a \times 3a \times … \times (p-1)a \equiv (p-1)! (mod \, p)$
=> $a^{p-1} \times (p-1)! \equiv (p-1)! (mod \, p)$
=> $a^{p-1} \equiv 1 (mod \, p)$

综上所述, 费马小定理得证.
注意: 费马小定理没有逆定理!