严格证明扩展欧几里得算法的正确性

川长思鸟来 2021-11-10 07:34 265阅读 0赞

### 严格证明扩展欧几里得算法的正确性 ###

引理一：\\(m\\mid x\_i, i\\in\[1, k\]\\)，则\\(m\\mid a\_1x\_1+\\dots + a\_kx\_k, a\_i\\in Z\\)

证明：设\\(mb\_i=x\_i\\)，则\\(a\_1x\_1+\\dots+a\_kx\_k=a\_1mb\_1+\\dots+a\_kmb\_k=m(a\_1b\_1+\\dots+a\_kb\_k),m \\mid m(a\_1b\_1+\\dots+a\_kb\_k)\\)

引理二：设正整数\\(m \\mid (a\_1,\\dots,a\_k)\\)，则\\(m(\\frac\{a\_1\}\{m\},\\dots,\\frac\{a\_k\}\{m\})=(a\_1,\\dots,a\_k)\\)。

证明：设\\(D=(a\_1,\\dots,a\_k)\\)，由\\(m \\mid D\\),\\(D \\mid a\_j\\)，得\\(m \\mid a\_j\\)（假定了整除满足同乘同除一个数依然成立），\\(\\frac\{D\}\{m\} \\mid \\frac\{a\_j\}\{m\}\\)，因此\\(\\frac\{D\}\{m\}\\)是\\(\\frac\{a\_i\}\{m\}\\)的公约数，有\\(\\frac\{D\}\{m\}\\le(\\frac\{a\_1\}\{m\},\\dots,\\frac\{a\_k\}\{m\})\\)

另一方面，若\\(d\\mid \\frac\{a\_j\}\{m\},1\\le j\\le k\\)，则\\(md \\mid a\_j,j=1,\\dots,k\\)。由于\\(D\\)是\\(a\_j\\)的最大公约数，所以\\(md\\le D\\)，\\(\\frac\{D\}\{m\} \\ge d\\)

取\\(d=(\\frac\{a\_1\}\{m\},\\dots,\\frac\{a\_k\}\{m\})\\)，则可得\\(\\frac\{D\}\{m\}=(\\frac\{a\_1\}\{m\},\\dots,\\frac\{a\_k\}\{m\})\\)

两边同乘\\(m\\)，可得\\(m(\\frac\{a\_1\}\{m\},\\dots,\\frac\{a\_k\}\{m\})=D=(a\_1,\\dots,a\_k)\\)

将\\(m=(a\_1,\\dots,a\_k)\\)代入上式，即得 \\((\\frac\{a\_1\}\{(a\_1,\\dots,a\_k)\},\\dots,\\frac\{a\_k\}\{(a\_1,\\dots,a\_k)\})=1\\)

--------------------

定理一： \\((x\_1, \\dots , x\_k)=min\\\{s=a\_1x\_1+\\dots+a\_kx\_k,s\\in A, s>0, a\_i\\in Z\\\}\\)

证明：设\\(s\_\{min\}=a\_1'x\_1+\\dots +a\_k'x\_k\\)。对于任意\\(d\\mid x\_i\\)，由引理可得\\(d\\mid s\_\{min\}\\)，因此\\((x\_1, \\dots, x\_k)\\mid s\_\{min\}\\)，\\((x\_1, \\dots, x\_k)\\le s\_\{min\}\\)

又因为\\(x\_i\\% s\_\{min\}\\in \[0, s\_\{min\})\\)【不严格】，且\\(s\_\{min\}\\)是\\(A\\)中的最小正元素，所以\\(x\_i\\% s\_\{min\}=0\\)，即\\(s\_\{min\} \\mid x\_i\\)，

所以\\(s\_\{min\}\\)是\\(x\_i\\)的公约数，小于等于最大公约数。即\\(s\_\{min\}\\le (x\_1,\\dots,x\_k)\\)

综上，可得\\((x\_1,\\dots, x\_k)=s\_\{min\}\\)

推论一：一定存在一组整数\\(a\_1', \\dots, a\_k'\\)，使得\\((x\_1, \\dots, x\_k)=a\_1'x\_1+\\dots+a\_k'x\_k\\)。这是因为\\((x\_1, \\dots, x\_k)=s\\in A\\)，而\\(A\\)中的元素表示为\\(a\_1x\_1+\\dots +a\_ks\_k\\)。因此一定存在一组整数表示\\((x\_1,\\dots,x\_k)=s\\)

推论二：\\((x\_1,\\dots,x\_k)\\mid a\_1x\_1+\\dots+a\_kx\_k,a\_i\\in Z\\)。这是因为\\((x\_1,\\dots,x\_k)\\mid x\_i\\)，根据引理推论二得证。

--------------------

【注】本节的\\(a\\)和\\(x\\)与前两节的位置是互换了的。

设整数\\(k \\ge 2\\)，\\(a\_1,\\dots,a\_k\\)是整数且不等于零，\\(c\\)是整数，\\(x\_1,\\dots,x\_k\\)是整数变数，方程\\(a\_1x\_1+\\dots+a\_kx\_k=c\\)称为k元一次不定方程，\\(a\_1,\\dots, a\_k\\)称为它的系数。

定理二 k元一次不定方程有解的充要条件是\\((a\_1,\\dots,a\_k)\\mid c\\)

证明：首先证明充分性。根据推论一，必定存在一组整数\\(x\_1',\\dots,x\_k'\\)，使得\\(a\_1x\_1'+\\dots+a\_kx\_k'=(a\_1,\\dots,a\_k)\\)。新方程的解之一就是\\(x\_i=x\_i'\\frac\{c\}\{(a\_1,\\dots,a\_k)\}\\)

然后证明必要性。根据推论二，\\((a\_1,\\dots,a\_k)\\mid a\_1x\_1+\\dots+a\_kx\_k=c\\)，必要性直接得证。

--------------------

定理三 设二元一次不定方程\\(a\_1x\_1+a\_2x\_2=c\\)有解，\\(x\_\{1,0\},x\_\{2,0\}\\)是它的一组解，那么它的所有解为

\\\[\\left \\\{ \\begin\{aligned\} x\_1=x\_\{1,0\}+\\frac\{a\_2\}\{(a\_1,a\_2)\}t, \\\\ x\_2=x\_\{2,0\}-\\frac\{a\_1\}\{(a\_1,a\_2)\}t, \\end\{aligned\} \\right. t=0,\\pm1,\\pm2,\\dots \\\]

证明：容易验证对于所有给出的解\\(x\_1,x\_2\\)，对于所有整数\\(t\\)都满足不定方程4。

反过来，设\\(x\_1,x\_2\\)是方程的一组解，我们有\\(a\_1x\_1+a\_2x\_2=c=a\_1x\_\{1,0\}+a\_2x\_\{2,0\}\\)，进而有\\(a\_1(x\_1-x\_\{1,0\})=-a\_2(x\_2-x\_\{2,0\})\\)，\\(\\frac\{a\_1\}\{(a\_1,a\_2)\}(x\_1-x\_\{1,0\})=-\\frac\{a\_2\}\{(a\_1,a\_2)\}(x\_2-x\_\{2,0\})\\)

根据引理二，\\((\\frac\{a\_1\}\{(a\_1,a\_2)\},\\frac\{a\_2\}\{(a\_1,a\_2)\})=1\\)，而上式可以转化为\\(\\frac\{a\_2\}\{(a\_1,a\_2)\}\\mid \\frac\{a\_1\}\{(a\_1,a\_2)\}(x\_1-x\_\{1,0\})\\)。根据定理\\((m,a)=1,m\\mid ab\\Rightarrow m \\mid b\\)（可用算数基本定理证明【不严格】），\\(\\frac\{a\_2\}\{(a\_1,a\_2)\} \\mid (x\_1-x\_\{1,0\})\\)。

因此，\\(x\_1=x\_\{1,0\}+\\frac\{a\_2\}\{(a\_1,a\_2)\}t\\)，\\(x\_2=x\_\{2,0\}-\\frac\{a\_1\}\{(a\_1,a\_2)\}t\\)，这就证明了满足二元一次不定方程的解一定满足上述解的前面的通式。

--------------------

求解二元一次不定方程需要用到扩展欧几里得算法。

我们现在需要求出方程\\(ax+by=z\\)的解\\((x,y)\\)。根据定理二，方程\\(ax+by=z\\)有解等价于\\((a,b) \\mid z\\)，因此我们只要先求出方程\\(ax+by=(a, b)\\)的解，再将解的值乘上\\(\\frac\{z\}\{(a,b)\}\\)，就求出了原方程的一组解。

那么，如何求解\\(ax+by=(a,b)\\)？考虑欧几里得算法\\((a,b)=(b, a\\%b)\\)，设\\(bx'+(a\\%b)y'=(b,a\\%b)=(a,b)=ax+by\\)，

则\\(bx'+(a\\%b)y'=bx'+(a-b\\lfloor\\frac\{a\}\{b\}\\rfloor)y'=ay'+b(x'-\\lfloor \\frac\{a\}\{b\}\\rfloor)\\)

可以发现\\(x=y',y=x'-\\lfloor \\frac\{a\}\{b\}\\rfloor\\)就是方程\\(ax+by=(a,b)\\)的一组解。

不断地列出\\(ax+by=ay'+b(x'-\\lfloor\\frac\{a\}\{b\}\\rfloor)\\)，代入\\(x=y',y=x'-\\lfloor \\frac\{a\}\{b\}\\rfloor\\)求解，最后就能求出\\(ax+by=(a,b)\\)的某一组解\\((x\_0,y\_0)\\)。在这之后再利用定理三求出通解：

\\\[\\left \\\{ \\begin\{aligned\} x\_1=x\_\{1,0\}+\\frac\{a\_2\}\{(a\_1,a\_2)\}t, \\\\ x\_2=x\_\{2,0\}-\\frac\{a\_1\}\{(a\_1,a\_2)\}t, \\end\{aligned\} \\right. t=0,\\pm1,\\pm2,\\dots \\\]

就完成了解二元一次不定方程的过程。

打【不严格】的部分是为了可读性省略的部分。如果展开会引入一些过长的概念。

参考资料：潘承洞《初等数论》

转载于:https://www.cnblogs.com/MyNameIsPc/p/11215224.html