概述
结论1
gcd
(
x
a
−
1
,
x
b
−
1
)
=
x
gcd
(
a
,
b
)
−
1
gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1
gcd(xa−1,xb−1)=xgcd(a,b)−1
证明:
采用数学归纳法。
令
a
=
k
b
+
p
a=kb+p
a=kb+p, 则有
gcd
(
x
a
−
1
,
x
b
−
1
)
=
gcd
(
x
k
b
+
p
−
1
,
x
b
−
1
)
=
gcd
(
x
p
(
x
k
b
−
1
)
+
x
p
−
1
,
x
b
−
1
)
=
gcd
(
x
p
−
1
,
x
b
−
1
)
=
gcd
(
x
b
−
1
,
x
(
a
m
o
d
  
b
)
−
1
)
gcd(x^a-1,x^b-1)=gcd(x^{kb+p}-1,x^b-1)=gcd(x^p(x^{kb}-1)+x^p-1,x^b-1)=gcd(x^p-1,x^b-1)=gcd(x^b-1,x^{(amod b)}-1)
gcd(xa−1,xb−1)=gcd(xkb+p−1,xb−1)=gcd(xp(xkb−1)+xp−1,xb−1)=gcd(xp−1,xb−1)=gcd(xb−1,x(amodb)−1).
中间一步利用到了如下结论:
(
x
−
1
)
∣
(
x
k
−
1
)
(x-1)|(x^k-1)
(x−1)∣(xk−1), 证明直接因式分解:
x
k
−
1
=
(
x
−
1
)
(
∑
i
=
0
k
−
1
x
i
)
x^k-1=(x-1)(sum^{k-1}_{i=0} x_i)
xk−1=(x−1)(∑i=0k−1xi)
结论2
gcd
(
F
i
b
(
a
)
,
F
i
b
(
b
)
)
=
F
i
b
(
gcd
(
a
,
b
)
)
gcd(Fib(a),Fib(b))=Fib(gcd(a,b))
gcd(Fib(a),Fib(b))=Fib(gcd(a,b))
其中
F
i
b
(
x
)
Fib(x)
Fib(x)为Fibonacci数列第
x
x
x项。
证明:
首先证明一个结论:
F
i
b
(
a
+
b
)
=
F
i
b
(
a
−
1
)
F
i
b
(
b
)
+
F
i
b
(
a
)
F
i
b
(
b
+
1
)
Fib(a+b)=Fib(a-1)Fib(b)+Fib(a)Fib(b+1)
Fib(a+b)=Fib(a−1)Fib(b)+Fib(a)Fib(b+1)
采用数学归纳法:
b
=
1
,
F
i
b
(
a
+
b
)
=
F
i
b
(
a
+
1
)
=
F
i
b
(
a
)
+
F
i
b
(
a
−
1
)
=
F
i
b
(
a
−
1
)
F
i
b
(
1
)
+
F
i
b
(
a
)
F
i
b
(
2
)
b=1, Fib(a+b)=Fib(a+1)=Fib(a)+Fib(a-1)=Fib(a-1)Fib(1)+Fib(a)Fib(2)
b=1,Fib(a+b)=Fib(a+1)=Fib(a)+Fib(a−1)=Fib(a−1)Fib(1)+Fib(a)Fib(2)
b
=
2
,
F
i
b
(
a
+
b
)
=
F
i
b
(
a
+
2
)
=
F
i
b
(
a
+
1
)
+
F
i
b
(
a
)
=
2
F
i
b
(
a
)
+
F
i
b
(
a
−
1
)
=
F
i
b
(
a
−
1
)
F
i
b
(
2
)
+
F
i
b
(
a
)
F
i
b
(
3
)
b=2, Fib(a+b)=Fib(a+2)=Fib(a+1)+Fib(a)=2Fib(a)+Fib(a-1)=Fib(a-1)Fib(2)+Fib(a)Fib(3)
b=2,Fib(a+b)=Fib(a+2)=Fib(a+1)+Fib(a)=2Fib(a)+Fib(a−1)=Fib(a−1)Fib(2)+Fib(a)Fib(3)
对于更大的
b
b
b, 假设有结论对
b
−
1
,
b
−
2
b-1, b-2
b−1,b−2成立，则
F
i
b
(
a
+
b
)
=
F
i
b
(
a
+
b
−
1
)
+
F
i
b
(
a
+
b
−
2
)
=
F
i
b
(
a
−
1
)
F
i
b
(
b
−
1
)
+
F
i
b
(
a
)
F
i
b
(
b
)
+
F
i
b
(
a
−
1
)
F
i
b
(
b
−
2
)
+
F
i
b
(
a
)
F
i
b
(
b
−
1
)
=
F
i
b
(
a
−
1
)
(
F
i
b
(
b
−
2
)
+
F
i
b
(
b
−
1
)
)
+
F
i
b
(
a
)
(
F
i
b
(
b
−
1
)
+
F
i
b
(
b
)
)
=
F
i
b
(
a
−
1
)
F
i
b
(
b
)
+
F
i
b
(
a
)
F
i
b
(
b
+
1
)
Fib(a+b)=Fib(a+b-1)+Fib(a+b-2)=Fib(a-1)Fib(b-1)+Fib(a)Fib(b)+Fib(a-1)Fib(b-2)+Fib(a)Fib(b-1)=Fib(a-1)(Fib(b-2)+Fib(b-1))+Fib(a)(Fib(b-1)+Fib(b))=Fib(a-1)Fib(b)+Fib(a)Fib(b+1)
Fib(a+b)=Fib(a+b−1)+Fib(a+b−2)=Fib(a−1)Fib(b−1)+Fib(a)Fib(b)+Fib(a−1)Fib(b−2)+Fib(a)Fib(b−1)=Fib(a−1)(Fib(b−2)+Fib(b−1))+Fib(a)(Fib(b−1)+Fib(b))=Fib(a−1)Fib(b)+Fib(a)Fib(b+1)
因此假设成立。
然后考虑如何证明
gcd
gcd
gcd: 首先
gcd
(
F
i
b
(
n
)
,
F
i
b
(
n
−
1
)
)
=
1
gcd(Fib(n),Fib(n-1))=1
gcd(Fib(n),Fib(n−1))=1 (数学归纳同样可证)，然后不妨设
a
>
b
a>b
a>b, 依然可以数学归纳证明，假设上式对于
a
,
b
a,b
a,b成立，则
gcd
(
F
i
b
(
a
+
b
)
,
F
i
b
(
a
)
)
=
gcd
(
F
i
b
(
a
−
1
)
F
i
b
(
b
)
+
F
i
b
(
a
)
F
i
b
(
b
+
1
)
,
F
i
b
(
a
)
)
=
gcd
(
F
i
b
(
a
−
1
)
F
i
b
(
b
)
,
F
i
b
(
a
)
)
=
gcd
(
F
i
b
(
b
)
,
F
i
b
(
a
)
)
=
F
i
b
(
gcd
(
a
,
b
)
)
=
F
i
b
(
gcd
(
a
+
b
,
a
)
)
gcd(Fib(a+b),Fib(a))=gcd(Fib(a-1)Fib(b)+Fib(a)Fib(b+1),Fib(a))=gcd(Fib(a-1)Fib(b),Fib(a))=gcd(Fib(b),Fib(a))=Fib(gcd(a,b))=Fib(gcd(a+b,a))
gcd(Fib(a+b),Fib(a))=gcd(Fib(a−1)Fib(b)+Fib(a)Fib(b+1),Fib(a))=gcd(Fib(a−1)Fib(b),Fib(a))=gcd(Fib(b),Fib(a))=Fib(gcd(a,b))=Fib(gcd(a+b,a)).
证毕。
推广: 由于
f
(
a
+
b
)
=
f
(
a
−
1
)
f
(
b
)
+
f
(
a
)
f
(
b
+
1
)
f(a+b)=f(a-1)f(b)+f(a)f(b+1)
f(a+b)=f(a−1)f(b)+f(a)f(b+1)对多种能表示成
f
(
n
)
=
a
f
(
n
−
1
)
+
b
f
(
n
−
2
)
,
(
gcd
(
a
,
b
)
=
1
)
f(n)=af(n-1)+bf(n-2), (gcd(a,b)=1)
f(n)=af(n−1)+bf(n−2),(gcd(a,b)=1)的递推关系式都适用，因此对于此类关系式都有
gcd
(
f
(
a
)
,
f
(
b
)
)
=
f
(
gcd
(
a
,
b
)
)
gcd(f(a),f(b))=f(gcd(a,b))
gcd(f(a),f(b))=f(gcd(a,b)).
最后
以上就是健壮夏天为你收集整理的【学习笔记】关于最大公约数(gcd)的定理的全部内容，希望文章能够帮你解决【学习笔记】关于最大公约数(gcd)的定理所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复