初等数论/同馀

数论 > 初等数论 > 初等数论/同馀

同馀的定义在第一章已经说明了，即a $\equiv b (\mod m)$ 当m|a-b时，数论中很多定理和证明用一般带馀数除法的表示法也能做得出来，但是这些定理和证明若用同馀式表示往往更加地简便明了

同馀的性质

由同馀的定义和基本的算术运算法则，可推出：

若 $a \equiv b (\mod m)$ 且 $c \equiv d (\mod m)$ ，则有 $a \pm c \equiv b \pm d (\mod m)$ ，和 $a c \equiv b d (\mod m)$ ，但是反过来时不一定成立
若 $n a \equiv n b (\mod m)$ 且 $n | m$ ，则 $a \equiv b (\mod m / | n |)$
若 $(a, m) = 1$ 则存在整数C，使得 $C a = 1 (\mod m)$

同馀类与剩馀系

同馀类：对于模m的元素，将所有对模m两两同馀的数取出，所形成的集合称之为模m的同馀类，即若 $s \equiv r (\mod m)$ ，则r和s属于模m的同一个同馀类

剩馀系：对于模m的不同同馀类的元素，各取一个出来所形成的集合称之为模m的剩馀系，即模m的一个剩馀系中的所有元素两两不同馀

多项式同馀

经典同馀恒等式

欧拉函数

$ϕ (n)$ 函数(又称欧拉函数)是指小于等于n的自然数中与n互质的数的数目。例子： $ϕ (6)$ =2，因为在1,2,3,4,5,6中只有1,5是和6互质

欧拉函数的特性

若正整数n个标准分解式为 $n = p_{1}^{q_{1}} p_{2}^{q_{2}} ...... p_{k}^{q_{k}}$ ，则 $ϕ (n)$ 函数的值为：

$ϕ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) ...... (1 - \frac{1}{p_{k}})$

用逻辑集合的概念、排列组合及算术基本定理可验证此式的成立

如果(m,n)=1，： $ϕ (m)$ $ϕ (n)$ = $ϕ (m n)$ ，即 $ϕ (n)$ 函数为一积性函数

例子： $ϕ (36)$ = $ϕ (4)$ $ϕ (9)$ =12

除了 $ϕ (1)$ = $ϕ (2) = 1$ 外，对其他的 $ϕ (n)$ ，都有 $2 | ϕ (n)$

另一方面，若设m的一个简化剩馀系为 ${r_{1}, r_{2}, \dots, r_{ϕ (m)}}$ ，其中对于任何 $r_{j}$ 有 $(r_{j}, m) = 1$ ，而这个简化剩馀系的元素有k个，则 $ϕ (m) = k$

费马小定理

费马小定理：对于任意正整数a，及任意质数p，有以下关系式：

$a^{p} \equiv a (\mod p)$

其中对任意使(a,p)=1的a，有以下关系式：

$a^{p - 1} \equiv 1 (\mod p)$

欧拉定理

欧拉定理：对于任意的 $(a, m) = 1$ ，存在有以下的关系式：

$a^{ϕ (m)} \equiv 1 (\mod m)$

并且 $a, a^{2}, a^{3}, \dots, a^{ϕ (m)}$ 中的数两两不同馀

利用简化剩馀系证明欧拉定理

设

{r_{1}, r_{2}, \dots, r_{ϕ (m)}}

为模m的简化剩馀系

由于 $(a, m) = 1$ ， ${a r_{1}, a r_{2}, \dots, a r_{ϕ (m)}}$ 也是模m的简化剩馀系
$(a r_{1}) (a r_{2}) \dots (a r_{ϕ (m)}) \equiv r_{1} r_{2} \dots r_{ϕ (m)} (\mod m)$
$a^{ϕ (m)} (r_{1} r_{2} \dots r_{ϕ (m)}) \equiv r_{1} r_{2} \dots r_{ϕ (m)} (\mod m)$
又 $(r_{1} r_{2} \dots r_{ϕ (m)}, m) = 1$ ，得 $a^{ϕ (m)} \equiv 1 (\mod m)$

卡迈克尔函数

卡迈克尔函数 $λ (n)$ 满足 $a^{λ (n)} \equiv 1 (\mod n)$ ，其中a与n互质。

当n为2、4、奇质数的指数、奇质数的指数的两倍时为欧拉函数，当n为2,4以外的2的指数时为它的一半。 $λ (n) = {\begin{matrix} φ (n) & n = 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 19, 22, 23, 25, 26, 27, 29 \dots \\ \frac{1}{2} φ (n) & n = 8, 16, 32, 64, 128, 256 \dots \end{matrix}$

欧拉函数有 $φ (p^{k}) = p^{k - 1} (p - 1)$

由算术基本定理，正整数n可写为质数的积 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{ω (n)}^{a_{ω (n)}}$

对于所有n， $λ (n)$ 是它们的最小公倍数：

$λ (n) = lcm [λ (p_{1}^{a_{1}}), λ (p_{2}^{a_{2}}), \dots, λ (p_{ω (n)}^{a_{ω (n)}})]$

证明当a与n互质时，

a^{λ (n)} \equiv 1 (\mod n)

由费马小定理得

a^{p - 1} = 1 + h p

$a^{p^{k - 1} (p - 1)} = 1 + h p^{k}$

$a^{p^{k} (p - 1)} = (1 + h p^{k})^{p} = 1 + h^{p} p^{k + 1} + \dots = 1 + h_{0} p^{k + 1}$

由数学归纳法得 $a^{p^{k - 1} (p - 1)} \equiv 1 (\mod p^{k})$ 成立，这是一般情况。

$a = 1 + 2 h$

$a^{2} = 1 + 4 h (h + 1) = 1 + 8 C_{h + 1}^{2}$

$a^{2^{k - 2}} = 1 + 2^{k} h$

$a^{2^{k - 1}} = (1 + 2^{k} h)^{2} = 1 + 2^{k + 1} (h + 2^{k - 1} h^{2})$

由数学归纳法得当 $k \geq 3$ 时， $a^{2^{k - 2}} \equiv 1 (\mod 2^{k})$ 成立。

威尔逊定理

威尔逊定理：对于所有质数 $p$ ，都有 $p | (p - 1)! + 1$ ，且若此式成立，p为质数

证明威尔逊定理

如果p不是质数，它的正因数必然包含在 $1, 2, 3, 4, \dots, p - 1$ 中，因此 $((p - 1)!, p) \neq 1$
$(p - 1)! \equiv - 1 (\mod p) \Rightarrow \exists k \in ℤ, s . t . (p - 1)! + p k = - 1$ ，与 $((p - 1)!, p) \neq 1$ 矛盾。
所以 $(p - 1)! \equiv - 1 (\mod p)$ 成立时p一定是质数。

若p是质数， $A = {1, 2, 3, \dots, p - 1}$ 是模p的剩馀系
$\forall i \in A, \exists j \in A, s . t . i j \equiv 1 (\mod p)$
当 $i = j$ 时， $i^{2} \equiv 1 (\mod p) \Rightarrow i \equiv \pm 1 (\mod p)$
其馀 ${2, 3, \dots, p - 2}$ 两两配对
$(p - 1)! \equiv 1 \times (p - 1) \equiv - 1 (\mod p)$

费马小定理馀式推广

$p | x^{p} - x \Rightarrow p^{k} | (x^{p} - x)^{k}$

除式： $x^{p k} \equiv \sum_{i = 1}^{k} (- 1)^{i - 1} (\binom{k}{i}) x^{p k - (p - 1) i} (\mod p^{k})$

馀式： $x^{p k + (p - 1) n} \equiv \sum_{i = 1}^{k} (- 1)^{i - 1} (\binom{n + i - 1}{i - 1}) (\binom{n + k}{k - i}) x^{p k - (p - 1) i} (\mod p^{k})$

n=0时为除式，用数学归纳法证明余式。

阶乘幂

$(x)_{k} \equiv x (x - 1) (x - 2) \dots (x - k + 1) \equiv 0 (\mod k!)$

由组合数为整数可得。

习题

第一部份─基础题

第二部份─进阶题