前置芝士
小学数学
写在前面
Q：啥叫飞鼠定理啊？
A：是斐蜀定理（捂脸
在数论中，裴蜀定理是一个关于最大公约数(或最大公约式)的定理--360百科
Q：说的啥啊？
1、对于正整数 (a, b) 存在整数 (x, y) 使得 (gcd(a, b) = ax +by)
2、整数 (a, b) 互质的充要条件是存在整数 (x, y) 使得 (ax + by = 1)
简单来说，我们设 (d = gcd(a, b))，那么对于方程 (ax + by = d) ，一定存在一组整数解。并且对于方程 (ax + by = z)，如果满足 (d mid z)，那么方程一定有整数解，否则无整数解。
（注：这里 (d mid z) 的意思是 (z mod d = 0)）
对于第一个推论的证明：
已知非零整数 (a, b)
记集合 (S = { ax + by mid x, y in mathbb{Z} 且 ax + by > 0})
记整数 (d = ax_0 + by_0)
我们只要证明 (d = gcd(a, b)) 就证明了斐蜀定理，
设 (a = dq + r), 其中 (q, r) 是 (a) 模 (d) 的商和余数，则有
因为我们用到的都是整数，所以不难看出 (1 - x_0q) 和 (y_0q) 也都是整数
所以 (r in S cup { 0 }) ，（为啥要并上 (0) 尼？因为 (r) 表示余数，余数可以为 (0) 嘛）
我们又知道 (0 leqslant r < d)，而 (d) 又是 (S) 中的最小元素，所以 (r = 0)
这意味着 (d mid a)， 同理 (d mid b)，又因为 (gcd(a, b) mid d) ，所以 (d = gcd(a, b))
证毕。
另外的，由集合 (S) 可以看出 (x, y) 的解不是唯一的，有无穷组系数 ((x, y)) 都能满足 (gcd(a, b) = ax + by).并且，如果 ((x, y)) 是一组系数，那么所有系数可以表示为
对于第二个推论的证明：
再抄一遍
整数 (a, b) 互质的充要条件是存在整数 (x, y) 使得 (ax + by = 1)
利用反证法，
设 (a, b) 不互质，那么 (a, b) 可以表示成 (a = q imes gcd(a, b), b = p imes gcd(a, b))，带入上面的式子，得到：
两边同时除以 (gcd(a,b)) 得到：
显然，如果 (a, b) 不互质，那么式子右边已经变成了一个小数，那么方程一定不存在整数解。所以只有当 (a, b) 互质时，该方程才有整数解.
证毕。
顺便我们可以得到：
对于方程 (ax + by = z), 只有满足 (gcd(a, b) mid z) ，方程才有整数解
证明：
设 (d = gcd(a, b), z = d imes q)
对于方程 (ax + by = d) , 我们设有一组解为 (x_0, y_0), 那么就有：
两边同时乘 (q) 得：
(ecause z = d imes q)
( herefore) 方程 (ax + by = z) ，一定存在一组整数解为 (x = x_0 imes q, y = y_0 imes q) , 证毕
按照同样的思路可以扩展到 (n) 元不定方程上
对于不定方程 (a_1x_1 + a_2x_2 + a_3x_3 + … +a_nx_n = 1)，只有所有系数的 (gcd) 为 (1) 时，方程才有整数解。
顺便得到
所有系数 (a_1, a_2, a_3 ,···,a_n) 的最大公约数为 (1) 的充要条件是：满足不定方程 (a_1x_1 + a_2x_2 + a_3x_3 + … +a_nx_n = 1)