你有任意张50块，我有任意张20块，咱俩一共能有多少钱？

作者: 理理你的数学 | 来源:发表于2020-07-09 08:46 被阅读0次

01 数论的几个表达以及相对应的性质

01 整除

若 $a=bq$ ，其中 $b$ 不等于零，我们就说b整除a，记作 $b|a$ ，此时我们把b叫做a的因数，因此他有如下性质：

1.如果 $b|a, c|b$ ,则 $c|a$
2.如果 $b|a$ ,则 $cb|ca$
3.如果 $c|a$ , $c|b$ ,则对任意的整数 $m,n$ 有
$c|ma+nb$
4.如果 $b|a$ 且, $a\neq0$ ,则 $|b|\le|a|$
5.如果 $cb|ca$ ,则 $b|a$
6.如果 $b|a,a\neq0$ ,则 $\frac{a}{b}|a$

02 最大公因数

设 $a_1,a_2,\ldots,a_n$ 是n个不全为零的整数。若整数d是他们之中每一个数的因数，那么d就叫做 $a_1,a_2,\ldots,a_n$ 的一个公因数。这时，他们的公因数只有有限个。整数 $a_1,a_2,\ldots,a_n$ 的公因数中最大的一个叫做最大公因数，记作 $(a_1,\ldots,a_n)$ ,若 $(a_1,\ldots,a_n)=1$ ,我们说 $a_1,a_2,\ldots,a_n$ 互素

02 啥是裴蜀定理？（数学版）

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，它形式上表示着一个判断整数系方程有无整数解的方法。 具体定理内容如下：

对于整数 $a,b,c$ ,二元一次方程 $ax+by=c$ 有整数解的充分必要条件是 $(a,b)|c$

证：首先证明充分性,若此方程有解，则可知 $(a,b)|a,(a,b)|b$ ,因此可知 $(a,b)|c$ 。
其次证明必要性,设 $d=(a,b)$ ，且设 $a=k_1d,b=k_2d,c=k_3d$ ，因此原方程可化为 $k_1x+k_2y=k_3$ ，又因为 $k_1x+k_2y=k_3\Leftrightarrow k_2y|k_1x-k_3\Leftrightarrow k_1x\equiv k_3(mod\ k_2)$ ，并且 $(k_1,k_2)=1$ ，因此当 $x$ 遍历 $k_2$ 的一个完全剩余系时， $k_1x$ 遍历 $k_2$ 的一个完全剩余系。证毕。

02* 啥是裴蜀定理？（人话版）

~~相信不少同学直接跳到了这个位置~~（裴蜀内心OS：证了半天都不看的嘛我哭了呜呜呜）。

假设你有任意张50块钱，我有任意张20块钱，咱们一共能有多少钱呢？

裴蜀定理一方面告诉我们只要是10的倍数的钱咱都能有，就比如说10块钱，我欠人家两张20你一张50帮我还咱一共就有10块钱。

另一方面告诉我们不是10的倍数咱们怎么都凑不出来，就像咱俩无论如何变不出来一张5块钱。

总结来说，裴蜀定理告诉我们只要未知项系数的最大公因数是常数项的因数 $(gcd(50,20)|10)$ ,这个方程就是有解的。

03 最大公因数的求法

对于正整数 $p,q$ 来说，如何求他们的最大公因数呢？

最直接的方法可能是从1一直试到 $p,q$ 之间最小的数，最大的能同时整除 $p,q$ 的数，就是 $p$ 和 $q$ 的最大公因数。

这种方法最大的弊端就是当 $p$ 和 $q$ 都很大的时候，计算量会很大，就比如说让你计算50块和20块的最大公因数很简单，但是让你计算银行账户里的数字和世界人口总数的最大公因数可能就会很麻烦。

（然鹅我就不一样了，世界人口有多少，这个最大公因数就是多少）

04 辗转相除法（数学版）

要证明辗转相除法的可行性，我们首先需要证明另一个较为简单的定理。

定理 1 设 $a,b,d$ 是任意三个不全为零的整数，且 $a-kb=d$
其中 $k$ 是整数，则 $(a,b)=(b,d)$

证:因为 $(a,b)|a, (a,b)|b$ ，所以有 $(a,b)|d$ ，因而 $(a,b)\le(b,d)$ .同法可证 $(b,d)\le(a,b)$ ，于是得到 $(a,b)=(b,d)$

现在我们证明辗转相除法，辗转相除法本质上就是把两个数 $a,b$ 做有限次形如 $a-kb=d$ （此处方便理解写法不正规）的带余除法。由此我们证明
定理2 若任给整数 $a>0,b>0$ ，进行有限次带余除法，则 $(a,b)=d_{n-1}$ （一大波推导来袭）
证： $a-k_1b=d_1,k_1b<a<(k_1+1)b$ $(a,b)=(b,d_1)$ $b-k_2d_1=d_2,k_2 d_1<b<(k_2+1)d_1$ $(b,d_1)=(d_1,d_2)$ $...$ $d_{n-3}-k_{n-1}d_{n-2}=d_{n-1}, k_{n-1}d_{n-2}<d_{n-3}<(k_{n-1}+1)d_{n-2}$ $d_{n-2}-k_{n}d_{n-1}=0$ $(d_{n-2},d_{n-1})=(d_{n-1},0)$
因此由等式的传递我们可以得知
$(d_{n-1},0)=(a,b)$
因此
$d_{n-1}=(a,b)$