Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/numbertheory1/

前言

笔者最近开始学习 OI 需要的数论……
本系列为学习笔记。

参考教材：《信息学奥赛之数学一本通》 (林厚雄)

整除

定义

整除，设 $a$ 为非零整数， $b$ 为整数， $q$ 为整数。
若有 $b = a * q$，则 $b$ 被 $a$ 整除， $a$ 整除 $b$，$a$ 是 $b$ 的因子。
记作 $a|b$。

性质

整除的一些性质。

1. 若 $a | b$，$b | c$，则 $a | c$。

证明：设 $b = a \times q_1$，$c = b \times q_2$，则 $c = a \times q_1 \times q_2$，即 $a | c$。

2. 若 $a | b$，$a | c$，则对于任意整数 $x$,$y$ 有 $a | (b \times x + c \times y)$。

证明：设 $b = a \times q_1$，$c = a \times q_2$，则 $b \times x + c \times y$ 等价于 $a \times (q_1 \times x \times q_2 \times y)$，则 $a | (b \times x + c \times y)$。

3. 设 $m \ne 0$，若有 $a | b$，则有 $(m \times a) | (m \times b)$。

证明：设 $b = a \times q$，则原式等价于 $(m \times a) | (m \times a \times q)$。

4. 设整数 $x,y$ 满足：$a \times x + b \times y = 1$ 且有 $a | n，b | n$，则 $(a \times b) | n$。

证明：
根据 性质3 由 $a | n，b | n$ 有 $(a \times b) | (a \times n)，(a \times b) | (b \times n)$。
根据 性质2 有 $(a \times b) |((a \times n) \times x + (b \times n) \times y)$。
化简得 $(a \times b) | n \times (a \times x + b \times y)$，其中 $a \times x + b \times y = 1$。
得原式 $(a \times b) | n$。

5. 若 $b = q \times d + c$，则 $d | b$ 的充要条件为 $d | c$。

证明：$b = q \times d + \frac{c}{d} \times d$，则 $\frac{c}{d}$ 为整数时 $d | b$，此时 $d | c$。

例题

由于书上的例题跟整除没有什么关系，并且后一道题涉及到更为困难的知识，笔者现在还未掌握，故照搬书上内容。

Church

StrongBox

由于笔者水平不足，在阅读本题题解时遇到许多困难，因此本题笔者亦想补充一点讲解……

二元一次不定方程一般形式为 $a \times x + b \times y = c$，其中 $a,b,c$ 为整数，$a \times b \ne 0$。

方程有整数解的充要条件为 $\gcd (a,b) | c$，这个定律叫做裴蜀定理。
笔者不会证，暂且背下来了。

设 $x_0,y_0$ 为该方程的一组整数解，则所有整数解可表示为：

$$x = x_0 + \frac{b}{\gcd(a,b)} \times t,y = y_0 – \frac{a}{\gcd(a,b)} \times t$$

证明如下：
原式等价于

$$\frac{a}{\gcd(a,b)} \times x + \frac{b}{\gcd(a,b)} \times y = \frac{c}{\gcd(a,b)}$$

$$\frac{a}{\gcd(a,b)} \times x = \frac{c}{\gcd(a,b)} – \frac{b}{\gcd(a,b)} \times y$$

将式子看做关于 $x$ 的方程，由于该式中自变量只有 $y_0$，且系数为 $\frac{b}{\gcd(a,b)}$。
因此设 $x = x_0 + \frac{b}{\gcd(a,b)} \times t$。

代入原式，有：

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{a}{\gcd(a,b)} \times \frac{b}{\gcd(a,b)} \times t = \frac{c}{\gcd(a,b)} – \frac{b}{\gcd(a,b)} \times y$$

移项整理得：

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{b}{\gcd(a,b)} \times (y + \frac{a}{\gcd(a,b)} \times t) = \frac{c}{\gcd(a,b)}$$

已知：

$$\frac{a}{\gcd(a,b)} \times x_0 + \frac{b}{\gcd(a,b)} \times y_0 = \frac{c}{\gcd(a,b)}$$

解得此时：

$$y = y_0 – \frac{a}{\gcd(a,b)} \times t$$

命题得证。
剩下的内容大概能看懂了，就不写了。