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

裴蜀定理（或贝祖定理，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个数也符合。

令前n个数的最大公约数为：q 注意：n+1个数互质，前n个数不一定互质。

根据菲蜀定理：

将式一左右都乘以y1的

联合式二式三得：

解为：

得证

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

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

扩展阅读

视频课程

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

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。