ほぼ雑記的メモ
調子こいてもう一発。単なるメモという話もありますが。 4n+1型の素数（すなわち4で割ると1あまる素数）は平方数の和に出来ます。それも只一通りです。不思議なことですが、これは紛れもない事実なのです。 5=1+4 13=4+9 17=1+16 ちなみに4n+3型の素数は平方の和には出来ません。 小さい素数は手当たりしだいに計算していけばいいのですが、巨大な素数となると結構厄介です。（例えば120710677とか） そこでこれを計算するアルゴリズムを紹介します。 まずB=1として A^2+B^2=kp となるような数Aを探します（ようするに二乗して1を足したらpの倍数になる数を探す）。このようなAはpが4n+1型なら必ず存在します。（平方剰余の相互法則） もしk=1ならA^2+1^2 = pだからこれが平方和です。よって、k>1とします。 次のような u, vを探します。 u = A mod k v = B mod k ここでu, vは -k/2からk/2の間に入るようにとります。すると u, vはkを法としてA, Bに合同ですから、A^2+B^2 ≡ u^2+v^2 ≡ 0 (mod k)。すなわち u^2+v^2はkで割り切れることに注意します。 ここで次の恒等式を考えます。 (uA + vB)^2 + (vA - uB)^2 = (A^2 + B^2)(u^2 + v^2) 右辺はk^2で割り切れます。 また、(vA - uB) ≡ 0 (mod k)ですから、(vA - uB)^2も k^2で割り切れます。 故に恒等式が成立するためには (uA + vB)^2も k^2で割り切れなければなりません。 したがって、 (vA - uB)、(uA + vB)はともにkで割り切れます。 A' = (uA + vB)/k B' = (vA - uB)/k k' = (u^2 + v^2)/k とすれば A'2 + B'2 = k'p u, vの条件より k' < kだから A, Bからはじめてより小さいk'を得ることができました。以下これをkが1になるまで繰り返せば平方和が求まります。
参考までに120710677の平方和をこのアルゴリズムで求めると以下の様になります。
46505545^2 + 1^2 == 17916938 * 120710677 18805958^2 + 3^2 == 2929849 * 120710677 7874929^2 + 18^2 == 513745 * 120710677 2586742^2 + 270^2 == 55432 * 120710677 866197^2 + 12690^2 == 6217 * 120710677 283914^2 + 31516^2 == 676 * 120710677 14455^2 + 107238^2 == 97 * 120710677 48346^2 + 8768^2 == 20 * 120710677 18011^2 + 16708^2 == 5 * 120710677 3081^2 + 10546^2 == 1 * 120710677
このアルゴリズムを使用せずに、これを手当たり次第で計算していくのはすごい時間がかかります。このアルゴリズムが如何に便利かがよくわかるかと。
ところで、最初の 46505545^2 + 1^2 をどうやって求めるのでしょう？これを手当たり次第に計算していくのは、偉い時間がかかります。これは原始根をうまく使うと簡単に求められます。
120710677(=p)の原始根は5ですから 5^(p-1) ≡ 1 (mod p) 120710676乗すれば1なのだから、その半分すなわち60355338乗したときの剰余は-1か1です。しかし5は原始根だから (p-1)/2乗したときの剰余は-1。故にその半分 (p-1)/4乗した数が求めるAです。 なぜなら A^2 ≡ (5^((p-1)/4))^2 ≡ 5^((p-1)/2) ≡ -1 (mod p) 故に A^2 + 1 ≡ 0 (mod p) ここでpが4n+1型というのが効いてきます。なぜなら4n+1型でなければ、(p-1)/4は整数ではないからです。 最後に原始根をどうやって求めるのか？という問題もありますが、 これは手当たり次第に計算していくしかありません。ただそれも、全ての冪(2～p-1)をチェックする必要はなく、 p-1の約数乗だけチェックすればいいのです。この場合ですと p-1 = 2^2 3^1 17^2 34807^1 だから36通りのべき乗で1に合同になるかどうかを確認すればよいことになります。 (もっともp-1は絶対1に合同になるし、1乗もあまり意味がないですから、34通りについてどれも1に合同にならないことを示せばOKです） これでチェックが120710676通りから35通りに減らすことができます。
参考 二個の平方数の和 - Wikipedia
追記 A^2 + 1 ≡ 0 (mod p)
の求め方ですが原始根をワザワザ求める必要はありません。適当に数を選んで(p-1)/4乗してみます。すると1/2の確率でAになります。
まず半数の数は(p-1)/2乗すると1、もう半数は-1になります。 -1になる数の平方根は(p-1)/4乗した数です。これがAになります。 確率的なアルゴリズムですが、p-1が大きな約数を持つときはこちらのほうが圧倒的に簡単です。
実際のゲームにおける例を示しましょう。 今、山が３つで １、４、７とします。 この場合 １ ４ １＋２＋４ ですから、１，４の個数は偶数で２の個数が奇数です。故に3つ目の山から2個とり、１，４，５とすれば全ての数が偶数になります。 この後、 １）相手が１の山を取ってしまえば、５の山から１つとり、４，４として勝利が確定。 ２）相手が4の山から1つまたは１つとれば、１，２，３に持ち込めるから勝ち確定。 ３）相手が4の山から３つまたは全部とれば１，１に持ち込めるから勝ち確定。 相手が５の山から取った場合も同様に必勝形に持ち込むことができます。 なぜこのやり方で勝てるのか証明しようと以前おもったけど、一箇所どうしてもうまく証明できませんでした。そこがなんだったかもよく覚えてませんが、とりあえずこれで勝てます。お試しアレ。
LaTeXできれいに書いて清書しようとおもったけど、あまりに膨大な式になるので（何しろ平方根が8個入れ子になる）、calcというUNIXのアプリで計算できる形式にしました。bcだと最後の負の平方根が計算できないんですよね。 これを実行すると、最後にx0に1の257乗根が格納され出力されます。エクセルのマクロにしようかとおもったけど、めんどくさいんでパス。
a0 =-1/2+sqrt(257)/2 a1 =-1/2-sqrt(257)/2 b0 =a0/2+sqrt(a0^2+64)/2 b2 =a0/2-sqrt(a0^2+64)/2 b1 =a1/2+sqrt(a1^2+64)/2 b3 =a1/2-sqrt(a1^2+64)/2 c0 =b0/2+sqrt(b0^2-4*(2*b0+5*b1+4*b2+5*b3))/2 c4 =b0/2-sqrt(b0^2-4*(2*b0+5*b1+4*b2+5*b3))/2 c1 =b1/2-sqrt(b1^2-4*(2*b1+5*b2+4*b3+5*b0))/2 c5 =b1/2+sqrt(b1^2-4*(2*b1+5*b2+4*b3+5*b0))/2 c2 =b2/2+sqrt(b2^2-4*(2*b2+5*b3+4*b0+5*b1))/2 c6 =b2/2-sqrt(b2^2-4*(2*b2+5*b3+4*b0+5*b1))/2 c3 =b3/2-sqrt(b3^2-4*(2*b3+5*b0+4*b1+5*b2))/2 c7 =b3/2+sqrt(b3^2-4*(2*b3+5*b0+4*b1+5*b2))/2 d0 =c0/2+sqrt(c0^2-4*(2*c0+2*c2+c4+2*c5+c6))/2 d8 =c0/2-sqrt(c0^2-4*(2*c0+2*c2+c4+2*c5+c6))/2 d1 =c1/2+sqrt(c1^2-4*(2*c1+2*c3+c5+2*c6+c7))/2 d9 =c1/2-sqrt(c1^2-4*(2*c1+2*c3+c5+2*c6+c7))/2 d2 =c2/2+sqrt(c2^2-4*(2*c2+2*c4+c6+2*c7+c0))/2 d10=c2/2-sqrt(c2^2-4*(2*c2+2*c4+c6+2*c7+c0))/2 d3 =c3/2+sqrt(c3^2-4*(2*c3+2*c5+c7+2*c0+c1))/2 d11=c3/2-sqrt(c3^2-4*(2*c3+2*c5+c7+2*c0+c1))/2 d4 =c4/2+sqrt(c4^2-4*(2*c4+2*c6+c0+2*c1+c2))/2 d12=c4/2-sqrt(c4^2-4*(2*c4+2*c6+c0+2*c1+c2))/2 d5 =c5/2+sqrt(c5^2-4*(2*c5+2*c7+c1+2*c2+c3))/2 d13=c5/2-sqrt(c5^2-4*(2*c5+2*c7+c1+2*c2+c3))/2 d6 =c6/2-sqrt(c6^2-4*(2*c6+2*c0+c2+2*c3+c4))/2 d14=c6/2+sqrt(c6^2-4*(2*c6+2*c0+c2+2*c3+c4))/2 d7 =c7/2+sqrt(c7^2-4*(2*c7+2*c1+c3+2*c4+c5))/2 d15=c7/2-sqrt(c7^2-4*(2*c7+2*c1+c3+2*c4+c5))/2 e0 =d0/2+sqrt(d0^2-4*(d0+d1+d2+d5))/2 e16=d0/2-sqrt(d0^2-4*(d0+d1+d2+d5))/2 e1 =d1/2+sqrt(d1^2-4*(d1+d2+d3+d6))/2 e17=d1/2-sqrt(d1^2-4*(d1+d2+d3+d6))/2 e2 =d2/2+sqrt(d2^2-4*(d2+d3+d4+d7))/2 e18=d2/2-sqrt(d2^2-4*(d2+d3+d4+d7))/2 e7 =d7/2-sqrt(d7^2-4*(d7+d8+d9+d12))/2 e23=d7/2+sqrt(d7^2-4*(d7+d8+d9+d12))/2 e8 =d8/2-sqrt(d8^2-4*(d8+d9+d10+d13))/2 e24=d8/2+sqrt(d8^2-4*(d8+d9+d10+d13))/2 e9 =d9/2-sqrt(d9^2-4*(d9+d10+d11+d14))/2 e25=d9/2+sqrt(d9^2-4*(d9+d10+d11+d14))/2 e15=d15/2+sqrt(d15^2-4*(d0+d1+d4+d15))/2 e31=d15/2-sqrt(d15^2-4*(d0+d1+d4+d15))/2 f0 =e0/2+sqrt(e0^2-4*(e1+e23))/2 f32=e0/2-sqrt(e0^2-4*(e1+e23))/2 f24=e24/2-sqrt(e24^2-4*(e15+e25))/2 f56=e24/2+sqrt(e24^2-4*(e15+e25))/2 g0 =f0/2+sqrt(f0^2-4*f56)/2 x0 =g0/2+sqrt(g0^2-4)/2 x0 x0^257
さて、ここまでは何が面白いのかさっぱりわからんでしょう。ｗ 面白くなるのは、この集まりというのを無限個としてから。 というのも、どんな順序にもその次というのがあり、順序というのはどこまでも定義できる・・・様な気がするわけです。つまり数というのはどこまでも数えられる・・・ １・２・３・・・・１００・・・ そういったことを考えていくと幼稚園児にもできる「数える」という単純な概念ですらとたんに難しくなります。ラッセルのパラドックスなんて有名な矛盾も。 それはそれで面白いんですが私は専門化じゃないんで、詳しくはかけませんが機会があったら書きましょう。 あ、ちなみに自然数の数ってのはよく「可算個」とか「たかだか可算個」って言われます。せいぜい数えられるくらいしかない→たいした数じゃないって意味でよく使われます。 数学者にとって自然数の数なんてたいした数じゃないんですよ。 だからふざけてよくつかいます。どうせ高々可算個でしょ？って。 でもそれって無限の数があるんですけどねぇ～～ （追伸） この日記では一つの「ずる」をしています。それは 「子供という集まりがあるということ」 「そこから一人選べるということ」 を暗黙のうちに仮定してることです。つまり最初っから集合っていうのがあることを仮定して、そこから一人選べるというのを前提にしてるわけです。 これは感覚的に正しいと思えることだけど、数学を厳密にしたいと思ってる人たちには面白くないようで、そういう人たちは公理的集合論とかいうなにがなんだかわけわからんチンプンカンプンなことを考えています。選択公理とか、ツォルンの補題とか、ZF集合論とか・・・ そんなのものを考えはじめると時間がいくらあっても足りないので、上の２つの仮定はそんなもんだと納得しちゃったほうが幸せです。ええ。（結局ここで日よってしまうｗ）
そして、答えは意外なところにありました。それは、ちょっと前までやってたWebラジオ。 まぁちょっとお馬鹿な声優がアフォな質問にアフォな形で答えるというものなんですが、これが実に的確。そしてわかりやすい。それを紹介しましょう。 ---------------------------------------------------- １＋１を１１ １＋１＋１を１１１ １＋１＋１＋１を１１１１ なんて書いてったら百なんて書ききれなくて不便でしょ？ だから１＋１を２って書くんだよ。 ---------------------------------------------------- これは１に１を足したものをなぜ２と書くのかという疑問にしっかりと答えています。ぶっちゃけ２で書かなくてもいいんですよ。二でもいいし、弐でもいいし、IIでもいいし、煮でもいい。 ようするにその文字が２つのものをあらわすということの合意が取れていればいい。 文字ってのは人と人とがコミュニケーションをとるための手段であって、２をどういった字で書こうと２であることには変わりはないのです。 だから、明日から２と３の文字を入れ替えましょうということになっても数学の理論はなんら変わらない（ただ突然２と３の文字が入れかわったら大混乱するとおもうけど）わけです。 次にもうひとつの重要な問題 １の次には２がきて、 ２の次には３がきて、 ３の次には４が来る というきわめて基本的なことに１という縦棒を増やしていくという概念で答えていること。 これって幼稚園とかでは図入りでちゃんと説明してて、むしろ数って概念はこういったところから入るはずなんですが、人間って成長するにつれこういった基本的な感覚を忘れちゃうんですよね。 さて、どういうわけか、世の中のものには順序をつけることができるものが多々あるんです。なぜあるのかは知りませんが、順序をつけるというのはきわめて自然なことのように思われます。きっとこの世界をつくった神様が考えたんでしょう。そのため、 あるものから、ひとつものを取り除いて、１という名前をつけ、 残ったものから、ひとつものを取り除いて、２という名前をつけ、 さらに残ったものから、ひとつものを取り除いて、３という名前をつけられるのです。 この順序に対して、 ひとつ取り除くというのを１ ふたつ取り除くというのを２ といった感じに対応させると ２つ取り除いて２つ取り除くと４つ取り除いたことになるというきわめて自然な現象がうまく説明できます。そして、そういうふうに足し算という演算を定義すると すべての順序数（１，２，３、・・・・）について足し算というのが定義できて、それはわれわれの生活や感覚に非常によくマッチしているわけです。 とまぁきわめて当たりまえのことをとうとうと述べましたが、これをさらに深く追求してったカントルという数学者は集合論という数学の分野を確立し、数に対する興味深い結論をいろいろと発見してったのです。 例えば「無限には何種類もあって、例えば実数の数は自然数の数より圧倒的に多いとか」なんてのがその理論の帰結のひとつ。 どんなつまらないことでもちゃんと考えてみる。大事なことですね。
Powered by Red Leaf ( Rev. c78c769f2 ), © Issei Numata, 2007-2021