【数学归纳法反证法】菲蜀定理

本文主要是介绍【数学归纳法反证法】菲蜀定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

定理 $\iff$ 推论

假定a $\neq$ 0 b $\neq$ 0 $\rightarrow$ 它们的公约数不为0。
令a1和b1的最大公约数是q,a1=qa,b1=ab。
则a1x+b1y=d ，等式左右同时除以d，变成ax+by=1

下面来证明a > 0 ,b > 0一定有整数解

初始条件：a > 0 b > 0，a和b互质。
如果a = b，且互质 $\rightarrow$ a=b =1 ，则至少有解为 x=-1,y=2。
如果a $\neq$ b
如果 a < b，a和b互换，x和y互换。
令 c =a -b
ax + by = (b+c)x + by = b(x+y)+cx
将 b改名为a ,x+y改名为x，c改名为b ,x改名为y。则变成了:ax+by
且max(a,b)变小。
由于 c =a-b，且 a > b，故不断持续此过程，一定将a，b都变成1。故一定有解。

a > b > 0互质，则(a-b)和b互质

反证法：假定(a-b)不互质，其有公约数e>1。则 a-b = f1e ,b = f2e $\rightarrow$ a = (f1+f2)e $\rightarrow$ a和b有公约数 e，与假设矛盾。

a或b为负数

令abs(a)x+abs(b)y=1的一个解为(x1,y1)
如果 a < 0 b < 0 ，则解为(-x1,-y1)
如果 a < 0 b > 0，则解为(-x1,y1)
如果 a> 0 b < 0 ，则解为(x1,-y1)

多个数也符合菲蜀定理

下面来证明：如果n个数符合菲蜀定理，则n+1个数也符合。
$\cdots a_n,a_{n+1}$
令前n个数的最大公约数为：q 注意：n+1个数互质，前n个数不一定互质。
根据菲蜀定理：
$\cdots a_nx_n = q \quad 式一 \\ qy1 +a_{n+1}x_{n+1} =1 \quad 式二$
将式一左右都乘以y1的
$\cdots a_nx_ny1 = qy1 \Large \quad 式三$
联合式二式三得：
$\cdots a_nx_ny1 +a_{n+1}x_{n+1} = 1$
解为：
$\cdots x_ny1,x_{n+1}$ 得证

如果有整数解，则一定互值

反证法：假定有公约数q，q>1。则 ax+by $\cdots$ 之和一定是q的倍数，不会为1。

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛