ガウス素数大富豪 入門と理論
素数大富豪 Advent Calendar 2018への参加です。
今日は12/23です。1223は素数です。ガウス素数でもあります。12+23iもガウス素数です。
そういうわけでこの日を獲りました。
-----
ガウス素数大富豪、流行らないのは予想されたことですが、でも、例えば
・ゲームバランスとしてはそれなりに成り立っている
・二次体の整数論への入り口に良い
・たまに素数を覚えるきっかけになる
(例えば適当に出した910+43iがガウス素数だったついでに91043が素数だということを知る)
程度の意義があるんじゃないかなと思っています。
・そう言えばガウス素数判定アプリが無いやと思って
素数仲間探しでガウス素数も判定できるようにしました
(ついでに仲間も探せます)
・[追記] そういえばiが何か説明してなかった
「大学生にきちんと虚数を教えよう」という資料が印象的で
虚数を説明するにはいろいろな視点があるけど
ガウス素数大富豪入門という文脈からは、次を引用しておこう:
「iの入った数式をiを文字として計算し,i^2 があればそれを -1 で置き換えればよい」
-----
[入門]
[1] とりあえず遊ぶための知識
[2] 倍数判定法
[3] ぱっと見ガウス素数
[もうすこし先]
[4] 2枚出し最強クラスの紹介
[5] 合成数出しについて
[6] 13以上の素数判定の例
[おまけ]
[7] 素因数分解の理論
[8] A^2+B^2=pの整数解は X^2≡-1 (mod p)となるX/pの分数近似に現れる
[9] (2+i)^nは実数ではないことを示せ
[1] とりあえず遊ぶための知識
実部と虚部を設定して場に出す。(実部だけでも良い。)
合成数出しは[5]で説明する。実際難しいし、最初は素数出しだけで十分である。
実部がn枚、虚部がm枚のとき、Max(m,n)枚出し と扱う。
通常の素数大富豪のように、k枚出しにはk枚出しで返す必要がある。
ガウス素数には2つのパターンがある。
・a^2+b^2 が素数となるような a+bi
・aが4N+3型素数であるような a
従って、3,7,11は1枚で出すことができる。
次にa+biの形の1枚出しガウス素数を挙げて行く。括弧の中はa^2+b^2の値である。
1+i (2)
2+i (5)
3+2i (13)
4+i (17)
5+2i (29)
6+i (37)
5+4i (41)
7+2i (53)
6+5i (61)
8+3i (73)
8+5i (89)
9+4i (97)
10+i (101)
10+3i (109)
8+7i (113)
11+4i (137)
10+7i (149)
11+6i (157)
13+2i (173)
10+9i (181)
12+7i (193)
13+8i (233)
13+10i (269)
13+12i (313)
以上23種類である。
通常の素数大富豪での2枚出し(38個)より少ないぐらいで、100以下の素数(25個)と同程度の量である。
しかし、暗記する必要は無い。
100以下では2,3,5の倍数を回避し、それから77と91を避ければ、残りは素数であった。
ガウス素数でも同様の状況である。
[2]で2,3,5の倍数判定について説明し、生き残ったぱっと見ガウス素数を[3]で挙げる。
2桁を2枚を使うものは、ちょうど通常の2枚出しできる1013と1213と同じ組み合わせが出現している。
また、12が12+7iでしか使えないのも、通常の2枚出しとなぜか似ている。
強さは、a^2+b^2の値で決める。つまり複素数としての絶対値の大小である。
従って例えば 5+4i < 7 < 6+5i という大小関係が成り立つ。
また、実部aと虚部bを逆にしても同じ効果とする。
[2] 倍数判定法
a^2+b^2 が合成数なら、a+biは合成数である。
・2の倍数判定
まず偶奇を観察することで、
1+iを除いて、実部と虚部には、奇数と偶数が1つずつ、という条件になる。
3+5i, 4+6i, 7+3i などはすべてa^2+b^2が2の倍数となるので合成数である。
ということは、奇数と偶数をバランス良く残しておくことが求められる。
・3の倍数判定
これは簡単である。
a+biが3の倍数 ⇔ a,bがともに3の倍数 が成立する。理論は[7]で。
だから、6+6i とか 9+12i を出さなければ良い。
通常の素数大富豪と違って手札の合計が3の倍数でも問題ない(2+iや5+4iはガウス素数)。
・5の倍数判定
まずa,bのどちらも5の倍数でない場合を考える。
実は、実部と虚部の1の位の組み合わせで判定できる。
(1,2),(1,8), (3,4),(3,6), (7,4), (7,6), (9,2), (9,8) の組み合わせで5の倍数となる。
まとめると
*5に近い奇数(3,7)と偶数(4,6)の組
*5に遠い奇数(1,9)と偶数(2,8)の組
が5の倍数となる。
だから5の倍数を避けるには1の位を
*5に近い奇数(3,7)と5に遠い偶数(2,8)の組
*5に遠い奇数(1,9)と5に近い偶数(4,6)の組
の組み合わせで出せば良い。
*a,bの片方が5の倍数の時は、もう片方が5の倍数でなければ良い。
5+2i,5+4i,5+6i,5+8iは四つ子ガウス素数である。
10+i,10+3i,10+7i,10+9iも四つ子ガウス素数である。
・7の倍数や11の倍数のような4N+3型素数の倍数判定は、3の倍数と同様である。
・次に自明でないのは13の倍数判定となる。
これは簡単ではないと思う。判定法の1つを、[6]で紹介する。
[3] ぱっと見ガウス素数
[2]の2,3,5の倍数判定で生き残ったものを「ぱっと見ガウス素数」と名付ける。
1枚出しで、ガウス素数ではない、ぱっと見ガウス素数は、なんと以下の2つだけである:
12+5i (169=13^2)
10+11i (221=13*17)
これを避ければ良い。(ちなみに1011も合成数でしたね。)
> 2桁を2枚を使うものは、ちょうど通常の2枚出しできる1013と1213と同じ組み合わせが出現している。
> また、12が12+7iでしか使えないのも、通常の2枚出しとなぜか似ている。
を思い出すことで、回避することも可能である。
そういうわけで、1枚出しでは ぱっと見ガウス素数は、実際ほとんどガウス素数である。
[4] 2枚出し最強クラスの紹介
2枚出し強者を挙げた:
1213+1312i (3192713)
1213+1310i (3187469)
1111+1310i (2950421)
1213+1212i (2940313)
1313+1012i (2748113)
1311+1010i (2738821)
913+1312i (2549669)
1013+1210i (2490269)
1011+1210i (2497221)
1313+812i (2383313)
813+1312i (2382313)
1313+810i (2380069)
813+1310i (2377069)
811+1310i (2373821)
1213+910i (2299469)
911+1210i (2294021)
713+1312i (2229713)
1013+1112i (2262713)
813+1210i (2125069)
913+1110i (2065669)
1011+1010i (2042221)
2枚出しは実質4枚出しとなるので、組み合わせが多く、大変である。
2枚出しになると、[2]の判定だけではやはり判定しきれない。
ギャンブルも楽しもう。
[5] 合成数出し
これは、ルールの中で最も難しく、手間がかかる所になる。
実現も難しいし、ゲームするには知らなくても良いぐらいである。
しかしながら、二次体の整数論の入り口としては、良いきっかけかもしれない。
[5-1] 概念
a+bi(a,bは整数)をガウス整数と呼ぶ。
任意の整数が、いくつかの素数(および-1)の積で表せるのと同じように、
任意のガウス整数は、いくつかのガウス素数(およびiの冪)の積で表すことができる。
[1]の最初に提示したように、
4N+3型素数はガウス素数でもあるが、2と4N+1型素数は2つのガウス素数の積に分解する。
これを視覚的に描写し、例えば(2±i)は5の「上にある」という言葉を使うことにする。
つまり4N+1型素数の上には2つのガウス素数がある。
ここでiの冪の違いは同等なガウス素数とみなす。(3と-3を同等な素数とみなすようなものである)
*i(1-i)=1+i なので、(1+i)と(1-i)は同等なガウス素数である。
*(2+i)と(2-i)は同等ではない。
*(2-i)と(1+2i)は同等である。
*結局 a+bi, b-ai, -a-bi, -b+ai の4つ組が同等となる。
任意のガウス整数はこれらの積に分解できる。(これはすごいことである。)
そしてその分解は、同等を除いて一意的となる。
実際にその素因数を知りたいときには、共役を掛けるという方法が便利である。
例を見るのが一番良い。
例:1211は合成数だったが、12+11iもガウス素数ではない。これの素因数分解を求めたい。
(12+11i)(12-11i) = 12^2+11^2 = 265 = 5*53 と分解される。
従って、12+11iは、5の上にあるガウス素数と53の上にあるガウス素数の積と考えられる。
よって(2±i)と(7±2i)の積(に同等)だと考えられる。しかし複号はこの考察では分からない。
2-iを試してみる。(懐かしいかもしれない)分母の有理化を使う。
(12+11i)/(2-i) = (12+11i)(2+i) / (2-i)(2+i) = (13+34i)/5
c=13/5, d=34/5 を得た。
これは確かにc^2+d^2=53を満たすが、c+diがガウス整数でないので、ハズレである。
a=2,b=1のほうが正解である。
(12+11i)/(2+i) = (12+11i)(2-i) / (2+i)(2-i) = (35-10i)/5 = 7-2i
すなわち 12+11i = (2+i)(7-2i) と素因数分解できた。
(ちなみにこちらが正解であることは実は 12+11i≡2+i(mod 5)で判断できる。)
注意:
もう1つのめんどくさい手間がある。
実際に12+11iを合成数出しするには、カードの都合で各素因数の実部と虚部を非負にする必要がある。
12+11i = (2+i)*(2+7i)*i というふうに変形する。
素因数場に (2+i) と (2+7i) を出した状態で、12+11i を出せば良い。
あるいは素因数場に (1+2i) と (7+2i) を出した状態で、11+12i を出しても良い。(共役)
他、ゲームのページの説明欄にある「合成数出しの例」も参照。
[6] 13以上の素数判定方法の例
2枚出し以上になると、ぱっと見素数はなかなか素数とは限らないのであった。
ぱっと見素数で判定できない最初の倍数が、13と17である。(従って登場頻度が高い。)
1001チェックのように、まとめて判定する方法を考えてみた。(実用的かどうかは知らない。)
-10+11i = (2+3i)*(1+4i) に注目することで、以下の判定法を得ることができる:
「a^2+b^2が13か17の倍数である ⇔ 10a±11bのどちらかが13か17の倍数」
[説明]
11(a+bi) = 11a+11bi = (10a+11b)i + (11a-10ai) = (10a+11b)i + (10+11i)ai
= (10a+11b)i + (2+3i)(1+4i)ai
10(a+bi) = 10a+10bi = (10a-11b) + (10bi+11b) = (10a-11b) + (10-11i)bi
= (10a+11b) + (2-3i)(1-4i)bi
これを観察することで
(a+bi)が(2+3i)か(1+4i)の倍数 ⇔ (10a+11b)が(2+3i)か(1+4i)の倍数
(a+bi)が(2-3i)か(1-4i)の倍数 ⇔ (10a-11b)が(2-3i)か(1-4i)の倍数
の関係があり
a^2+b^2が13の倍数 ⇔ (a+bi)が(2+3i)か(2-3i)の倍数
a^2+b^2が17の倍数 ⇔ (a+bi)が(1+4i)か(1-4i)の倍数
と合わせることで説明がつく。
[7] 理論
任意のガウス整数が、[5]で紹介したようにガウス素数に分解できることを説明する。
ガウス整数についても倍数、約数という概念を考えることができる。
y=wxとなるガウス整数wが存在するとき
yはxの倍数であり、xはyの約数である、と言うことにする。
このとき±1,±iとは異なるガウス整数a+biがガウス素数であるとは:
<定義1>
・a^2+b^2 が素数となるような a+bi
・aが4N+3型素数であるような a (あるいは-a,±ai)
<定義2>(素元)
x,yをガウス整数とする。
「xyが(a+bi)の倍数ならば、x,yのどちらかが(a+bi)の倍数」が成り立つ。
<定義3>(既約元)
(a+bi)の約数は本質的に1と自身のみである。
すなわち ±1,±i,±(a+bi),±i(a+bi) のみである。
これらの定義が一致することを示す。
証明の精神について少し述べる。
定義2⇒定義3はすぐに従う。
定義3⇒定義2が、素因数分解の一意性に関係する。
参考:https://mathtrain.jp/primeunique
これはユークリッド整域という概念を使って示されることが多いが、
ここでは定義1を経由するという、おそらくあまり見かけない方針を使ってみた。
(具体的には、Z[i]/(a+bi)Z[i]がZ/pZと同型であることを利用した。)
定義3⇒定義1を示すときには、[5]の視覚化で暗黙に使った、
「すべての4N+1型素数の上には2つのガウス素数がある。」という事実を使う
これはガウス整数の性質の最も本質的な所であり、フェルマーの二平方定理としても知られている。
この事実は、そこらへんに証明があり、特に斬新な方針も思い浮かばないので、省略する。
参考:https://mathtrain.jp/twosquare
http://tsujimotter.hatenablog.com/entry/2014/03/21/025930
-----
・<定義1>⇒<定義2>
*p=a^2+b^2 が素数となるような a+bi の場合
「剰余」を有理数の範囲でとることができるという視点を使う。
つまり x=c+di を(a+bi)で割った余りというものを考える。
bはpと互いに素だから、bk≡d (mod p) となるようなkをとることができる。
x = c+di = x'+k(a+bi)+p(u+vi) と変形できるので、
(x-x')が(a+bi)の倍数となるような有理整数x'をとることができる。
このとき「xが(a+bi)の倍数 ⇔ x'が(a+bi)の倍数 ⇔ x'がpの倍数」が成り立つ。
左の同値は上記の式変形による。右の同値(⇒方向)は、
x'/(a+bi) の分母を有理化して x'a/pとx'b/pが整数であることから言える。
また、この記号を使って、(xy)' ≡ x'y' (mod p) が成り立つ。
これは通常の合同式での a≡b, c≡d ならば ac≡bd の証明と同様である。
そういうわけで xyが(a+bi)の倍数 ⇒ (xy)'がpの倍数 ⇒ x',y'のどちらかがp'の倍数
という手順で定義2を得る。
*pが4N+3型素数であるような p (あるいは-p,±pi)の場合
x=c+di と y=e+fi の積が pの倍数である とおく。
(c^2+d^2),(e^2+f^2)のどちらかがpの倍数であることが要求される。
(c^2+d^2)がpの倍数と設定して良い。
pが4N+3型素数の時、x^2≡-1 (mod p)は解を持たない(より初等的な整数論)ことから
(c^2+d^2)がpの倍数ならば、c,dがともにpの倍数でなければいけないことが言える。
・<定義2>⇒<定義3>
xy = a+bi とおくと定義2より x=z(a+bi) とおける。yz=1が要求される。
これを満たすガウス整数y,zはiの冪しかないことから定義3を得る。
・<定義3>⇒<定義1>
<定義1>に該当しない新しいガウス素数(a+bi)があったとする。
a^2+b^2の値に注目する。これが4N+3型素数の倍数、例えば、3の倍数だったとする。
そうすると<定義1>⇒<定義2>で議論したようにa,bはともに3の倍数なので、
a+biは新しいガウス素数ではない。他の4N+3型素数でも同様である。
次に、a^2+b^2の値が、4N+1型素数の倍数、例えば5の倍数だったとする。
ここで、(2±i)は<定義1>を満たし従って<定義2>を満たすから、
(a±bi)のどちらかが(2±i)の倍数だと言える。
共役の性質を考えれば、(a+bi)は(2±i)のどちらかで割り切れる。
従ってやはり a+biは新しいガウス素数ではない。他の4N+1型素数でも同様である。
残るパターンは、a^2+b^2が2の倍数の場合であり、同様である。
[8] a^2+b^2=pの整数解は x^2≡-1 (mod p)となるX/pの分数近似に現れる
https://twitter.com/icqk3/status/942043278676975617
説明を思い出してみた。
「中間分数近似」の視点を説明する。
あるnに対応するファレイ数列で隣り合う分数の組を「隣り合う分数」と呼ぶことにする。
ファレイ数列 https://mathtrain.jp/farey
・A/B < C/D が隣り合う分数だとする。
A/BとC/Dの間に存在する数Xを近似する分数列を次の手順で得ることができる:
中間分数 E/F=(A+C)/(B+D)をとり、E/FとXの大小に応じて、
区間[A/B,C/D]を、区間[A/B,E/F]あるいは[E/F,C/D]に更新する。
これを繰り返す。(A/B < E/F および E/F < C/D もまた隣り合う分数となる)
・互いに素な整数a,bに対して「a:b重みつき中間分数」E'/F'=(aA+bC)/(aB+bD)は、
A/BとC/Dの間にあり、上記の操作を繰り返すことで得られる。
実感のために1つだけ例を挙げる。a=2,b=7とする。
[A/B, C/D]
→[(A+C)/(B+D), C/D]
→[(A+2C)/(B+2D), C/D]
→[(A+3C)/(B+3D), C/D]
→[(A+3C)/(B+3D),(A+4C)/(B+4D)]
→(2A+7C)/(2B+7D)
この道順はwikipediaファレイ数列のページの画像に緑の矢印で書きこんだ上記画像で描写されている
本題に戻る。x^2≡-1 (mod p)からp=a^2+b^2を求めたい。
1+x^2がpの倍数であり、1+xi = (a+bi)(c+di)とおくことができる。
すなわち ac-bd = 1, ad+bc = x の関係がある。
c/b < d/a は隣り合う分数となる。
また、b:a重みつき中間分数 (bc+ad)/(bb+aa) は x/p に等しい。
従って、[c/b,d/a]はx/pをはさむ隣り合う分数である。
従ってそれらはx/pの中間分数近似に現れる。
*連分数近似で得られる近似分数列は、中間分数近似の部分列となる。
c/b,d/aが連分数近似列にも現れるかどうかは示せていない。
[9] z=(2+i)^n が実数にならないことを証明せよ
(これはtan(2)が有理数でないことを意味する)
ガウス素数の視点で考えることができる:
zはガウス整数だから、もしzが実数なら、zは(通常の意味、つまり実な)整数でもある。
素因数分解の様子から、実な整数は (2+i)の倍数ならば、それは(2-i)の倍数でもある。
そこで(2-i)はガウス素数であるので <定義2>の性質を満たす。
<定義2>の性質を繰り返し使えば、zは(2-i)の倍数ではないことが言える。
従って仮定と矛盾するので、zは実数でない。
(出会い:https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11156197566)
ガウス素数大富豪