x^n-1とx^m-1の最大公約数はx^(n,m)-1となる。(n,m)はnとmの最大公約数
証明
x^n-1=x^(n-m)(x^m-1)+x^(n-m)-1,(x,n,m∈Z)
fn=x^n-1と表すと
fn=kfm+f(n-m)となる(k=x^(n-m))・・・1
(fn,fm)=f(n,m)を示す。
n+mについての数学的帰納法による。
n=m,n=0,m=0のときは明らかに成り立つ
n>m>0とする。
(fn,fm)=(f(n-m),fm)が1式より成り立つ
帰納法の仮定より
(f(n-m),fm)=f(n-m,m)が成り立つ
(n-m,m)=(n,m)だから(fn,fm)=f(n,m)が成り立つ
以上により
(x^n-1,x^m-1)=x^(n,m)-1
Q.E.D.
inserted by FC2 system