物理

循环提问帖

@一职的man（疯狂攒质子ing）

那是中国剩余定理（孙子定理），不是裴蜀定理

裴蜀定理表示如下：∀a，b∈N*，∃x，y∈Z，（a，b）=ax+by

特别地，当且仅当（a，b）=1时，∃x，y∈Z，ax+by=1

证明过程有点不太记得了，下周三我有时间的话就跟你解释一下

@ Black澄養&泽『小号』@一职的man（疯狂攒质子ing）

裴蜀定理还是比较有用的，下面展示如何利用裴蜀定理证明斐波那契数列中的GCD定理：

记斐波纳契数列的第n项为F（n），求证：F（（m，n））=（F（m），F（n））

证明：❲引理1❳F（m+n+1）=F（m）F（n）+F（m+1）F（n+1）。

❲引理的证明❳记等式右侧为G（m，n）。

显然，当m=1时，左侧=右侧。

当m≥2时，G（m，n）=F（m）F（n）+F（m-1）F（n+1）+F（m）F（n+1）=F（m）F（n+2）+F（m-1）F（n+1）=G（m-1，n+1）。

重复有限次此操作，可以得到G（m，n）=G（1，m+n-1）=F（m+n+1）。证毕。

❲引理2❳若m|n，则F（m）|F（n）。

❲引理的证明❳设n=qm，q∈N*。

当q=1时，显然成立。

当结论对q=k成立时，由引理1，F（（k+1）m）=F（km-1）F（m）+F（km）F（m+1）

由F（m）|F（km），知F（m）|F（（k+1）m），即结论对于q=k+1成立。

由第一数学归纳法，证毕。（怕字数超了所以剩下步骤放下一条回复）

❲引理3❳（F（k），F（k+1））=1。

❲引理的证明❳当k=1时，显然成立。

当k≥2时，（F（k），F（k+1））=（F（k），F（k+1）-F（k））=（F（k），F（k-1）），

重复执行有限次操作即可得（F（k），F（k+1））=（F（1），F（2））=1。证毕。

❲引理4❳（F（m），F（qm+n））=（F（m），F（n）），q∈Z。

❲引理的证明❳当q=0时，显然成立。下面只讨论q≠0的情形。

当n=1时，显然成立。

当n≥2时，由引理1，F（m+n）=F（m）F（n-1）+F（m+1）F（n），

由引理3，（F（m），F（m+1））=1，（F（m），F（m+n））=（F（m），F（n））

重复执行有限次操作，可得（F（m），F（qm+n））=（F（m），F（n）），Q∈N*。

当q<0时，（F（m），F（n））=（F（m），F（n+qm+（-q）m））=（F（m），F（qm+n））。

综上，对于∀q∈Z，证毕。

下面回到对原命题的证明。

由引理3，F（（a，b））|F（a），F（（a，b））|F（b），故F（（a，b））|（F（a），F（b））。①

由裴蜀定理，可设（a，b）=as+bt，s∈N*，t∈Z。

而由引理3，引理4，（F（a），F（b））|（F（as），F（b））=（F（as+bt），F（b））|F（as+bt）=F（（a，b））。②

综合①②可得F（（a，b））=（F（a），F（b））。证毕。

谢谢各位的回答~

Source: OI Wiki

来看看这个证明