多項式は整数のようなもの？
多項式の割り算とGCD
１．多項式も整数も環だ
このワークシートはMath by Codeの一部です。
＜整数は環だ。＞
整数の集まりをZとかこう。
２項演算＋について、＜Z、＋＞は群だったね。
・閉性。a,b∈Zならa+b∈Z。
・ゼロ、ゼロ元は０∈Z
・＋算は結合法則が成り立つ。
・ｘ∈Zの反数、反元は１つのだけ -ｘ∈Zがある。
(＋算は交換法則が成り立つ。)
２項演算×について、＜Z、×＞は逆元の存在以外OKだから、可換なモノイドと言えるね。
・閉性。a,b∈Zならa×b∈Z。
・イチ、イチ元は１∈Z
・×算は結合法則が成り立つ。
（×算は交換法則が成り立つ。)
（Z∋ｘ≠０の逆数、逆元1/xは∉Z。逆元のあるｘのことを単数、単元という。整数では1,-1）
＋、×についての分配法則が成り立つ。
a,b,c∈Zなら(a+b)×c=a×c+b×c
整数は加法群・乗法群を分配法則でつなぎ、乗法の逆元の存在には穴がある。
穴の空いた２群のつながりだから？＜Z,+,×＞を環(Ring)と呼ぶのか？
でも、指輪のリングではなく、ボクシングのリング・土俵、領域・区域という意味のRingらしい。
環は交換法則は標準ではないけれど、たいていが可換環だ。むしろ、非可換環の方がまれかもしれない。
だから、環は定義上は可換である必要はないが、たいてい可換なので可換環とはあえて呼ばないようだ。
整数は無定義に語ったけど、
ｎ次の多項式K[X]は、係数の集合をKとしたときのXの最高次数がｎの項の和の式とする。
Kが整数ZならZ[X], Kが実数ならR[X]、一般にf[X]のようにかく。
f[X]=ΣanXnと書ける。(an≠0)
＜多項式も環だ＞
実数係数のR[X]を簡単にZと書いてみよう。
□２項演算＋について、＜Z、＋＞は群だ。
・閉性。a,b∈Zならa+b∈Z。
・ゼロ元は定数項の式０∈Z
・＋算は結合法則が成り立つ。
・ｘ∈Zの半元は１つのだけ -ｘ∈Zがある。
（＋算は交換法則が成り立つ。）
□２項演算×について、＜Z、×＞は逆元の存在以外がOKだ。
可換なモノイドだね。
・閉性。a,b∈Zならa×b∈Z。
・イチ元は定数項の式１∈Z
・×算は結合法則が成り立つ。
（×算は交換法則が成り立つ。）
（Z∋ｘ≠０の逆元1/xは分数式∉Z。単元は０以外の定数）
□＋、×についての分配法則が成り立つ。
a,b,c∈Zなら(a+b)×c=a×c+b×c
多項式R[X]をZと名前を変えても、同じように環(Ring)になることがわかったね。
２．環から整域へ
＜環の用語を確認しよう＞
環の性質は整数の計算の一般化とも言える。
整数、整数計算がもっている面白い性質といえば、何でしょうか？
倍数、約数の数列を作ったり、最大公約数、最小公倍数
さらには素数を見つけたりしたね。
最小公倍数のもとは、最大公約数だった。
そして、最大公約数は連除法もあったけど、ユークリッドの互除法という、割り算の繰り返しから求められた。その根拠は、割り算の余りは割る数よりも小さい正の数だった。
この「割り算の原理」が多項式でも成り立つと、
多項式にも約数、倍数、GCM,LSM,素数を生み出せるかもしれないね。。。。。。
環の世界の特殊が整数だということなので、用語を整数から環に言い換えをしておこう。
構造的には整数でも環でも同じ意味になりますね。
整数では約数、倍数というのがあった。これを筆頭に、
約数、倍数、単数（1,-1)、素数、公約数、最大公約数、互いに素は最大公約数が１、公倍数
数を元に変えます。
約元、倍元、単元、素元、公約元、最大公約元、互いに素は最大公約元が単元、公倍元。
素数がその数と単数しか約数がない数だった。
素元はその数と単元しか約元がない要素になるね。
では、これを多項式の世界に移すとどうなるだろうか。
約元は因数分解の因数だね。
単元は０でない数、０以外の定数は、多項式にとってはイチとして見るということだね。
素数は既約多項式。その係数の世界で因数が定数かその式自身しかないということだね。
公約元は共通因数だ。これはよく使っていたでしょう。
＜普通の整数らしい環が整域＞
ｙ≠０のｙに対してｘ＊ｙ＝０となるｘを零因子（ゼロ因子）と呼ぶけれど、
整数環の世界ではｘ＝０しかないけれど、集合や演算が変わればゼロ以外のゼロ因子がありうるね。
整数以外の環の世界ではｘ≠０でも、y≠０に対してｘ＊ｙ＝０になることがある。
＜Z６,+,×＞整数のmod 6での剰余の環={0,1,2,3,4,5}の演算では、
2×3=0、4×3=0。
1×0=0、5×0=0。
だから、
0はもちろん、ゼロ因子。
2,3,4はゼロ以外のゼロ因子だね。
1,5はゼロ因子ではない。
普通の整数からすると、2×3=0、4×3=0は変な計算ができてしまう環だ。
普通の整数らしく、ゼロ以外のゼロ因子がない環、変な計算がない環を「整域」という。
環の定義には、「ゼロ以外のゼロ因子がないものとする」という条件がないために
環の一般定義を変えずに、整数らしい環を、環の特殊として「整域」というネーミングにしたという
流れだと思われる。
・整域のよさは計算が変でないということだけではない。整域なら、簡約法則が使える。
たとえば、a*x=b*xのとき、ｘ≠０なら、a=bとカンタンな式に直してよい。
それは、0=a*x-b*x=(a-b)*xと変形すると、０以外のゼロ因子がない環、整域なら、
(a-b)=0のみ、a=bと断言できるというわけだ。
＜体と整域の関係＞
体は環のうち乗法の逆元があるもの、だから、環の特殊の１つと言える。
すると、環という一般の中に２つの特殊（体と整域）があるということになるね。
では、体と整域の関係はどうなるのだろうか？
a,b,xが体の要素だとしよう。
a*x=b*xで、x≠０ならば、ｘの逆元x-1が存在する。だから、a*x*x-1=b*x*x-1で、a=bとなる。
体では、簡約法則が使える。
y=a-bとおくとき、x*y=x*(a-b)=0としよう。x≠0ならば、x-1が存在するから、y=0となるので、
ゼロでないゼロ因子が存在できない。つまり「体ならば整域」となる。
体は整域よりもさらに特殊なもの
ということがわかる。
つまり、
環＞整域＞体とだんだんと絞り込まれてきたね。
逆から見てみると、体（field）が、選ばれた者たちが戦ったり、集ったりできる競技場で、
そこに入れない者たちでも対戦したり、つながったりできるのが環（リング）ということか。
条件を複数クリアした正方形から見たら、長方形もひし形もずっこけているけど、ちゃんと平行四辺形
というワクに収まっているのと何か似ている気がするね。
3.整域からユークリッド整域へ
＜ユークリッド整域は中道？を行く＞
ユークリッドの整域は、
ユークリッドの互除法と
不定方程式AX+BY=C（CはA,Bの最大公約元Dの倍元）の解法の
前提となる
整除原理「A,B.Q,Rが整域に属するとき、
AをBで割った商がQで余りがRのとき、A＝BQ＋R（Rが正でBより小さい）」
が成り立つ整域を特にネーミングしたものだ。
定義上は例えば、こうなる。
整除原理の一般化した定義
整域＜A,+,×＞の各元ｘに非負整数を対応させる高さ関数H(x)があるものをユークリッド整域という。
・H(x)=0の核はx=0に限る。
・非ゼロのx,y∈AでH(xy)>=H(x)。「＝」はyが単元に限る。
・どの非ゼロのx∈Aとどのy∈Aに対しても、q,r∈Aがあり、y=qx+r で、0<=H(r)＜H(x)
係数の集合を、体R、体C、体Qにすれば、余りRをわる式Bより次数を低いもので求めることができる。
ただし、整除原理が成り立っても、逆元の存在は何ら保証しないから、ユークリッド整域は体になれるとは限らない。
つまり、
整域と体の間にユークリッド整域があるということだね。
整域を体にまで狭めなくても、整除原理が成り立てば、最大公約元もたぶん素元分解も一意的にもっていけるから、それで、ユークリッド整域の存在価値は高いと予想されるでしょう。
環＞整域＞ユークリッド整域＞体だね。
４．整式の素元分解
＜素元分解の一意性＞
整数世界の素数は、多項式世界では既約多項式だった。
整数が素数の積に一意的に分解できるということは
多項式が既約多項式の積に一意的に分解できるということに対応するでしょう。
多項式K[X]がユークリッド整域となるため、
元ｘに対する非負整数、高さ関数H(x)：＝ｘの次数＋１
と定めてみよう。
通常の定数の高さは１，１次式の高さは２、０の高さだけ０。
次数を変えない、高さを変えないイチの働きをする多項式は定数。
多項式を多項式で割ると、割る数より次数が低い余りが決まる。
（例）
たとえば、f=x+1,g=x+2, h=x2+3x+2, i=x2+2x+1 としよう。
単元の高さは1, f,gの高さは2, h,i の高さは３になる。
h=f* g, i= f*f から、h, i の公約元、1, f 。（マイナスの場合は略す。 ）
最大公約元G=fになる。
また、f, gは互いに素。
fとiの最小公倍元L= h*i/G=f*g*f*f/f=f*f*fの３次式となり、高さは４になる。
１次式を１つかけるたびに次数が１あがり、高さが１増える。
だから、高さHが次数＋１という定義は常識にあうね。
さらに、
素元ｐとｐの倍元でないｘとは互いに素だ。互いに素は、最大公約元が単元、高さ１だ。
公倍元は最小公倍元Lの倍元だ。公倍元のうち、最小公倍元の高さHが最小の高さである。
公約元は最大公約元Gの約元だ。公約元のうち、最大公約元の高さHが最大の高さだ。
多項式の公約元は、共通因数だった。
a,bの最大公約元Gと最小公倍元Lの間には、ab=eGLが成り立つ。（eはある単元）
多項式の積商にとって単元倍は些末な違いだから気にしない。
K[X]のKがZのときは、Zを正の整数に限り、一般にモニックな（最高次の係数が１）の多項式に限定するとよいね。
ユークリッド整域では、a,bが互いに素でbcがaの倍元なら、cはaの倍元になる。
(理由）
a,bが互いに素なら、Gが単元eというこで、ab=eLとなり、L=abe'
bcがaの倍元なら、a,bの倍元だから、bc=kL=abe'k
整域だからbで簡約すると、c=ae'kとなり、cはaの倍元となる。
これから、０でも単元でもないどんな元も素元の積で表せる。
・整除原理から、単元でない元なら、どの元も素元になるまで割って行くことができる。
・素元の積がAとBの２通りになった場合、Aの１素元ｐについてみると、A＝Bはｐの倍元だから、
Bの素元のどれかがｐの倍元か単元倍になる。A、Bのともに素元ｐで割る。この作業を繰り返せば、
A、Bのともに単元の積になる。
だから、順序と単元倍の差をのぞくと、それは１通りになる。
（ただし、これは、存在証明のアルゴリズムであり、構成するアルゴリズムではない。）
つまり、ユークリッド整域で素元分解は一意的だ。
質問：２つ整数係数の多項式の割り算の商と余りを求めるコードはどうすれば作れますか。
割り算の関数に適当に名前をつけます。割る方の式はモニックとします。
モニックで、高さが２以上でなければ計算せずにメッセージを出すようにします。
たとえば、divf(A,B)関数として、A,B,そしてA÷Bの商Q、余りZを返すものとしましょう。
係数分離法、組立除法の考え方で多項式を係数のリストとして
データ化します。すると、最高次の係数がリストの０番目になります。
A÷Bのうち、割り算に関係する部分だけX=A,Y=Bとします。
Bの高さ、つまりリストBの長さをh=len(B)とします。
多項式の最大係数が同じなるように、商をたてますから、q=X[0]//Y[0]です。
引き算は先頭次[リストのi=0]での係数の差０になりますから、Z=X-Y*qの計算の次数は[リストのi+1番目]からにします。
引き算をするときに、Yの最後の次の位が必要になるので０を補ってから引き算します。
最後の引き算は、Yの最後までだから、範囲をhではなくh-1にしておきましょう。
また、０を立てたあとに、Xの方がサイズが小さくなるときのため、Xに０を補ってから引き算します。
（※なお、pythonの基本ですが、i in range(h)の範囲は0以上h未満になります。もし、h=3なら、
iは0,1,2の３個の数を動きますね。）
pop()は補った[0]をけずるための行です。
動作確認のために商を立てるごとに余りZを出力しています。
その都度のZを次のXとしてX=Zで更新し、YはずっとBのままです。
[IN]Python======================================
#多項式の割り算
def divf(A, B):
h=len(B)
X=A
Y=B
cnt=0
Q=[]
if len(B)<2 or B[0]!=1:
print("割る式はモニックで１次式以上にしてください。")
return A,B,[],[]
while cnt<=len(A)-h:
q=X[0]//Y[0]
Q.append(q)
print(f"{X}-{Y}×({q})",end="")
if len(X)> h:
Y +=[0]
Z=[X[i+1]-Y[i+1]*q for i in range(h)]
Y.pop()
elif len(X)==h :
Z=[X[i+1]-Y[i+1]*q for i in range(h-1)]
else:
X +=[0]
Z=[X[i+1]-Y[i+1]*q for i in range(h-1)]
X.pop()
X=Z
print(f"={X}")
cnt +=1
return A,B,Q,Z
A,B,Q,R = divf([1,2,0,5],[1,-1,4])
print(f"{A}＝{B}×{Q} + {R}")
print()
A,B,Q,R = divf([-2,0,0,0,0,0],[1,0,-1])
print(f"{A}＝{B}×{Q} + {R}")
print()
A,B,Q,R = divf([1,2],[1,1])
print(f"{A}＝{B}×{Q} + {R}")
print()
A,B,Q,R = divf([1,2,1],[3,3])
print(f"{A}＝{B}×{Q} + {R}")
A,B,Q,R = divf([1,2,1],[3])
print(f"{A}＝{B}×{Q} + {R}")
A,B,Q,R = divf([1,2,1],[0])
print(f"{A}＝{B}×{Q} + {R}")
A,B,Q,R = divf([1,2,1],[1,1])
print(f"{A}＝{B}×{Q} + {R}")
print()#==========================================
[OUT]
[1, 2, 0, 5]-[1, -1, 4]×(1)=[3, -4, 5]
[3, -4, 5]-[1, -1, 4]×(3)=[-1, -7]
[1, 2, 0, 5]＝[1, -1, 4]×[1, 3] + [-1, -7]
[-2, 0, 0, 0, 0, 0]-[1, 0, -1]×(-2)=[0, -2, 0]
[0, -2, 0]-[1, 0, -1]×(0)=[-2, 0]
[-2, 0]-[1, 0, -1]×(-2)=[0, -2]
[0, -2]-[1, 0, -1]×(0)=[-2, 0]
[-2, 0, 0, 0, 0, 0]＝[1, 0, -1]×[-2, 0, -2, 0] + [-2, 0]
[1, 2]-[1, 1]×(1)=[1]
[1, 2]＝[1, 1]×[1] + [1]
割る式はモニックで１次式以上にしてください。
[1, 2, 1]＝[3, 3]×[] + []
割る式はモニックで１次式以上にしてください。
[1, 2, 1]＝[3]×[] + []
割る式はモニックで１次式以上にしてください。
[1, 2, 1]＝[0]×[] + []
[1, 2, 1]-[1, 1]×(1)=[1, 1]
[1, 1]-[1, 1]×(1)=[0]
[1, 2, 1]＝[1, 1]×[1, 1] + [0]
ユークリッドの互除法を使うと最大公約数を求めることができましたね。
A,BからX=A,Y=Bとし、[もし、Y＞０ならQ=X/Y, R=X-Y*Q、X=Y,Y=R ]を繰り返すと、
最後の直前のYつまり、Xが最大公約数になるというアルゴリズムが互除法でした。
質問：２つ整数係数の多項式の最大公約元を求めるコードはどうすれば作れますか。
ユークリッドの互除法のアルゴリズムの割り算部分を整数から多項式に置き換えましょう。
Y>０というのはY＝RをしたあとのYのことだから、割り算の余りの式Rの係数がすべて０以外です。
なので、係数の２乗和が正の間は、割り算を繰りかえしましょう。
ただし、せっかく、Yをモニックにしても、割った余りRがモニックでないと、Y＝Rで代入したあとの
計算がうまく進みません。そこで、Yがモニックにならなくなったらモニックにする処理を先頭にして
おきましょう。
[IN]Python
#============
def sqsum(L):
return sum([x**2 for x in L])
def eucld(A,B):
(X,Y) = (B,A) if len(A)0:
if Y[0]!=1:
print(f"Y={Y} => ",end="")
toOne=Y[0]
Y=[x//toOne for x in Y]
print(Y)
A,B,Q,R=divf(X,Y)
X=Y
Y=R
return X
print(eucld([1,2,1],[1,1]))
print(eucld([1,2,1],[2,2]))
A=[1,2,-1,-2]
B=[1,-2,-1,2]
print(eucld(A,B))
#=============
[OUT]
[1, 2, -1, -2]-[1, -2, -1, 2]×(1)=[4, 0, -4]
Y=[4, 0, -4]==>[1, 0, -1]
[1, -2, -1, 2]-[1, 0, -1]×(1)=[-2, 0, 2]
[-2, 0, 2]-[1, 0, -1]×(-2)=[0, 0]
[1, 0, -1]
[IN]python
#===============
A=[1,0,1,1,1]
B=[1,0,1]
print(eucld(A,B))
[OUT]
#==========================
[1, 0, 1, 1, 1]-[1, 0, 1]×(1)=[0, 0, 1]
[0, 0, 1]-[1, 0, 1]×(0)=[0, 1]
[0, 1]-[1, 0, 1]×(0)=[1, 0]
[1, 0, 1]-[1, 0]×(1)=[0, 1]
[0, 1]-[1, 0]×(0)=[1]
割る式はモニックで１次式以上にしてください。
[1]
互いに素になった。
質問：geogebraで多項式の割り算や最大公約元を求めるにはどうしたらよいでしょうか。
数式のビューで、
Division( <割られる多項式>, <割る多項式> )2つの多項式の除算の商と余りを与える．
Division(x^2 + 3 x + 1, x - 1) 出力： {x + 4, 5}.
CASビューで、
GCD( <多項式>, <多項式> )2つの多項式の最大公約数を計算する．
GCD(x^2 + 4 x + 4, x^2 - x - 6) 出力： x + 2.
が使えます。
これを使ってみよう。
geogebraの代数コマンドには、整式の約数まで出せたり、複素数の範囲で因数分解できたりと
スゴイです。geobebraの技術力は素晴らしい！