循环提问帖

物理
循环提问帖

用户头像
Black澄養&泽『小号』 更新于2024-6-1 05:02:56

想问一下裴蜀定理的证明

收起
5
1
共10条回复
时间正序
用户头像
一职的man
1月前
三人同行七十稀,五树梅花二十一。七子团圆正半月,除百零五便得知
用户头像
一职的man
1月前
白话就是给定一个数,分别除以3,5,7.将余数分别乘以70,21,15。最后将乘积相加起来,得最终结果与初始给定的数一定相差105的倍数
4条评论
用户头像
浙里很安竞
1月前

怎么证明?

用户头像
水(数学)是剧毒的
1月前

0呢?0与0只差0啊jj-huaji

用户头像
用户头像
Grievous. 回复 水(数学)是剧毒的
1月前

105*0=0

用户头像
水(数学)是剧毒的 回复 Grievous.
1月前

漏了个“倍数”zx-caizixing2@2x

用户头像
一职的man
1月前

@浙里很安竞一般来说没必要掌握这玩意的吧(嗯?)

1条评论
用户头像
一职的man
1月前

指怎么证明

@一职的man(疯狂攒质子ing)

那是中国剩余定理(孙子定理),不是裴蜀定理

裴蜀定理表示如下:∀a,b∈N*,∃x,y∈Z,(a,b)=ax+by

特别地,当且仅当(a,b)=1时,∃x,y∈Z,ax+by=1

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

1条评论
用户头像
一职的man
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))。证毕。


用户头像
Starry
1月前

没时间就先不写了可以辗转相除



用户头像
Black澄養&泽『小号』
1月前

谢谢各位的回答~

2条评论
用户头像
11月20日0点北京雨中的黄智英
1月前

没事啦(其实真实原因是我周三才上过)

用户头像
11月20日0点北京雨中的黄智英
1月前

我们老师课上还特别强调裴蜀定理的重要性,举例就是上面的所谓GCD定理(如果我没记错应该是叫这个名字)的证明

用户头像
盼星盼不到星>∆
1月前
罗老讲哩鸭
1条评论
用户头像
盼星盼不到星>∆
1月前

数论第三节

用户头像
Konjac0629
1月前

Screenshot_20240604-181651.png

Source: OI Wiki

来看看这个证明

Screenshot_20240604-181843.png

7条评论
用户头像
盼星盼不到星>∆
1月前

哈哈哈,开大是吧?

用户头像
Konjac0629 回复 盼星盼不到星>∆
1月前

开大是什么意思awa

用户头像
盼星盼不到星>∆
1月前

召唤打捞

用户头像
Konjac0629 回复 盼星盼不到星>∆
1月前

原来如此awa

抱歉ww高考假没看论坛

用户头像
盼星盼不到星>∆ 回复 Konjac0629
1月前

哇!佬高三啊!盼星才六年级@_@

用户头像
Konjac0629 回复 盼星盼不到星>∆
1月前

我高二哈哈哈(但马上就要是高三了ww

加油哇盼星

年轻人好好努力(doge

用户头像
盼星盼不到星>∆ 回复 Konjac0629
1月前

嘻嘻谢谢jj-bixin