ガウス素数大富豪 入門と理論

素数大富豪 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

ガウス素数大富豪 inserted by FC2 system