【學習筆記】關于最大公約數(gcd)的定理

手動博客搬家: 本文發表于20181004 00:21:28, 原地址https://blog.csdn.net/suncongbo/article/details/82935140

結論1

\[\gcd(x^{a}-1,x^{b}-1)=x^{\gcd(a,b)}-1\]
證明:
采用數學歸納法。
令\(a=kb+p\), 則有\(\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^{(a\mod b)}-1)\).
中間一步利用到了如下結論: \((x-1)|(x^k-1)\), 證明直接因式分解: \(x^k-1=(x-1)(\sum^{k-1}_{i=0} x_i)\)

結論2

\[\gcd(Fib(a),Fib(b))=Fib(\gcd(a,b))\]
其中\(Fib(x)\)為Fibonacci數列第\(x\)項。
證明:
首先證明一個結論: \(Fib(a+b)=Fib(a-1)Fib(b)+Fib(a)Fib(b+1)\)
采用數學歸納法: \(b=1, Fib(a+b)=Fib(a+1)=Fib(a)+Fib(a-1)=Fib(a-1)Fib(1)+Fib(a)Fib(2)\)
\(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-1, b-2\)成立，則\(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(Fib(n),Fib(n-1))=1\) (數學歸納同樣可證)，然后不妨設\(a>b\), 依然可以數學歸納證明，假設上式對于\(a,b\)成立，則\(\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(n)=af(n-1)+bf(n-2), (\gcd(a,b)=1)\)的遞推關系式都適用，因此對于此類關系式都有\(\gcd(f(a),f(b))=f(\gcd(a,b))\).

發表于 2019-01-22 19:48 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

總結

以上是生活随笔為你收集整理的【学习笔记】关于最大公约数(gcd)的定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。