これでも環
ガウス整数の倍元
このワークシートはMath by Codeの一部です。
＜環のリングのゴングはなった！＞
きちんとルールに合格した体（フィールド）とちがって、環（リング）は少しずっこけていても参加できる場所だった。ということは、環のリングには、普通でない？数も参加できるという気がするね。
では、どんな数が登場できるのだろうか？
１．ガウス整数
＜ガウス整数は環だ＞
ガウス整数は複素数で実部も虚部も整数のものだ。
いたって単純な定義だ。これが環ならガウス整数環と名付けてあげよう。
整数の集まりをZ[i]とかこう。
２項演算＋について、＜Z[i]、＋＞は可換群だ。
・閉性。a,b∈Zならa+b∈Z[i] 。
・ゼロは０+0i∈Z[i]だ。
・＋算は結合法則が成り立つ。
・ｘ+yi∈Zの反元は１つのだけ -ｘ+(-y)i∈Z[i]がある。
（＋算は交換法則が成り立つ。成分ごとに見ると整数和だからOK。）
２項演算×について、＜Z[i]、×＞は可換なモノイドだね。
・閉性。x=a+bi, y=c+di∈Z[i]ならxy=(ac-bd)+(ad+bc)i∈Z[i]でOKだ。
・イチは1+0i∈Z[i]だ。
・×算は結合法則が成り立つ。
（×算は交換法則が成り立つ。成分ごとに見ても交換できるからOK）
（逆元がある元（単元）は±１，±iの４元あるね。）
＋、×についての分配法則が成り立つ。
a,b,c∈Z[i]なら(a+b)×c=a×c+b×c
＜複素数のノルム＞
複素数xの原点からの距離の２乗をノルムといい。
ノルムはN(x)とか、|x|2などとかく。
N(x)は非負であり、N(x)=0となるのは、x=0に限る。
N(ab)=N(a)N(b)。だから、Nは準同型写像でもある。
単元のノルム＝１とすると、x2+y2=1となるのは実部か虚部の片方だけの絶対値＝１だから、
単元は±１，±iとなるね。
ガウス整数aの単元倍をした数を同伴数という。a,-a,ai,-aiが互いに同伴数になる。
＜ガウス整数の倍元＞
ガウス整数x=a+biの倍元どうしはどんな関係になるだろうか。
ｘに任意のガウス整数y=m+niをかけたものxy=x(m+ni)=m(x)+n(ix)となる。
だから、x=a+biとix=i(a+bi)の一次結合といえるね。iはｘを90度回転する働きがある。
だから、ガウス平面をベクトル平面としてみると、
ベクトルx=(a,b)を90度回転したix=(-b,a)と原点が作る正方形の４頂点を平行移動した格子点が
ｘ＝a+biの倍数となるね。
質問：ガウス整数1+i,2+i,3+i,4+i,の倍元を視覚化するにはどうしたよいでしょうか。
まず、m=2 + i とします。pythonでは、虚数単位をjとして、虚部が１のときは1jとかきます。
また、mにｘ+yi をかけるとき、x,yを-10以上10以下に動かしたいので、
複素数の生成関数でcomplex(x,y)のようにして、20*20=400個の倍元集合を作ります。
点ごとドットができないので、ｘ座標の数列とｙ座標の数列をリスト渡して描画しましょう。
うまく動くのを確認したら、
#=============== １つで実験
[IN]python
import numpy as np
import matplotlib.pyplot as plt
m = 2 + 1j
fig = '*'
bai=[m*complex(x,y) for x in range(-10,10) for y in range(-10,10)]
xs=[c.real for c in bai]
ys=[c.imag for c in bai]
plt.plot(xs,ys,fig)
#======================== 複数を同時にかく
[IN]python
import numpy as np
import matplotlib.pyplot as plt
m = [1 + 1j, 2 + 1j, 3 + 1j, 4 + 1j]
fig = ['.','*','+','^']
for num in range(len(m)):
bai=[m[num]*complex(x,y) for x in range(-10,11) for y in range(-10,11)]
xs=[c.real for c in bai]
ys=[c.imag for c in bai]
plt.plot(xs,ys,fig[num])
[OUT]
geogebraでも視覚化してみよう。
ガウス整数の倍元
＜割り算の商と余り＞
ガウス整数x=a+biの高さH(x)をノルムN(x)=a2+b2で定義してみよう。N(x)は非負整数だ。
・H(x)=0の核はx=0に限るから、１対１対応でOK。
・非ゼロのx,y∈Z[i]でH(xy)>=H(x)。＝はyが単元のときに限るからOK。
・どの非ゼロのx、y∈Z[i]に対しても、
q,r∈Z[i]があり、y=qx+r で、0<=H(r)＜H(x)となる最小のｒがあるか？
両辺をxで割ると、y/x= q + r/x, H(r/x)<1
z= y/x＝a+bi（a,b∈R)。
zがガウス平面の格子点のとき、つまり、ｚ∈Z[i]なら、H(r/x)<1だから、r=0。
zが格子点でなく、近い格子点の１つがｃならH(z-c)<1。商をcとするときの余りをrとすると、
z=y/x, xz=yから、r=y-cx=xz-cx=x(z-c)だから、N(r)=N(x)N(z-c)＜N(x)
商も余りも求められるが、格子点でないときは１通りとは限らない。
・割る数よりも小さな余りがあるということは、ガウス整数はユークリッド互除法が使える整域、
ユークリッド整域だね。
ユークリッドの互除法が、ガウス整数での使えるから、
最大公約元が見つかり、素因子分解もできるはずだね。
（例）
y=5+0i, x=-3+0iなら、y/x=5/-3 ,
5=(-1)×(-3)+2 商が-1で、余りが2。
5=(-2)×(-3)+(-1) 商が-2で、余りが-1。
どちらの余りもノルムはN(-3）より小さいが、最小のノルムは(-1)のときだから、
y÷xの商は-2で、余りは-1となるね。
（例）
y=5+4i, x=2-i なら、y/x=y*1/x=y*x'/N(x)=(5+4i)*(2+i)/5=(5*2-4*1)/5+(5*1+4*2)/5i=1.2+2.6i
y/xに近い格子点はq=1+3i。r=y-qx=5+4i-(1+3i)(2-i)=5+4i-{(1*2+3*1)+(6-1)i)=5+4i-5-5i=-i
N(x)=5, N(r)=1だから、rは余りとなる。y÷xの商は1+3i, 余りは-i
質問：ガウス整数でのA÷Bの整除によりQとRを求めるコードでかくとどうなりますか。
A/Bに近い格子点は、ガウス平面でA/Bを囲む正方形の４つの頂点の複素数になります。
それぞれの格子点はcomplex(p,q)のようにして複素数を書き出し、４点のリストを作ろう。
格子点とA/Bとの距離のリストを作り、最小になるインデックスをargminというnumpyの関数を
使って取り出します。こうすると最も近い格子点が取り出せます。
この格子点が商Qになります。余りR=A-B*Qで求められるね。
複素数cのNorm関数はなく、abs(c)を使います。absを２乗しないとノルムにならないのですが、
大小比較だけなら、絶対値で十分ですから。
pythonとgeogebraでやってみよう。
[IN]Python
#ガウス整数の割り算
import numpy as np
def divg(A, B):
h=abs(B)
if abs(B)<2:
print("割る数は単元以外にしてください。")
return A,B,[],[]
qC = A/B
print(f"A/B={qC}")
rel = qC.real
img = qC.imag
xl, yB = int(rel),int(img)
xr, yT = xl + 1, yB + 1
grid = [complex(xl,yT),complex(xl,yB),complex(xr,yT),complex(xr,yB)]
dists = np.array([abs(k-qC) for k in grid])
print(f"{grid}=> {dists}")
indx = dists.argmin()
Q = grid[indx]
R = A - B * Q
return A,B,Q,R
y = 5 + 4j
x = 2 -1j
A,B,Q,R = divg(y,x)
print(f"{A}＝{B}×{Q} + {R}")
print()
[OUT]
A/B=(1.2+2.6j)
[(1+3j), (1+2j), (2+3j), (2+2j)]=> [0.4472136 0.63245553 0.89442719 1. ]
(5+4j)＝(2-1j)×(1+3j) + -1j
＜ガウスの素元＞
3+4iは素元か？
3+4i=abとすると、N(3+4i)=N(a)N(b)
N(3+4i)=25だから、a,bが単元でないなら、N(a)=N(b)=5=4+1=(±2)2+(±i)2=(±1)2+(±2i)2
このうち、3+4i=(22-1)+2*2i=(2+i)2
3+4iは素元ではない。
2=12-i2=(1+i)(1-i)となるから、２は素元でなない。
5=4+1=22-i2=(2+i)(2-i)となるから、５は素元でないね。
3,7,11,19,23は素元だ。
13=9+4=32-(2i)2=(3+2i)(3-2i)となるから、１３は素元でない。
17=16+1=(4+i)(4-i)となるから、１７は素元でない。
29=25+4=(5+2i)(5-2i)となるから、２９は素元でない。
素元でないのは２か、5,13,17,29のように1(mod 4)だと気づく。
素元は3,7,11,19,23のように-1(mod4)と気づくね。
どうしてそうなるのだろうか？
＜素数pがガウスの素元になるとき＞
整数のときのように、単元でも素元でもない元を合成元と呼んでみよう。
ｐが素数でも、ガウス整数としては合成元となりうるね。
だから、非単元のa,bを使ってp=abと分解できる。
素数ｐには虚部がないので、形式的にpの2乗をpとｐの共役元の積とみなすこともできる。
p2=pp'=ab(ab)'=aa' bb'=N(a)N(b)となる。
だから、p=N(a)=N(b)に限るね。a=m+niとおくとN(a)=m2+n2だから、
素数ｐが平方数の和になる。
m,nともに偶数ならp=N(a)≡0+0=0(mod 4)となり、素数pが４の倍数になることになり、あり得ない。
mが偶数、nが奇数ならp=N(a)≡0+1=1(mod 4)となる。
m,nともに奇数ならp≡1+1=2(mod 4)となる。ｐが素数だから、p=2のみあり得る。
だから、素数pがガウス合成元ならｐは２か1(mod 4)となる。
この対偶は、
２より大きい素数pが３(mod 4)ならば素数pはガウス素元になる。
ではガウス素元にならなかったｐは使い道がないのだろうか？
そうではない。
＜一般のガウス素元＞
素数ｐが1(mod 4)のときは素数ｐはガウス素元のaa'の積に分解できた。
a=m+niとおくと、p=N(a)=m2+n2だから、ｐが平方数の和になり、
p=(m+ni)(m-ni)と分解できたね。
a,a'はガウス素元で、そのノルムN(a)=pが1(mod 4）の素数になっていた。
これを逆手にとろう。
一般に、m,n≠0のガウス整数a=m+niが素元なら、ノルムN(a)が素数になる。
だから、ノルムN(a)が合成数ならば、aは素元分解できる。
ガウス整数の整除
質問：素数ｐでガウス素元になるものを抜き出すにはどうしたらよいでしょう。
たとえば、1000以下の素数でガウス素元でもある数を抜き出します。
そのために、素数pのリストPを作ります。
filter(x-> f(x), List)
これがjuliaで、リストListの要素ｘに対して、f(x)が成り立つものに制限する構文です。
a:b
これがjuliaで、整数aからbまでのリストを作る構文です。
ｎを2以上1000とします。
ｎを１つ選んだとして、ｍが1以上n以下のリストを、n%m==0、つまりｎの約数にしたリストにします。
ｎに対して、リストの長さ、つまりｎの約数の個数==2になるｎ、つまり素数ｎにしたリストPにします。
juliaなら、高階関数が楽にかけるので、juliaを選びました。
見かけが少し変わりますが、他の言語でも同様にかけるでしょう。
リストPの要素xに対して、x%4==3となるものにしたリストがガウス素元リストppです。
[IN]julia
# Pは素数リスト
P =filter(n->length(filter( m -> n % m==0,1:n))==2, 2:1000)
# ppは素数で、ガウス素元
pp = filter(k -> k % 4 == 3, P)
println(pp)
[OUT]
[3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, 523, 547, 563, 571, 587, 599, 607, 619, 631, 643, 647, 659, 683, 691, 719, 727, 739, 743, 751, 787, 811, 823, 827, 839, 859, 863, 883, 887, 907, 911, 919, 947, 967, 971, 983, 991]
geogebraでも同様にかけます。
フィルターがfilter(x-> f(x), List)ではなく、KeepIf(f(k),k,List)
剰余の条件がa%b==0ではなく、Mod(a,b)==0
整数リストが1:bではなく、Sequence(b)
になるので、置き換えましょう。
数式を表示して、１行ずつ入力してエンターします。
#==================
L=Sequence(1000)
P=KeepIf(Length(KeepIf(Mod(k,n)==0,n,Sequence(k)))==2,k,L)
pp=KeepIf(Mod(k,4)==3,k,P)
素数ｐがガウス素元でもあるもの
質問：ガウス整数の互除法はどうコードにできますか。
A,BからX=A,Y=Bとし、[もし、Y＞０ならQ=X/Y, R=X-Y*Q、X=Y,Y=R ]を繰り返すと、
最後の直前のYつまり、Xが最大公約数になるというアルゴリズムが互除法でした。
Y＞０はabs(Y)＞０とかける。Q,Rは上で作ったdivg関数を調整して使いましょう。
#ガウス整数の整除
import numpy as np
def divg(A, B):
h=abs(B)
qC = A/B
print(f"A/B = {A}/{B} = {qC}")
rel = qC.real
img = qC.imag
xl, yB = int(rel),int(img)
xr, yT = xl + 1, yB + 1
grid = [complex(xl,yT),complex(xl,yB),complex(xr,yT),complex(xr,yB)]
dists = np.array([abs(k-qC) for k in grid])
indx = dists.argmin()
Q = grid[indx]
R = A - B * Q
print(f"{A} = {B}×{Q} + {R}")
return A,B,Q,R
#ユークリッドの互除法（ガウス整数版）
def eucg(A,B):
(X,Y) = (B,A) if abs(A)0:
A,B,Q,R=divg(X,Y)
X=Y
Y=R
return X
y = 23 + 16j
x = 13 -9j
print(f"G={eucg(y,x)}")
[OUT]
A/B = (23+16j)/(13-9j) = (0.62+1.6600000000000001j)
(23+16j) = (13-9j)×(1+2j) + (-8-1j)
A/B = (13-9j)/(-8-1j) = (-1.4615384615384615+1.3076923076923077j)
(13-9j) = (-8-1j)×(-1+1j) + (4-2j)
A/B = (-8-1j)/(4-2j) = (-1.5-1j)
(-8-1j) = (4-2j)×(-1-1j) + (-2+1j)
A/B = (4-2j)/(-2+1j) = (-2-0j)
(4-2j) = (-2+1j)×(-2+0j) + 0j
G=(-2+1j)
＜ガウス整数ｍ＋iの素元分解＞
ノルムがN(ab)=N(a)N(b)と分解できることと、
ガウス整数のノルムが素数になることを利用して素元分解にチャレンジしよう。
ｘ＝ｍ＋i 型のガウス整数の素元分解をするには、
まず、ノルムN(x)が素数かどうかを計算します。素数でないなら、素因数分解し、
各素数に対応するガウス整数をリストアップしましょう。
そして、その積がｘに等しくなるものをさがします。
また、a+biが素元なら,単元倍の-a-bi,ai-b,b-aiも素元。
実験しやすくするために、
geogebraで、２要素または３要素のガウス整数の積を計算するアプリを作っておきましょう。
（例）
N(1+i)=2から、1+iは素元
N(2+i)=5から、2+iは素元
N(4+i)=17から、4+iは素元
N(6+i)=37から、6+iは素元
N(10+i)=101から、10+iは素元
N(14+i)=197から、14+iは素元
N(16+i)=257から、16+iは素元
N(3+i)=10=2*5=N(1+i)N(2-i)より、 (1+i)(2-i)=3+i
N(5+i)=26=2*13=N(1+i)N(3-2i)より、(1+i)(3-2i)=5+i
N(7+i)=50=2*5*5と、7+i=(1+i)(4-3i)、(4-3i)/(2+i)=1-2iより7+i=(1+i)(2+i)(1-2i)
N(8+i)=65=5*13=N(2-i)N(3+2i) から、(2-i)(3+2i)=8+i
N(9+i)=82=2*41=N(1+i)N(5-4i)から、(1+i)(5-4i)=9+i
N(11+i)=122=2*61=N(1+i)N(6-5i)から、(1+i)(6-5i)=11+i
N(13+i)=170=2*85=2*5*17と、13+i=(1+i)(7-6i)、(7-6i)/(2-i)=4-iから、13+i=(1+i)(2-i)(4-i)
N(15+i)=226=2*113=N(1+i)N(8-7i)から、(1+i)(8-7i)=15+i
一般にmが奇数のとき、m=2n+1とすると、
N((2n+1)+i)=4n2+4n+2=2(2n2+n+1)=N(1+i)N(n+1-n i) となり、
(2n+1) + i =(1+i)(n+1-n i)と分解できる。
さらに、N(n+1-ni)が合成数なら、さらに(n+1-ni)が素元分解できる。
素元分解を検証するためのガウス整数かけ算アプリ
質問：実部と虚部の絶対値が５以下の範囲の素元だけを表示するコードはどうしたら作れますか。
ガウス素元は２種類あります。x=m+niとするとき
A型・N(x)=m2+n2が素数になるもの
B型・素数p≡3(mod4)を単数倍したもの
です。B型のノルムは、p2ですから素数ではありませんが、ガウス素元です。
割り算をするときにNormの代わりにabsを使いました。
しかし、absはルート計算までやってくれているので、Normとしては不適当です。
そのまま、c.real**2+c.imag**2が素数リストPの中にあるかを調べましょう。
#素元だけを表示する。
import numpy as np
import matplotlib.pyplot as plt
def show(length):
# pは素数リスト
norm=length**2
M=list(range(2,norm*2))
divCount=lambda n:len(list(filter(lambda m:n % m==0, list(range(1,n+1)))))
P= [x for x in M if divCount(x)==2]
# 純虚数でも実数でもないガウス整数のnormが素数なら素元である
under5=[complex(x,y) for x in range(-length,length+1) for y in range(-length,length+1)]
sogen= [c for c in under5 if c.real**2+c.imag**2 in P]
# 純虚数か実数の素元（数の絶対値が４で割って３余る素数ｐの単元倍）
pp = [x for x in P if x % 4 ==3 and x < length]
Onenum = [1,-1, 1j, -1j]
psogen = [ x*y for x in pp for y in Onenum]
sogen +=psogen
xs=[c.real for c in sogen]
ys=[c.imag for c in sogen]
plt.plot(xs,ys,'*')
show(5)
範囲を拡大して調べましょう。
show(50)
geogebraにコードを移し替えてみよう。
