目次「RSA暗号について」

中学３年３組　村上賢 ・・・1p

「エジプト分数」

中学２年２組　清水元喜 ・・・8p

「楕円曲線と n = 4」

中学３年２組　小野海 ・・・20p

「角度について」

中学３年３組　西川秀明 ・・・26p

「ライフゲーム」

高校２年１組　浅野知紘　 ・・・46p

「楕円曲線暗号アルゴリズム」

高校２年３組　平野正浩 ・・・58p

「平方和についての考察」

高校２年４組　関典史 ・・・66p

「ブラックジャックにおける親のバーストの可能性」

高校３年１組　大道修 ・・・88p

「整域について」

高校３年２組　二枝翔司 ・・・96p

「公理的集合論による自然数～実数の構成」

高校３年３組　河口祐輝 ・・・108p

「合同分割」

高校３年３組　吉田雄紀 ・・・128p

[表紙]ボロノイ図 (Voronoi diagram)

平面上にいくつかの点があらかじめ与えられている。平面上の全ての点に関

して、それらの与えられた点のうちどの点が最も近いか、を考える。それに

したがって平面全体を分割した図を、ボロノイ図という。ボロノイ図は、情

報科学、生物学、考古学など、さまざまな分野に広い応用を持つ。

1

RSA 暗号暗号暗号暗号についてについてについてについて

M3-3 村上 賢

1.公開鍵暗号と共有鍵暗号 さていきなり RSA暗号だ何だと言われてもわからない方も多いかと思いますので、ここでまず暗号について簡単に話しておきます。 【1】共有鍵暗号 共有鍵暗号とは送信する文字列を送信者がある秘密鍵 Aを使って暗号化し、 受信者は送信者からの暗号文に秘密鍵 Aを用いて解読します。 例えば「すうけん」という文章を送りたいとします。その時送信者は 「あいうえお順に 3 文字後にずらす」という秘密鍵を用意して暗号化し、送信します。 「すうけん」⇒「たかしう」 そして「たかしう」という文章を受け取った受信者は秘密鍵を知っているので そのステップを逆に行い解読します 「たかしう」⇒「すうけん」 しかし、共有鍵暗号には致命的な欠陥があります。それは送信者が受信者と共有すべき秘密鍵をどのようにして受信者に知らせるかという問題です。 これを解決するために生み出された暗号方式が公開鍵暗号です。 【2】公開鍵暗号 さて上で述べたように共有鍵暗号は秘密鍵をいかにして秘密裏に相手に渡すか という問題があります。そこで考え出されたのが公開鍵暗号です。 公開鍵暗号とは、まず受信者が公開鍵と秘密鍵を用意し、公開鍵のみを公開します。送信者は送りたい文面を公開鍵を用いて暗号化し受信者に送ります。 受信者はその暗号文を自分の持っている秘密鍵によって解読します。 この暗号方式のすごいところは公開鍵で暗号化した文章を公開鍵を用いて解読する事が出来ない、という点です。つまり、これによって鍵をいちいち秘密裏に配送せずとも、おおっぴらに電話で公開鍵だけをしらせれば暗号通信を行う事が出来ます。また共有鍵暗号では n人の人間がお互いに通信しようと思えば nC2通りの鍵が必要ですが、この方式なら 2n 個の鍵で十分だという事になります。この特徴はインターネットなど不特定多数が参加する際にとても役に立ちます。 さて、簡単な理論はこのくらいにしておきます。説明が下手なのでよくわからないという方はインターネットなどで調べてはいかがでしょうか。（たぶんその方がわかりやすく書いてあります。）

2

2、下準備 さて本題に入る前に少し下準備といいますか、説明をしておきましょう。ここで説明しておいた方が RSA暗号の説明がわかりやすいからです。 【1】時計代数 ある正の整数 N を定め、0以上 N未満の整数のみを考え、N以上になれば Nを引き、0 未満になれば N を足すという動作を行い、この範囲の整数のみ扱うのを N を法とする代数と言います（時計代数とも呼ばれる）。また、A、Bを Nで割った余りが等しい時「A,Bは Nを法として合同」と言い「A≡B (mod N)」と書きます。またこのような体系を ZNと書くとします。この時 ZNでの加法、減法には特に問題がありませんが、乗法ではいくつか困った現象が起こります。 例えば、 3×6≡0 (mod 2) のように Aも Bも 0 でないのに A、B の積が 0 になることがあります。 また 3×5≡3×9 (mod 12) のように 0でない Aを B,Cに掛けた積が同じなのに B≠Cになることもあります。こうなると割り算が成り立ちませんし、A×B=0 ならば A=0、B=0 という基本法則が成り立たないので因数分解が成立しません。 しかしこれは N が素数ならばこの現象は起きないのです。 何故起きないのかは以下で説明します。 【2】互除法 互除法とは二つの正の整数 Mと Nの最大公約数を求めるアルゴリズムで

1、M と N を比較し必要なら入れ替えて M≧Nとする。 2、M を N で割り、商を Q余りを Rとする。 3、余り R が 0 ならば、そのときの除数 Nが最大公約数である。これで完了 4、余り R が 0 でなければ、除数 Nと余り Rを M、N とおきなおして 2へ戻る。 という手順です。

【3】有限体 さて、上の互助法を応用すれば次のことが言えます。 正の整数 M、Nの最大公約数を D とすると、適当な整数 U、V を取って

MU+NV＝D

3

とすることが出来る。 さて、これの証明をします。

N0＝M、N1＝Nとすると 互除法を用いて N0を N1で割り、商を Q1、余りを N2とする。

N0＝Q1 N1+ N2 これは

N2＝－ Q1 N1 +N0 と書ける。 同様に NＭ－１を NMで割った商を QM、余りを NM+1のようにして互除法をする Nk＝－QkNk-1+Nk-2と Nk+1＝－QkNk+Nk-1 の右辺が M を整数倍したものと、Nを整数倍したものの和になっているとすると、Nk+2＝－Qk+1Nk+1+Nkの右辺は Mを整数倍したものと、Nを整数倍したものの和になっていることが言える。 今、N0＝1×M+0×N、N1＝0×M+1×Nが成り立つので 数学的帰納法よりすべての自然数Ｘにおいて NX+1＝－QXNX+NX-1の右辺が M を整数倍したものと、Nを整数倍したものの和になっていると言える。また D は互除法の余りの中に出てくるから これにより上記の MU+NV＝D は示された。 さて、ここからある重要なことがわかります。

MU+NV＝1 とすると MU＝1－NV。 よって

MU≡1 (mod N) これによりＵはＭの逆数となる、 逆数が存在するので素数 N を法とする代数において 除法を定義する事ができる。 さらに

AB≡0 (mod N)の時 A≡0 (mod N)かつ B≡0 (mod N) が成り立つ。

4

よって素数Ｎを法とする代数において四則計算、交換法則、結合法則、分配法則が全て成り立つ。 このように四則計算ができ、交換法則、結合法則、分配法則が全て成り立つ体系を体という。よって素数 Pを法とする体系ＺpはＰ個の数からなる有限体である。 【4】フェルマーの小定理 素数 Pを法とする体系Ｚpにおいて 0以外の数 Aを取ります そしてＺpの 0以外の数全てにＡを掛けます。 この時計算後のどの二数の差をとっても Aでは割り切れないので 計算後の数は Pを法として全て相異なり、また 0ではない。 したがってこれはＺp の 0 以外の数を全て並べ替えたものである。 よってこの数を全て掛ければＺpの 0以外の数を掛けたものと等しい。 すなわち A

P-1(P－1)！≡(P－1)！ が言える。 また(P－1)！は素数Ｐでは割り切れないので

AP-1≡1 (mod P)

つまり素数Ｐの倍数でない整数Ａは、(P－1)乗すれば、常にＰを法として 1に等しい。 これがフェルマーの小定理である。 さてこの定理から ＡN－1≡1 (mod N) でなければＮは素数ではないという事が導ける。 これは有効な素数判定法であり、フェルマー・テストと呼ばれる。

4、RSA暗号の数理 さて、ここまでが前置きであったわけだが、これから RSA暗号の数学的な理論を書いていきたいと思う。 【1】理論 まず受信者は十分大きな素数Ｐ、Ｑを選びＮ＝Ｐ×ＱとなるＮをとります。 またある指数Ｅをとります。そしてＮとＥを受信者は鍵として公開します。 送信者はある法則に従って平文（送信する文）を符号化します。 符号化は高度な工夫をする必要はあまりありません。 符号化された文をＭとします。 そして送信者はＭを公開鍵Ｎ、Ｅを用いて

5

ＭE≡C (mod N) となるＣを導き、それを受信者に送信します。 受信者は受信した暗号文ＣをＥの対する「逆演算」をあらわす指数Ｄを用いて 暗号文Ｃを復号します。 Ｍ≡CD (mod N) これで受信者は文を受け取ることが出来ます。 【2】指数 さて、理論は上に示したがここで少し問題があります。 それは上の操作に当てはまるような指数Ｄ、Ｅの組み合わせがあるかどうか、という問題であり、また公開鍵から秘密鍵Ｄが特定できるようでは不適です。 さて、そんな都合のいい指数の組み合わせがあるのか、と言うかも知れませんが、この指数の組合せはちゃんと存在します。 さて、上の合同式ＭE≡C (mod N)とＭ≡CD (mod N)より

MDE≡M(mod N)

です。 つまりＭを DE 乗して M と合同になるような組み合わせがあればいいわけです。 ここで N の素因数 P、Qで P－1、Ｑ－1が共に偶数で P－1、Ｑ－1の公約数が2 のみであるようなＰ、Ｑを選びます。公約数が 2でなければいけないという事はないですが、あまり公約数が多いと解読の手がかりとなってしいます。 そして EはＰ－1、Ｑ－1と互いに素であるものを選びます。 ある自然数 Aが P でもＱでも割り切れなければフェルマーの小定理より ＭP-1≡1 (mod P) と ＭQ-1≡1 (mod Q)が言えます つまりＰ－1とＱ－1 の最小公倍数をＬとした場合 ＭL≡1(mod P,Q) つまり、ＭL≡1(mod Ｎ)が成り立ちます この時、P－1 とＱ－1の公約数が 2だけなら L＝(Ｐ－1)(Ｑ－1)÷2 であり Ｐ－1、Ｑ－1はそれぞれＥと互いに素だから、ＬはＥと互いに素です。 よって互除法の所で述べたように

ED+LV=1

を満たす整数 D,Vが存在することがいえます。 よってＥＤ＝1－ＬＶなので

6

MDE≡M1－LV≡M×(ML)－V (mod Ｎ) となり、またＭL≡1(mod Ｎ)より

M×(ML)－V ≡Ｍ (mod N) よって MDE≡M(mod N) つまりこのＤ、Ｅの組み合わせならば M を DE 乗して Mと合同になります。しかもＮの素因数Ｐ、Ｑがわからないと秘密鍵Ｄを導き出すのは非常に難しく、またＰとＱを知っていれば秘密鍵Ｄを計算するのは非常に簡単です。よってこのＤ、Ｅの組合せはＲＳＡ暗号を使用する際に有効な指数の組み合わせであるといえます。 【3】素数判定法 さて、上で理論を満たす指数の組み合わせがあるのはわかりましたが、実際に用いられるような素数とはある程度の大きさを持った素数でなければいけません。よってある整数が素数であるかどうかを判別できる方法が必要です。しかもその方法は整数Ｎ対して 2から√Ｎまでの整数で割れるかどうか一つずつ計算する、というような計算量が膨大すぎる問題では実用的ではありません。 まず、先ほども少し述べたフェルマー・テストです これは「ＡN－1≡1 (mod N) でなければＮは素数ではない」という物でしたが これをいくつかの任意のＡで行い、それをパスした場合このＮは素数である確率が高いといえます。しかし勘違いしてはいけないのは「ＡN－1≡1 (mod N) でなければＮは素数ではない」は真であっても「ＡN－1≡1 (mod N) ならばＮは素数である」は偽なのです（反例 Ｎ＝341）。よってこれだけではＮが素数だと言い切る事はできません そこでこの判定法を精密化したものとして強概素数というものがあります。 Ｎ－1＝2TＵ（Ｕは素数）とおいて ＡT≡1 (mod Ｎ) が成立するかまたはＡ2の S乗×U≡－1 (mod Ｎ)がＴ未満のあるＳで成立する時、ＮをＡに対する強概素数と呼び、Ｎが素数ならＮで割り切れないＡに対して必ずこれが成り立つ。しかし、これもカンペキでなくこれを満たすが素数では無いという強擬素数と呼ばれる物も存在します。これはＮが奇数の合成数の時Ｎ－1までの整数Ａのうち少なくとも四分の三に対してＮはＡに対する強擬素数で無い事が証明されているので十分多くのＡに対してＮが強概素数であることを証明すればＮは素数であるという正しい判定になります。 【5】まとめ 以上の事からＲＳＡ暗号は実用に十分に耐えられる暗号である事がわかります。 いろいろな事情があってかなり中途半端というか薄い内容になってしまいました。いやホントにすいません。もっと深い内容が知りたいと思われる方は本屋で探されてはどうかと。灘生の方々なら、図書室に良く書かれている本が数札あるので興味があったら読んで見てください。 図書室にある資料

7

『暗号の数理』 著 一松 信 『暗号解読 ロゼッタストーンから量子暗号まで』 著 サイモン・シン 他にもあると思います。

ここまで読んで下さってありがとうございます。

ライフゲーム

高校２年１組 浅野知紘

1 はじめに

本日は数学研究部におこしくださりくださり、ありがとうございます。

この記事では「セル・オートマトン」と言うものの中でも、特に一次元の

ものと「ライフゲーム」と呼ばれるものを紹介したいと思います。

セル・オートマトンには無限に並ぶ「セル」と呼ばれる細胞（普通は正方

形や立方体とする）があり、それぞれのセルには何種類かの状態1 があり、セ

ル達は近くのセルの状態に影響を受け時刻ごとにその状態をあるルールに基

づいて変えていきます。

これから幾つかのルールについてどんな感じになっているのか見ていきます。

定義 1

セル達の初期状態を時刻 0の状態とし第 1世代とする。

任意の自然数 tに対し第 t世代の次の状態を第 (t + 1)世代、第 t世代の時刻

を時刻 (t − 1)とする。

セルの状態が生きているか死んでいるかの 2通りの場合、生きているセル

を黒セル、死んでいるセルを白セルと呼ぶ。

2 一次元セル・オートマトン

一次元セル・オートマトンは直線状で、それぞれのセルは両隣の 2つのセ

ルと接している。ある時刻でのあるセルの状態はその直前の時刻のそのセル

自身と両隣のセル（合計 3つのセル）の状態によって決まる。1つのセルの

状態を 2種類とするなら 3つのセルの状態は (23 =)8通りなのでその 8通り

それぞれに次のセルの状態を決定すればそれで 1つのルールが出来上がる。

定義 2

1ここではそのセルが「生きている」か「死んでいる」かの 2 つの状態しか考えません

46

ある一個のセルを 0番セルと名づけ、0番セルから（右隣を 1番目と数え

て）右に a番目のセルを a番セル、0番セルから（左隣を 1番目と数えて）

左に a番目のセルを −a番セルと名づける。

時刻 tで a番セルが黒セルとなっている全ての整数 aの集合を Btと表し、

Bt の補集合（時刻 tで a番セルが白セルとなっている全ての整数 aの集合）

をWt と表す。

b(a,t) を a番セルの時刻 tでの黒白を表すとし、

b(a,t) = 1(a ∈ Bt)

b(a,t) = 0(a /∈ Bt)

という値を持たせる。

定理 1 二つの時刻 t1、t2 を考える（但し t1 ≤ t2）。

時刻 t1の a番セルの状態は、時刻 t2の |b− a| ≤ t2 − t1なる b番セルにのみ

影響を与える2。

証明 1 t2 = t1の時

（同時刻なので）明らかに成り立つ。

t2 = t1 + kのとき成り立つとして t2 = t1 + k + 1の時

時刻 (t2 − 1)を考えると、その時刻には |c− a| ≤ kなる c番セルだけが影響

を受ける。その次の時刻（時刻 t2）にはそれぞれの c番セルは隣までしか影

響を与えないので、|b − a| ≤ k + 1(= t2 − t1)なる b番セルにのみ影響を与

える。

よって数学的帰納法により証明された。

証明終

そしてここからは特に断らない限り B0 = {0}（つまり初期状態に黒セルは 1

つだけある）として考える。

2.1 ルールの表し方

たとえばルール 99というルールを書いてみる。

2影響を与えるセルの状態を変えると、「影響を受けるセルの状態が変化する。」は成り立たないが、「影響を受けないセルの状態は変化しない。」は成り立ちます。

47

111 110 101 100 011 010 001 000

0 1 1 0 0 0 1 1

1は黒セル、0は白セルを表している。

この表の例えば左からに 2列目は「ある時刻に左隣のセルが黒で右隣のセル

が白、それ自体は黒セルであるセルは次の時刻に黒セルになる」と言うこと

を意味している。

このルールをルール 99と言う理由を説明しておく。表の上段は二進法表示

として見ると、左から 7、6、… … 1、0と並んでいる。下段を見ると数字が

01100011と並んでいる。これを二進法表示と見れば十進法の 99と等しいの

でルール 99と名前がついている。

つまりルール 0からルール 255まで 256種類のルールが存在する。

しかし議論を簡単にするためここではルールの表し方を変えることにする。

定義 3 ルール (m, n)

下の表の下段に 0,1を書き入れ3 、左 4つと右 4つをそれぞれ別に二進法表

示と見て、左側の数を m、右側の数を n（0 ≤ m ≤ 15, 0 ≤ n ≤ 15）とする

とそのルールをルール (m, n)と表す4。

À Á Â Ã

010 011 110 111

0 0 1 0

Ä Å Æ Ç

101 100 001 000

1 0 1 1

定義 4 複数のルールについて一度に考える場合Bt、Wt、b(a,t)では不十分な

ので、ルール (m, n)において、時刻 tで a番セルが黒セルとなっている全て

の整数 aの集合を B(m,n)t と表す。またルールが同じでも初期条件などを変

えて複数のパターンについて考える場合 Bt、B(m,n)t に対して B′

t、B′

(m,n)t

等として区別する。（例えば b′(m,n)(a,t)といったように）Wt、b(a,t)に対して

も同様に定義する。

2.2 ルール (12, 6)

これは規則的なパターンとランダムなパターンが混在する複雑なパターン

の代表例である。

010 011 110 111

1 1 0 0

101 100 001 000

0 1 1 0

直線状のセルを時間順に下へ並べていく。

3ここではルール 99 を書き込みました。4ルール 99 はルール (2, 11) と表されます。

48

これを更に続けていった時の模様（ここにかけないのが残念だが）に似てい

るものが自然界で発見されている。

2.3 ルール (6, 6)

010 011 110 111

0 1 1 0

101 100 001 000

0 1 1 0

このルール (6, 6)を図のように並べるとシェルピンスキーのギャスケットと

言うフラクタクル図形5に近づいていく。このことが分かる次の事実を示す。

定理 2 ルール (6, 6) において、t, n ∈ Z として 2n ≤ t < 2n+1 なる時刻

(t − 2n)で a番セルが黒セルの時、時刻 tで (a ± 2n)番セル 2つも黒セルで

ある。

また、時刻 tで b番セルが黒セルの時、b > 0ならば (b − 2n)番セル、b < 0

ならば (b + 2n)番セルが時刻 (t − 2n)で黒セルである。

5（正しい定義ではないが）図形の部分と全体が自己相似になっている図形

49

証明 2 B1 = {1,−1}であることから、時刻 1で 0番セルは白セルである。

ルールの表よりこの後は（0を対称の中心として）左右対称を保ち続ける。つ

まり常に −1番セルと 1番セルの状態は同じであるので、表より 0番セルが

黒セルになることはない。

さらに

B2n = {−2n, 2n}

を示す。これが示されれば、定理 1より（t1 = 2n, t2 = tと考えて）、時刻 t

での b番セルの状態は、0 < −t + 2n+1 ≤ b ≤ tならば時刻 2n の 2n 番セル、

−t ≤ b ≤ t − 2n+1 < 0ならば −2n 番セルからのみ（黒セルからの）影響を

受ける。ここで、その影響の受け方は時刻 (t − 2n)の −t + 2n ≤ a ≤ t − 2n

なる a番セルが時刻 0の 0番セルから受けるものと同じである。そして bが

それらの範囲に無い b番セルは黒セルの影響を受けないので白セルとなる。

これらより B2n = {−2n, 2n}を示せばよいことがわかる。

このことを数学的帰納法で示す。

n = 0の時、（t ∈ Zより n ≥ 0）

B1 = {−1, 1}

が成立。

n = kで成立するとして、n = k + 1の時、

定理 1より（t1 = 2k, t2 = 2

k+1 と考えて）、時刻 2k+1 で、−2k+1 ≤ b ≤ −1

なる b番セルは時刻 2kの−2k番セルからのみ（黒セルからの）影響を受け、

1 ≤ b ≤ 2k+1 なる b番セルは時刻 2k の 2k 番セルからのみ影響を受け、0番

セルは両方からの影響を受ける。

これらより、時刻 2k+1 で、−2k+1 ≤ b ≤ −1なる b 番セルが時刻 2k の

−2k 番セルからの影響の受け方は、時刻 2k での −2k ≤ a ≤ 2k − 1なる a

番セルが時刻 0（の 0番セル）から受ける影響と同じなので、時刻 2k+1 で、

−2k+1 ≤ b ≤ −1なる b番セルのうちで黒セルであるのは−2k+1番セルのみ。

同様に 1 ≤ b ≤ 2k+1 のうちで黒セルになるのは 2k+1 番セルのみ。0番セル

が白であることは証明しているので、

B2k+1 = {−2k+1, 2k+1}

が成立。よって全ての 0以上の整数について示された。

証明終

50

2.4 n ≡ 0(mod.8)の場合

定理 3 n ≡ 0(mod.8)のとき、tを任意の自然数とすると

Bt = {0}(m ≥ 8)

Bt = ∅(m ≤ 7)

証明 3 n ≡ 0(mod.8) は前出の表においてÅÆÇが全て 0（白）であること

と同値である。すると B0 = {0}より、時刻 1に 0番セル以外は全て白セル

（a 6= 0なら b(a,1) = 0）である。m ≥ 8の時、Àが 1（黒）なので、b(0,1) = 1。

この状態がその後も変化せずに続くので上側の式は示される。m ≤ 7の時は、

Àは 0（白）なので b(0,1) = 0。全てのセルが白でÇも 0（白）なのでこの状態

も変化せず続く。これによって下側の式も示される。

証明終

2.5 m + n = 15の場合

この小節では初期状態はどのような状態でもいいことにする。

定理 4 B′0 = W0という関係がある二つの初期状態があるとする。全てのB0

と自然数 tについて B′t = Wt であることは、m + n = 15と同値である。

証明 4 t = 1の場合のみ示せば良い。

010 011 110 111

a1 a2 a3 a4

101 100 001 000

a5 a6 a7 a8表の a1から a8にはそれぞれ、0または 1が入る。

a1から a4（つまりm）を任意に定めれば、（nが一意に定まり）a5から a8が

定まるので、m + n = 15であることは、全ての 1 ≤ h ≤ 4なる自然数 jにつ

いて ah + ah+4 = 1が成り立つことと同値であることが分かる。

まずm + n = 15 ⇒ B′1 = W1 を示す。

任意の a 番セルに注目し、初期状態が B0 で表される方は b(a−1,0)、b(a,0)、

b(a ＋ 1,0)を表と照らし合わせて b(a,1)が定まる。ここで b(a,1)には表の ai(0 ≤

i ≤ 8)が対応していたとする。初期状態がB′0で表される方は b′

(a−1,0)、b′

(a,0)、

b′(a ＋ 1,0)を表と照らし合わせて b′

(a,1)が定まる。ここで b′

(a,1)には表の aj(0 ≤

j ≤ 8)が対応していたとする。

51

B′0 = W0より、例えば b(a,0) + b′

(a,0) = 1であるから、|i− j| = 4が成り立

つ。よって b(a,1) + b′

(a,1) = ai + aj = 1。つまり B′

1 = W1が成り立つ。

次にm + n 6= 15 ⇒ B′1 6= W1 なる B0が存在することを示す。

m + n 6= 15ならば、ah = ah+4 なる自然数 h(1 ≤ h ≤ 4)が存在するので、

B0中に表の ahの上側に対応する 3つのセルの並びを含ませ、その 3つ並び

の真ん中のセルを a番セルとすれば、b(a,1) = ah = ah+4 = b′

(a,1)が成り立つ

ので、B′1 6= W1 となる。

証明終

定理 5 ルール (m, n)に対してルール (n, m)を考える。B(m,n)0 = B(n,m)0の

時、任意の自然数 tに対して B(m,n)2t = B(n,m)2tが成立する。

証明 5 t = 1の場合のみ示せば良い。

ルール (n, m)はルール (15−m, 15−n)とみれば、ルール (m, n)の表の下段

の 0と 1を入れ替えたもであることが分かる。よって任意の自然数 aについ

て b(m,n)(a,0) = b(n,m)(a,0) より、b(m,n)(a,1) + b(n,m)(a,1) = 1である。

B(n,m)1 の状態にルール (m, n)を適用したものを考え、その状態（a番セ

ルが黒セルである aの集合）を B′2 とすると、定理 4よりW(m,n)2 = B′

2 と

なる。

また、B(n,m)1 の状態にルール (n, m) を適用したもの（つまり B(n,m)2）

と B(n,m)1 の状態にルール (m, n)を適用したもの（つまり B′

2）を比べて、

W(n,m)2 = B′

2となる。

よってW(m,n)2 = W(n,m)2、つまり B(m,n)2 = B(n,m)2が成り立つ。

証明終

3 ライフゲーム

3.1 二次元セル・オートマトン

無限に広がる正方形状のセルが敷き詰められた平面があり、それぞれのセ

ルは他の 8個のセルと接していて、それらと影響を及ぼしあう。次の世代（時

刻）にそのセルが白か黒かは周り 8個と自分自身の状態によって決まるので、

(29 =)512通りについて次のセルの状態を決めてやれば一つのルールが出来

上がる。そしてそのルールは 2512種類考えられ、ライフゲームはそのうちの

1つである。

52

3.2 ライフゲーム

まずライフゲームのルールを書く。

• 黒セルの周りに（8個中）2つ若しくは 3つ黒セルがあった場合、次の

世代も黒セルである。（維持）

• 白セルの周りに丁度 3つの黒セルがあった場合、次の世代は黒セルにな

る。（誕生）

• それ以外の場合は次の世代には白セルになる。（死）

このルールは生命にとって過疎も過密も個体の生存には適さないという考え

による。このルールに従って色々な初期状態から始めてみると、黒セルがなく

なる（死滅する）場合も多いが、そうでない場合最終的にセルの集まりを固

定型、周期型、移動型、繁殖型の 4種類に分類6できる。

3.3 固定型

固定型は世代が進んでも場所や形など状態が全く変わらないものをいう。

実際に少し例を挙げてみる。

左から順に「ブロック」「タブ」「ボート」「蜂の巣」「釣り針（イーター）」と

言う名前がついている。3セル（黒セルが 3つ）以下の固定型は存在せず、4

セルの固定型は「タブ」と「ブロック」のみで、5セルの固定型は「ボート」

のみである。

6ここやそれ以降に書かれている種類やセルの集まりの名前は一般的ではないかもしれません。

53

3.4 周期型

周期型はある周期で同じ状態に戻るものをいう。

左から順に「ブリンカー（周期 2）」「ヒキガエル（周期 2）」「十五種競技（周

期 15）」「銀河（周期 8）」

3.5 移動型

移動型は一定のパターンを繰り返しながら移動していくものをいう。

上のセル（の集まり）はグライダーと呼ばれ、最も頻繁に現れる移動型である。

その外の移動型の例　左から順に「軽量級宇宙船」「中量級宇宙船」「重量級

宇宙船」

54

3.6 繁殖型

繁殖型は黒セルの数が（単調続増加である必要はないが）限りなく増え続

けるパターンである。

この代表例が上の「グライダーガン」で、周期的な動きをするが、30世代ご

とにグライダーを一台ずつ作り出し発射する。

他にも繁殖型はあるが、上 2つは比較的単純な繁殖型の初期状態で 10セルの

ものは最少数である。

そして「max」と呼ばれるものは最も速く成長し、平面を覆うように成長し

ていく。

3.7 ライフゲームのバリエーション

ライフゲームをヒントにしたり、応用したりして様々な発展版（?）のライ

フゲームを考えることができる。その例を幾つか書いてみる。（ただこれらの

例の中の多くはセル・オートマトンの範疇に属している。）

3.7.1 ルールを変える

ライフゲームでは周りに黒セル 2個又は 3個で維持し 3個で誕生するルー

ル（これをルール 23/3と書くことにする）だがそれを変えてみる。それぞれ

のルールに特有の周期型や移動型等がある。

55

例:ルール 245/3

左から三つは周期型で（順に周期 2、4、4）、一番右側は移動型である。

3.7.2 状態を増やす

ライフゲームではセルの状態は 2通りしかないがそれを変えて、「各黒セル

に生命力のような数字を与えて、生命力の高いセルは過酷な状況でもすぐに

は死なず、自分の生命力を消費する」といったルールも考えられる。

若しくは種類の違う生命（例えば青セルと赤セル）を考えれば 2人（以上）

で対戦ゲームのようなことができるかもしれない。

3.7.3 セルの形を変える

ライフゲームでは正方形が敷き詰められているが、正三角形や正六角形も

平面に敷き詰められる。それらをセルとして同じようなルールを考えられる。

更に言えば、正八角形と正方形を組み合わせて敷き詰める（一つの頂点に 2

つの正八角形と 1つの正方形を集める）ことも可能なのでこれをセルとして

も（正方形のセルと正八角形のセルでルールを変えるべきだが）可能だろう。

3.7.4 次元を変える

3次元空間を立方体（に限らず正四面体や正八面体）で埋め尽くしてその一

つ一つをセルとしても（手作業でセルの様子を追っていくのは難しいが）可

能である。勿論 4以上の次元でも可能。

4 あとがき

この記事を読んでくださりありがとうございました。

私にとっては初めての部誌で、初めての TEXでした。なので読みにくい所や

56

分かりにくい所、杜撰な所が多々あるかも知れません。内容に関しては、意

味のある数学的な考察（何をもって「意味がある」というのかも難しいです

が）もできず、単に「ライフゲームを紹介した」と言うような形になってし

まった気がします。やはり初めてだと言うのに取り掛かるのが遅かったと思

います。来年はこの反省を活かして良いものを書きたいです。

まあ、つまらない言い訳はここまでにして、この記事を読んでライフゲーム

で遊んでみたいと思った方は、インターネット上には沢山ライフゲームが遊

べるフリーソフトがあるので探してみてください（私は 2種類しか使ったこ

とが無いのでここで具体的にどれがオススメかは書けませんが）。

また TEXを使う時に、

『LATEX2ε美文書作成入門』（奥村晴彦 著　技術評論社）

ならびに先輩方の過去の記事を参考にさせて頂きました。

ライフゲームの様々なセルの集まりについては

Eric Weisstein’s Treasure Trove of the Life C.A.

（http://www.ericweisstein.com/encyclopedias/life/）

等のサイトを中心に参考にさせて頂きました。

最後にスペースが余ったので記事内で紹介した「max」の初期状態を書い

て終わりにしたいと思います。

57

楕円曲線暗号アルゴリズム

高校２年３組３８番 平野正浩

はじめに

灘校数学研究部にお越しいただきありがとうございます。この記事は、楕円曲線と

いう物を用いた暗号アルゴリズムにかんして書いてみました。研究が至らない部分

多々あり、読みづらい部分もあるかと思いますが了承願えたらなと思います。あと、

Cryptography(暗号)に関する内容です。その分野の基本的な定義をいちおうは書い

ておきますが、独自に勉強なさったほうがいいかと思います。

Introduction

楕円曲線暗号とは、1985年にKoblitzという人物とMillerという人物によって独立

に考え出された暗号アルゴリズムです。大体の公開鍵アルゴリズムがそうであるよう

に、楕円曲線暗号系も離散対数問題に安全性が依存しています。しかし、その後通称

MOV攻撃という離散対数問題に攻撃する手段がMOVという三人組によって考え出

されました。この方法は後に示す参考文献に詳しく載っているので参照してください。

58

1 暗号ことはじめ

ある文 P (plain text, 平文)という普通に意を解せる文書や、バイナリデータがあっ

たとします。これをだれが見ても読めないような文章にするという作業を暗号化す

るといいます。この暗号化された文章を暗号文といい、C(Complex text)で表します。

さらに、正規の利用者がこの C から P を求める作業を復号化といいます。そして、

第三者が暗号文を平文に変換する操作を解読といいます。さて、これぐらいが暗号と

いうものを理解するのに必要な最低限の知識です。まず、公開鍵暗号アルゴリズムの

概要から説明します。公開鍵暗号では、「暗号化の鍵」と「復号化の鍵」を分けます。

送信者は、「暗号化の鍵」を使ってメッセージを暗号化し、受信者は「復号化の鍵」を

使って暗号文を復号化します。

公開鍵暗号を理解するためには、「暗号化の鍵」と「復号化の鍵」をはっきりと区別

することが大切です。ここで、対称暗号で問題になった鍵配送問題を解決できている

ことがわかりますか？盗聴者は「暗号化の鍵」を持っていても「復号化の鍵」を持っ

ていなければ解読することができないからです。つまり、「暗号化の鍵」は暗号化の

ために送信者が使うもので、「復号化の鍵」は復号化のために受信者が使うものです。

公開鍵暗号では「暗号化の鍵」は一般に公開することができます。この鍵の事を公開

鍵 (public key)と呼びます。一方、「復号化の鍵」は絶対に公開してはいけません。こ

の鍵の事をプライベート鍵（秘密鍵, private key)と呼びます。そして、公開鍵とプ

ライベート鍵は、2本 1対になっているのでこの鍵の対の事を鍵ペアと呼びます。公

開鍵暗号アルゴリズムとは、この公開鍵と秘密鍵を出すのに使われるものの事です。

2 楕円曲線暗号

2.1 概要

有限体上定義された楕円曲線の点が群をなすことを利用した暗号を楕円曲線暗号と

いいます。上にも書きましたが、楕円曲線暗号の安全性は、この群の離散対数問題の

困難さに依存しています。のちにもこのことに関して詳しく述べます。

この楕円曲線上の離散対数問題の解を求めるための計算量が、有限体の大きさ logqの

指数関数オーダーになるのに対し、通常の有限体における離散対数問題や大きな合成

数の素因数分解問題は、準指数時間で解を求めることが可能です。

つまり、RSA暗号や ElGamal暗号と同等の安全性を実現するために必要な有限体の

大きさを、それに必要な大きさに比べて比較的小さくできます。たとえば、RSA暗

号では 1024ビット必要なところが、楕円曲線暗号では有限体の大きさを 160ビット

で抑えることができます。

公開鍵を秘密鍵の配送に用いた場合、1回のやり取りで必要な公開鍵の暗号化、復号

59

化には一部ロックで十分なので楕円曲線暗号はRSA暗号に比べて 10倍以上高速であ

ることが知られています。

2.2 ElGamal暗号

楕円曲線暗号は公開鍵暗号で用いられます。そこで、公開鍵暗号の最も初歩的な

ElGamal暗号を紹介したいと思います。離散対数問題とは、有限体における対数を求

める問題であり、素数 pに対して、y ≡ gx (mod p) なる関係式があるとき x以外

のすべてからこの xを求めるという問題です。gの位数が小さければ xに brute force

attackをすれば求まりますが gの位数が大きく、その位数の素因数に大きな素数が

含まれている場合 xを求めることは困難でありその計算量は logp の準指数関数オー

ダーとなります。ここで具体的な手順を説明します。

1. 大きな素数 pを生成する。但し、この pは攻撃に対して十分安全な素数とする)

2. 有限体 Fp の原始根を求める。

3. 乱数 x ∈ Zp − 1を生成し、y ≡ gx (mod p)により y ∈ Fp を得る。

4. g,y,pを公開鍵とし、xを秘密鍵とする。

秘密鍵:x ∈ Zp − 1 公開鍵:p, g ∈ Fp, y ≡ gx (mod p)

暗号化:

ElGamal暗号は、平文 1ブロックに対して、暗号文は 2ブロックとなるので、平分

mに対応する暗号文を c = c1, c2 と表すことにする。平文 mを暗号化して、暗号文

c = c1, c2を得るには公開鍵 g,y,pを用いて

c1 ≡ gk (mod p)c2 ≡ my

k (mod p)

を計算すればよい。ただし、kは暗号化に際して生成する乱数である。ここで乱数と

は擬似乱数といって完全な乱数ではないものの事を言います。まあ普段ではあまり意

識しなくてもいいのですが（笑）

復号化:

暗号文 c = c1, c2を復号化し、平文mを得るには秘密鍵 x,公開鍵 pを用いて、

m ≡c2cx1

(mod p)

を計算する。ここで正しく復号されることを確認しておきましょう。

c2cx1

≡myk

(gk)x≡

myk

yk≡ m (mod p)

こんな具合です。この後に紹介する楕円 ElGamal暗号はこれの key pairを楕円曲線

暗号で作成したものです。

60

2.3 有限体上の楕円曲線

本当は一般的にやるのが筋なのですが簡単に話を進めるため、有限体を素体とし、

素体 Fpの標数 pは、p 6= 2, 3とします。

（いや、これも本当は全部調べるのがいいんですが、時間が足りない感があり少々物

足りない記事になってしまいました。)

有限体上の楕円曲線 E/Fpは次の式で表されます。

y2 = x3 + ax + b, a, b ∈ Fp (1)

上の式を満たす Fに属する元 x, y ∈ Fp の組からなる点 (x, y)を有理点という。有理

点全体と無限遠点 O は次に示す加法において群をなします。但し、無限遠点はこの

群の単位元であり、射影平面上では (0:1:0）と表すことができます。つまり xy平面

上には存在しないが、xy平面上の任意のある点と無限遠点を通る直線は、y軸と平行

な直線となります。

楕円曲線の点と点の加法: 有理点 P = (x1, y1)とQ = (x2, y2)は次のように定義でき

ます。まず、有理点 P = (x1, y1)とQ = (x2, y2)を通る直線と楕円曲線との第３の交

点をP ∗Qとする。そして、この点P ∗Qと、ｘ軸に対して対称な点をP +Q = (x3, y3)

として、この点を点 P と点 Qの加算結果とします。

1. Qが無限遠点 (零点)Oの場合

P + Q = Q + P = P (2)

(Oは加法における単位元)

2. x2 ≡ x1 (mod p), y2 ≡ −y1 (mod p)の場合

P + Q = Q + P = O (3)

(この時、Q = −P と表す)

3. P ≠ Qかつ x1 6≡ x2 (mod p)7の場合 (すなわち、P と Qのｘ座標が異なる

場合)

点 P と点 Qを通る直線を l : y = mx + nとし、次の連立方程式を考える。

y2 = x3 + ax + b (4)

y = mx + n (5)

(5)を (4)に代入して整理すると

x3 − m2x2 + (a − 2mn)x + b − n2 = 0 (6)

61

という三次方程式が得られる。この三次方程式の三つの解が x1,x2,x3となるの

で、この方程式の左辺は次のように因数分解することができる。

x3 − m2x2 + (a − 2mn)x + b − n2 = (x − x1)(x − x2)(x − x3)

= x3 − (x1 + x2 + x3)x2 + (x1x2 + x2x3 + x3x1)x − x1x2x3

従って、両辺の x2の係数に着目すると

x3 = m2 − x1 − x2 (7)

となり、この式に点 P と点 Qを通る直線の傾きを代入すると

x3 =

(

y2 − y1x2 − x1

)2

− x1 − x2 (8)

が得られる。また、x3を (5)に代入すると以下の式が得られる。

x3 ≡

(

y2 − y1x2 − x1

)2

− x1 − x2 (mod p) (9)

y3 ≡

(

y2 − y1x2 − x1

)

(x1 − x3) − y1 (mod p) (10)

62

4. P = Qの場合

3.の場合は簡単に導くことができました。同じノリでいきましょう。点 P とQ

が異なる場合との差は、x1 = x2 であること、さらに直線の方程式の傾きが楕

円曲線の点 P における接線の傾きで与えられることである。ここで (1)を xで

偏微分すると、

2yϑy

ϑx= 3x2 + a (11)

となるので、点 P における接線の傾きmは

m =ϑy

ϑx=

3x21

+ a

2y1(12)

となり、これを (7)に代入すると以下の式が得られる。

x3 ≡

(

3x21

+ a

2y1

)2

− 2x1 (mod p) (13)

y3 ≡

(

3x21

+ a

2y1

)

(x1 − x3) − y1 (mod p) (14)

この場合は、2P=P+P と表す。

1.の場合、点 P と点 Oを結ぶ直線は、第三の点-P で楕円曲線と交わり、-P を x軸

に関して折り返すと点 P 自身となり P + O = P となる。また、2.の場合は点 P と

点-P を通る直線は、第三の点Oで曲線と交わる。Oを x軸に関して折り返すとO自

身となり、P + (−P ) = Oとなる。4.の場合は P において二重に交わる点は、P に

おける接線、まさにそれである。この直線は第三の点 P ∗P で交わり P ∗P を x軸に

関して折り返した点が P + P = 2P であり、この点 2P を点 Pの 2倍点という。さら

に、(k − 1)P + P = kP と記述し、kP を Pの k倍点と呼ぶ。

2.4 楕円ElGamal暗号

楕円曲線状の離散対数問題を解く困難さを利用した公開鍵暗号として楕円ElGamal

暗号があります。この暗号は、ElGamal暗号における、有限体の乗法群の演算を楕円

曲線の有理点がなす加法群の演算に置き換えたもので、key pairは次のようになりま

す。

秘密鍵:d

公開鍵:有限体 Fq上の楕円曲線 E/Fq : y2 = x3 + ax + b有理点 P, Q=dP ∈ E(Fq) こ

こで、点Qは点 P を d倍したものであり、P ,Qから dを求めることが楕円曲線上の

離散対数問題になっていることに注意してくださいね。（こんな言い方をするとすご

く直感的なイメージができていいですね）

63

暗号化:

平文に対応する楕円曲線上の有理点 Pm から暗号文 C = (C1, C2)への暗号化は適当

な乱数（もちろん擬似乱数… )を生成し、楕円曲線上の点の k倍算、および加算によ

り次のように行われる。

C1 = kP (15)

C2 = Pm + kQ (16)

復号化:

復号化は、ElGamal暗号の場合と同様の原理に基づいて次のように行います。

C2 − dC1 = Pm + kQ − d(kP ) = Pm + kQ − k(dP ) = Pm (17)

3 おわりに

ほんとは、もっともっと書きたかったのですが、諸制限がありほんとにさわりのさ

わり位しか触れることができませんでした。楕円曲線暗号はかなり奥が深い世界で今

もなお研究が日進月歩である学問です。こんな駄記事で一人でも興味を持っていただ

けたらなと祈っております。HPには余力があればもっと面白い事をあげておこうか

なと思っておりますが、いつになるかはわかりませんｗあまり期待しないでいてくだ

さい。

参考文献

[1] Bruse Schneier著, Applied Cryptography

[2] イアン・F・ブラケ,他 2人共著, 楕円曲線暗号

64

Column

さて、奇数ページで終わってしまったのでここで一つ小話を。

先ほど乱数と述べましたが、これも奥が深いのです。そのあたりの世界をちょっとの

ぞいてみましょう。

まず、乱数の性質を分類してみましょう。

• 無作為性

統計的に偏りがなく、でたらめな数列になっているということ。

• 予測不可能性

過去の数列から次の数を予測できないという性質。

• 再現不可能性

同じ数列を再現できないという性質。再現するためには数列そのものを保存し

ておく必要がある。

この三つの性質は下に行くほど厳しくなります。また、下にあるものを満たせば上に

あるものを満たします。ここでそれぞれに関してもう少し踏み込んでみましょう。

・無作為性

たとえば、1,2,3,4,5,6,7,8,9,0,1,2,3,4,5· · ·でも統計的に等しく分布されているので無

作為性があるといえます。また、一見でたらめに見えても数列に一個も 8が入ってい

なかったりした場合はそれは無作為性があるとはいえません。

・予測不可能性

これは、過去に出力した擬似乱数列を知られても、次に出力する擬似乱数を言い当て

ることはできない、というものです。seedを用いたアルゴリズムなんかはこれをもつ

といえますね。これを実装するのは他の暗号技術で行います。

・再現不可能性

上であげた seedを知られても再現するにはそのものを保存しておくしかないような

性質の事を言います。擬似乱数生成器はその名の通り、完全な乱数を作り出すことは

できません。

再現不可能性を持つ乱数は、周りの温度とかからのみ得られます。このような再現

不可能性を持つ乱数を「真の乱数」といいます。

こんな感じで乱数にも何種類かあるのですね。

65

平方和についての考察

高校 2年 4組 27番 関 典史

1 はじめに

この記事では、与えられた整数 a, b, nに対して ax2 + by2 = nを満たす整数 x, yは

存在するか、またそのような (x, y)の組はいくつあるか、という問題を扱います。

2 準備

必要な定義・定理を書いておきます。

定義 2.1 (二次体)

m ∈ Zは平方因子を持たないとするとき

x + y√

m(x, y ∈ Q)

の形の数全体の集合は体をなす。これを二次体といい、K(√

m)と表す。

有理数体 Qの中に Zがあるように、二次体に対しても「整数」を定義します。

定義 2.2 (二次体の整数)

Z係数の二次方程式

x2 + ax + b = 0

の解となるような数を二次体の整数という。

二次体の整数は次のように書けます。

定理 2.3

二次体K(√

m)の整数は、x, y ∈ Zとしてm ≡ 2, 3 (mod 4)のとき x + y

√m

m ≡ 1 (mod 4)のとき x + y√

m

2, x ≡ y (mod 2)

となる。

66

定義 2.4 (共役、ノルム)

二次体K(√

m)に属する 2数 α = x + y√

m, α = x − y√

m を互いに共役という。

N(α) = αα = x2 − my2と定め、これを αのノルムという。

定義 2.5

K(√

m)の整数 α, β について、α

βがK(

√m)の整数となるとき、αは β で割り切れ

るといい、β | αと書く。

定義 2.6 (単数)

K(√

m)の整数 ǫが N(ǫ) = ±1を満たす (すなわち ǫ | 1となる )とき、ǫを単数という。

定理 2.7 (基本単数)

m > 0のとき、K(√

m)には無数に単数があり、それらは一つの単数 ǫ0 によって次

の形に表される。

±ǫn0 (n ∈ Z)

このような単数 ǫ0 を基本単数という。

定理 2.8

m < 0, m 6= −1,−3のときK(√

m)の単数は ±1の 2個である。

また、K(i)の単数は±1,±iの4個、K(√−3)の単数は±1,±−1 +

√−3

2,±−1 −

√−3

2の 6個である。

定義 2.9 (同伴数)

K(√

m) の整数 α, β について、α

βが単数となるとき、α, β を互いに同伴数といい、

α ∼ βと書く。

定義 2.10 (素元)

K(√

m)の 0でも単数でもない整数 πについて、π | αβ ⇒ π | αまたはπ | β が成り立つとき、πをK(

√m)の素元という。

定義 2.11 (イデアル)

K(√

m)の整数からなる集合 Aが次の条件 (1), (2)を満たすとき、Aをイデアルとい

う。

(1) α, β ∈ A ⇒ α + β, α − β ∈ A(2) λ : K(

√m)の整数, α ∈ A ⇒ λα ∈ A

ただし、0のみからなる集合はイデアルでないとする。

67

定義 2.12

K(√

m)の整数α1, · · · , αnについて、集合 {λ1α1+· · ·+λnαn | λ1, · · · , λn : K(√

m)の

整数}はイデアルである。これをα1, · · · , αnで生成されるイデアルといい、(α1, · · · , αn)と表す。

K(√

m)の整数 αで生成されるイデアル、すなわち (α)の形のイデアルを単項イデア

ルという。

定理 2.13

(α) = (β) ⇔ αと β は同伴数

定理 2.14

任意のイデアルは (α1, · · · , αn)の形に表される。

定義 2.15 (イデアルの積)

イデアル A = (α1, · · · , αm)と B = (β1, · · · , βn)の積を、イデアル

AB = (α1β1, · · · , αµβν , · · · , αmβn)

で定義する。

すなわち、ABは

k∑

i=1

aibi (ai ∈ A, bi ∈ B)の形の数全体の集合である。

イデアル A, B, Cについて C = ABが成り立っているとき、C は Aまたは Bで割り

切れるという。

定義 2.16 (共役イデアル)

イデアル A = (α1, · · · , αn)に対して、A = (α1, · · · , αn)と定義し、これを Aの共役イデアルという。

定理 2.17

任意のイデアル Aに対し、ある n ∈ Nが存在し、AA = (n)となる。この正整数 nをイデアル Aのノルムといい、N(A) = nと書く。

定義 2.18 (素イデアル)

イデアル P (P 6= (1))が (1)と P 以外のイデアルで割り切れないとき、P を素イデアルという。

次の定理は非常に重要です。

定理 2.19 (イデアル論の基本定理)

(1)以外のイデアルは一意的に素イデアルの積に分解できる。

68

素イデアルとは Zにおける素数のようなもので、Zで素因数分解の一意性が成り立つ

ように、素イデアル分解の一意性が成り立つということです。

pを素数とし、二次体K(√

m)でのイデアル (p)の素イデアル分解を考えると、以下

が成り立ちます。

定義 2.20 (判別式)

二次体K(√

m)に対し

• m ≡ 2, 3 (mod 4)のとき d = 4m

• m ≡ 1 (mod 4)のとき d = m

により dを定め、この dをK(√

m)の判別式という。

定理 2.21

二次体K(√

m)において、素数 pは (p)の素イデアル分解によって以下の三種に分か

れる。

第一種

(

d

p

)

= 1なる奇素数 pについて1、(p) = PP , P 6= P, N(P ) = p

d ≡ 1 (mod 8)ならば (2) = PP , P 6= P , N(P ) = 2

第二種

(

d

p

)

= −1なる奇素数 pについて、(p) = P, N(P ) = p2

d ≡ 5 (mod 8)ならば (2) = P, N(P ) = 4

第三種 dの素因数 pについて、(p) = P 2, N(P ) = p

定義 2.22 (イデアルの類別)

二次体K(√

m)において、イデアルAの各数に、ある数 ρ (整数でなくてもよい )を

かけたときに、その積が全て整数であるならばそれらの積の集合はイデアルである。

このイデアルを ρAと表す。このように、二つのイデアル A, Bの間に

B = ρA

という関係があるとき、Aと Bは対等であるといい、A ∼ Bと書く。この対等という関係は同値関係であるので、これによってイデアルを類に分けること

ができる。単項イデアルは互いに対等であるので、単項イデアル全ての集合は一つの

類をなす。これを主類という。

1p : 奇素数, a 6≡ 0 (mod p) に対して、x2 ≡ a (mod p) なる x ∈ Zが存在するかしないかによって�a

p

�= 1,−1

とする。(Legendre 記号 )

69

定理 2.23

二次体K(√

m)のイデアルの類の数は有限である。

これをK(√

m)の類数という。

定理 2.24

二次体K(√

m)のイデアルの類全体の集合は群をなす。

証明

C1, C2を二つの類とする。C1, C2に属するある一定のイデアルを A1, A2とし、任意

のイデアルを B1, B2 とすれば、B1 = ρA1, B2 = σA2 より、B1B2 = ρσA1A2 とな

る。すなわち、B1B2はA1A2を含む一定の類C3に属する。このようにC1, C2によっ

て定まる類 C3 を、C3 = C1C2 と表すことにすると

• 任意の類 C1, C2, C3 に対して、(C1C2)C3 = C1(C2C3)

• 主類 E,任意の類 C に対して、EC = C

• 任意の類Cに対して、Cに属する各イデアルの共役イデアルは一つの類をなし、この類を C−1 と書くと CC−1 = E

となることが確かめられる。

証明終

これで準備は終わりです。

3 解の個数～有限個か無限個か～

ax2 + by2 = n (a, b, n ∈ Z, 6= 0)の Z解 (x, y)の個数が有限個か無限個かを考えます。

a, b, nを ak, bk, nk(k ∈ Z)に置き換えても同値なので、aと bは互いに素で、a > 0であるとしておきます。

次の定理が成り立ちます。

定理 3.1

ax2 + by2 = n (a, b, n ∈ Z, a > 0, b, n 6= 0, aと bは互いに素)の Z解 (x, y)の個数は、

(1) b > 0のとき有限個　

(2) b < 0かつ−abが平方数のとき有限個　(3) b < 0かつ−abが平方数でないとき 0個または無限個　である。

70

定理の証明に入る前に補題を一つ用意します。この補題は (3)の証明に用います。

補題 3.2

平方数でない任意の自然数mに対して、x2 −my2 = 1を満たす x, y ∈ Nが存在する。

証明略

二次体による証明や連分数展開による証明が知られています。

では定理の証明に入りましょう。

定理 3.1の証明

(1) a, b > 0より、ax2 + by2 > 0なので、n < 0のときは解なし。

n > 0のとき、b > 0より ax2 = n− by2 ≤ nなので |x| ≤√

n

aとなり、同様に a > 0

より |y| ≤√

n

bとなる。したがって解は有限個。

(2) aと bは互いに素でかつ −abが平方数なので、aと −bはともに平方数。a = p2,−b = q2 (p, q ∈ N)とおくと、n = ax2 + by2 = (px + qy)(px − qy)なので、組 (px + qy, px − qy)として有り得るのは有限通り。px + qy = r, px − qy = sのとき、x = r + s

2p, y =

r − s2q

と定まるので、解は有限個。

(3) ax2 + by2 = nが解を持つとき、無限個の解があることを示せばよい。

(x0, y0)が ax2 + by2 = nの Z解であるとする。x0, y0 ≥ 0としてよい。

ax20+by20 = n ⇔ (ax0)2+aby20 = an ⇔ (ax0+y0

√−ab)(ax0−y0

√−ab) = an · · · (∗)

補題 3.2より、t2 + abu2 = 1なる t, u ∈ N (t > 1)がとれる。このとき (t + u

√−ab)(t − u

√−ab) = 1 · · · (∗∗)

(∗)と (∗∗)を辺々かけて、(ax0 + y0

√−ab)(t + u

√−ab)(ax0 − y0

√−ab)(t − u

√−ab) = an

⇔(

atx0 − abuy0 + (aux0 + ty0)√−ab

) (

atx0 − abuy0 − (aux0 + ty0)√−ab

)

= an

⇔ (a(tx0 − buy0))2 + ab(aux0 + ty0)2 = an⇔ a(tx0 − buy0)2 + b(aux0 + ty0)2 = nよって (tx0 − buy0, aux0 + ty0)も ax2 + by2 = nの Z解である。したがって、(xk+1, yk+1) = (txk − buyk, auxk + tyk) (k = 0, 1, · · · )により (xm, ym)を定めると、全てのmに対して (xm, ym)は ax

2 + by2 = nの Z解である。

また、xk, yk ≥ 0のとき、n 6= 0より xk = yk = 0となることはないので、t > 1よりxk+1 = txk − buyk > xk, yk+1 = auxk + tyk > ykよって (xm, ym)は全て異なるので、解が無限個あることが示された。

証明終

71

4 解を持つ条件と解の個数

ax2 + by2 = nが解を持つ条件と解の個数を、いろいろな場合について調べていき

ます。以下、aと bは互いに素で、a, bはどちらも平方因子を持たないとします。

4.1 a = 1のときへの帰着

次が成り立ちます。

定理 4.1

aと bが互いに素で、a, bが平方因子を持たないとき、ax2 + by2 = nの解の個数は

x2 + aby2 = anの解の個数と等しい。

証明

at2 + bu2 = n (t, u ∈ Z) が成り立つとすると、(at)2 + abu2 = an より (at, u)はx2 + aby2 = anの解である。

逆に、v2+abw2 = an (v, w ∈ Z)が成り立つとすると、v2は aの倍数であり、aは平方因子を持たないので、vは aの倍数。また、このとき a

(v

a

)2

+bw2 =1

a(v2+abw2) = n

となるので、(v

a, w

)

は ax2 + by2 = nの解である。

以上より、ax2 + by2 = nの解と x2 + aby2 = anの解は (t, u) ↔ (at, u)により一対一対応する。よって示された。

証明終

この定理により、x2 −my2 = n (m ∈ Z, mは平方因子を持たない)について調べればよいことが分かります。ここから先は、最初に準備した二次体論を使います。

x2 −my2 = n ⇔ (x + y√

m)(x− y√

m) = nより、αα = nとなるようなK(√

m)の

整数 αで、α = x + y√

m (x, y ∈ Z)の形であるものを求めればよいことになります。この記事ではK(

√m)の類数が 1の場合と 2の場合を考えます。

4.2 x2 − my2 = nについて～K(√

m)の類数が 1の場合～

K(√

m)の類数が 1、すなわちイデアルが全て単項イデアルであるときを考えます。

このとき、(α)が素イデアル⇔ αが素元 が成り立ちます。したがって、類数 1の二次体では素元分解の一意性が成り立ちます。

例えば、K(i) (類数 1)において、8 + i = (2 − i)(3 + 2i)は素元分解です。8 + i =(1 + 2i)(2 − 3i)も素元分解ですが、2 − i ∼ 1 + 2i, 3 + 2i ∼ 2 − 3iとなっています。このように同伴数で置き換えた分解は同じと考えると、一意性が成り立つわけです。

72

4.2.1 m < 0のとき

m < 0のとき、K(√

m)の類数が 1であるようなmは

m = −1,−2,−3,−7,−11,−19,−43,−67,−163

の 9個のみであることが知られています。

これらのmの値について、x2 − my2 = nを考えていきましょう。n < 0のとき明らかに解はないので、以下 n > 0とします。

定理 4.2

x2 + y2 = nが Z解を持つための必要十分条件は、nの素因数分解

n = 2ape11 · · · pekk qf11 · · · qfll (p1, · · · , pk ≡ 1 (mod 4), q1, · · · , ql ≡ 3 (mod 4))

において f1, · · · , fl がすべて偶数であることであり、このとき解の個数は 4(e1 +1) · · · (ek + 1)個である。

証明

K(i)の整数は x + yi(x, y ∈ Z)なので、x2 + y2 = nが解を持つことは αα = nなるK(i)の整数 αが存在することと同値。

p :奇素数に対して、(−1

p

)

= 1 ⇔ p ≡ 1 (mod 4),(−1

p

)

= −1 ⇔ p ≡ 3 (mod 4)なので (このことの証明は省略 )定理 2.21より、K(i)において

第一種 : p ≡ 1 (mod 4)なる奇素数 pについて、p = ππ (π :素元)第二種 : p ≡ 3 (mod 4)なる奇素数 pについて、pは素元第三種 : p = 2について、2 = (1 + i)(1 − i) ∼ (1 + i)2

となる。

したがって nを素元分解すると、

n = (1 + i)a(1 − i)aπe11 π1e1 · · ·πekk πkekqf11 · · · qfll

∼ (1 + i)2aπe11 π1e1 · · ·πekk πkekqf11 · · · q

fll

となる。

よって、αα = nなるK(i)の整数 αが存在するとき、β | α ⇔ β | αに注意して

• 1 + i ∼ 1 − iより ord1+iα = ord1+iαであり2、ord1+iα + ord1+iα = 2aなので、ord1+iα = ord1+iα = a · · · (1)

2α が π で最大 N 回割れるとき ordπα = N と書く。( オーダー )

73

• j = 1, · · · , kについて、ordπj α = ordπj α, ordπjα+ordπjα = ejより、ordπjα+ordπj α = ej · · · (2)

• r = 1, · · · , l について、ordqrα = ordqrα より、fr = ordqrα + ordqrα =2ordqrα · · · (3)

となる。(3)より f1, · · · , fl はすべて偶数である。逆に f1, · · · , flがすべて偶数であるとき

αα = n ⇔ α ∼ (1 + i)aπt11 π1e1−t1 · · ·πtkk πkek−tkqf12

1 · · · qfl2

l (t1, · · · , tk ∈ Z, 0 ≤ tj ≤ ej)

となる。(⇒: (1), (2), (3)より ,⇐: K(i)の単数が ±1,±iであることより )0 ≤ tj ≤ ej より t1, · · · tk のとり方は (e1 + 1) · · · (ek + 1)通りで、素元分解の一意性より (e1 + 1) · · · (ek + 1)個の (1 + i)aπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l はどの 2つ

も互いに同伴数でない。

K(i)の単数は 4個あるので、αα = nを満たす αの個数は 4(e1 + 1) · · · (ek + 1)個。よって解の個数は 4(e1 + 1) · · · (ek + 1)個である。以上より示された。

証明終

以下の証明で、この定理 4.2の証明と同様な部分はとばして書くことがあります。

定理 4.3

x2 + 2y2 = nが Z解を持つための必要十分条件は、nの素因数分解

n = 2ape11 · · · pekk qf11 · · · qfll (p1, · · · , pk ≡ 1, 3 (mod 8), q1, · · · , ql ≡ 5, 7 (mod 8))

において f1, · · · , fl がすべて偶数であることであり、このとき解の個数は 2(e1 +1) · · · (ek + 1)個である。

証明

K(√−2) の整数は x + y

√−2(x, y ∈ Z) なので、x2 + 2y2 = n が解を持つことは

αα = nなるK(√−2)の整数 αが存在することと同値。

定理 2.21より、K(√−2)において

第一種 : p ≡ 1, 3 (mod 8)なる奇素数 pについて、p = ππ (π :素元)第二種 : p ≡ 5, 7 (mod 8)なる奇素数 pについて、pは素元第三種 : p = 2について、2 = (

√−2)(−

√−2) ∼ (

√−2)2

となる。

したがって nを素元分解すると、

n = (√−2)a(−

√−2)aπe11 π1e1 · · ·πekk πkekq

f11 · · · qfll

∼ (√−2)2aπe11 π1e1 · · ·πekk πkekq

f11 · · · qfll

74

となる。

よって、αα = nなるK(√−2)の整数 αが存在するとき f1, · · · , flはすべて偶数であ

る。

逆に f1, · · · , flがすべて偶数であるとする。このとき

αα = n ⇔ α ∼ (√−2)aπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l (t1, · · · , tk ∈ Z, 0 ≤ tj ≤ ej)

となる。

t1, · · · , tkのとり方は (e1+1) · · · (ek+1)通りで、K(√−2)の単数は2個あるので、αα =

nを満たす αの個数は 2(e1 +1) · · · (ek +1)個。よって解の個数は 2(e1 +1) · · · (ek +1)個である。

以上より示された。

証明終

定理 4.4

x2 + 3y2 = nが Z解を持つための必要十分条件は、nの素因数分解

n = 3ape11 · · · pekk qf11 · · · q

fll (p1, · · · , pk ≡ 1 (mod 3), q1, · · · , ql ≡ 2 (mod 3))

において f1, · · · , flがすべて偶数であることであり、このとき解の個数は nが奇数ならば 2(e1 + 1) · · · (ek + 1)個、nが偶数ならば 6(e1 + 1) · · · (ek + 1)個である。

証明

K(√−3)の整数は x + y

√−3

2(x ≡ y (mod 2))なので、x2 + 3y2 = nが解を持つこ

とは、αα = nなるK(√−3)の整数 αであって α = x + y

√−3 (x, y ∈ Z)の形であ

るものが存在することと同値。

定理 2.21より、K(√−3)において

第一種 : p ≡ 1 (mod 3)なる奇素数 pについて、p = ππ (π :素元)第二種 : p ≡ 2 (mod 3)なる奇素数 pと p = 2について、pは素元第三種 : p = 3について、3 = (

√−3)(−

√−3) ∼ (

√−3)2

となる。

したがって nを素元分解すると、

n = (√−3)a(−

√−3)aπe11 π1e1 · · ·πekk πkekq

f11 · · · qfll

∼ (√−3)2aπe11 π1e1 · · ·πekk πkekq

f11 · · · qfll

となる。

よって、αα = nなるK(√−3)の整数 αが存在するとき f1, · · · , flはすべて偶数であ

る。

75

逆に f1, · · · , flがすべて偶数であるとする。このとき　

αα = n ⇔ α ∼ (√−3)aπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l (t1, · · · , tk ∈ Z, 0 ≤ tj ≤ ej)

となる。t1, · · · , tk のとり方は (e1 + 1) · · · (ek + 1)通りある。

ここで、K(√−3)の単数は±1,±−1 +

√−3

2,±−1 −

√−3

2の6個なので、

x + y√−3

2(x ≡

y (mod 2))の同伴数は

x + y√−3

2,−x − 3y + (x − y)

√−3

4,−x + 3y − (x + y)

√−3

4,

−x − y√−3

2,x + 3y − (x − y)

√−3

4,x − 3y + (x + y)

√−3

4

の 6個である。

x ≡ y (mod 2)より、(x, y)はmod 4で (1, 1), (1, 3), (3, 1), (3, 3), (0, 0), (0, 2), (2, 0), (2, 2)のいずれかであり

• (x, y)が mod 4で (1, 1), (1, 3), (3, 1), (3, 3), (0, 2), (2, 0)のとき、x2 + 3y2 ≡ 4(mod 8)より、上の 6個の数のノルム

x2 + 3y2

4は奇数である。また、このとき

上の 6個の数のうち x + y√−3 (x, y ∈ Z)の形のものは 2個。

• (x, y)が mod 4で (0, 0), (2, 2)のとき、x2 + 3y2 ≡ 0 (mod 8)より、上の 6個の数のノルム

x2 + 3y2

4は偶数である。また、このとき上の 6個の数すべてが

x + y√−3 (x, y ∈ Z)の形である。

したがって、αα = n なる K(√−3) の整数 α であって α = x + y

√−3 (x, y ∈ Z)

の形であるものの個数は、nが奇数のとき 2(e1 + 1) · · · (ek + 1)個、nが偶数のとき6(e1 + 1) · · · (ek + 1)個である。よって解の個数は nが奇数のとき 2(e1 + 1) · · · (ek + 1)個、nが偶数のとき 6(e1 +1) · · · (ek + 1)個である。以上より示された。

証明終

定理 4.5

x2 + 7y2 = nが Z解を持つための必要十分条件は、nの素因数分解

n = 2a7bpe11 · · · pekk qf11 · · · q

fll (p1, · · · , pk ≡ 1, 2, 4 (mod 7), q1, · · · , ql ≡ 3, 5, 6 (mod 7))

において a 6= 1かつ f1, · · · , flがすべて偶数であることであり、このとき解の個数はa = 0ならば 2(e1 + 1) · · · (ek + 1)個、a ≥ 2ならば 2(a− 1)(e1 + 1) · · · (ek + 1)個である。

76

証明

K(√−7)の整数は x + y

√−7

2(x ≡ y (mod 2))なので、x2 + 7y2 = nが解を持つこ

とは、αα = nなるK(√−7)の整数 αであって α = x + y

√−7 (x, y ∈ Z)の形であ

るものが存在することと同値。

定理 2.21より、K(√−7)において

第一種 : p ≡ 1, 2, 4 (mod 7)なる奇素数 pと p = 2について、p = ππ (π :素元)第二種 : p ≡ 3, 5, 6 (mod 7)なる奇素数 pについて、pは素元第三種 : p = 7について、7 = (

√−7)(−

√−7) ∼ (

√−7)2

となる。

2は第一種の素数で、2 =1 +

√−7

2· 1 −

√−7

2と素元分解される。

したがって nを素元分解すると、

n =

(

1 +√−7

2

)a (1 −

√−7

2

)a

(√−7)b(−

√−7)bπe11 π1e1 · · ·πekk πkekq

f11 · · · qfll

∼(

1 +√−7

2

)a (1 −

√−7

2

)a

(√−7)2bπe11 π1e1 · · ·πekk πkekq

f11 · · · q

fll

となる。

よって、αα = nなるK(√−7)の整数 αが存在するとき f1, · · · , flはすべて偶数であ

る。

逆に f1, · · · , flがすべて偶数であるとする。このとき　αα = n

⇔ α = ±(

1 +√−7

2

)t (1 −

√−7

2

)a−t

(√−7)bπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l

(t, t1, · · · , tk ∈ Z, 0 ≤ t ≤ a, 0 ≤ tj ≤ ej) となる。

α = ±(

1 +√−7

2

)t (1 −

√−7

2

)a−t

(√−7)bπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l ,

β = (√−7)bπt11 π1e1−t1 · · ·πtkk πkek−tkq

f12

1 · · · qfl2

l とおく。

ββ = 7bpe11 · · · pekk qf11 · · · q

fll より ββ は奇数。

β =x + y

√−7

2(x ≡ y (mod 2))と書けるが、x, yが奇数であるとすると x2+7y2 ≡ 0

(mod 8)より ββ =x2 + 7y2

4は偶数となり矛盾するので、x, yは偶数。

よって β = u + v√−7 (u, v ∈ Z)の形である。

ββ = u2 + 7v2 が奇数なので u, vはどちらか一方が奇数、もう一方が偶数である。

a = 0のとき、α = ±β より α = x + y√−7 (x, y ∈ Z)の形で、t1, · · · , tk のとり方よ

り αは 2(e1 + 1) · · · (ek + 1)個あるので、解の個数は 2(e1 + 1) · · · (ek + 1)個。以下 a ≥ 1とする。(

1 +√−7

2

)r

(r ∈ N)が x + y√−7

2(x, y : 奇数, x ≡ y (mod 4))の形であることを

rに関する数学的帰納法により示す。

77

(1) r = 1のとき明らか。

(2) r = j のとき成り立つと仮定する。(

1 +√−7

2

)j

=x + y

√−7

2とすると、(x, y)はmod 4で (1, 1), (3, 3)のいずれか。

(

1 +√−7

2

)j+1

=

(

1 +√−7

2

) (

x + y√−7

2

)

=x − 7y + (x + y)

√−7

4=

x−7y2

+ x+y2

√−7

2

であり、(x, y)がmod 4で (1, 1), (3, 3)のいずれかであるので、x − 7y

2,x + y

2はとも

に奇数。

またx − 7y

2− x + y

2= −4y ≡ 0 (mod 4)より x − 7y

2≡ x + y

2(mod 4)

よって r = j + 1のときも成り立つ。

(1), (2)より示された。

同様にして、

(

1 −√−7

2

)r

(r ∈ N)は x + y√−7

2(x, y : 奇数, x ≡ −y (mod 4))の

形である。

したがって

• t = 0, aのときα = ±(

x + y√−7

2

)

(u+v√−7) = ±xu − 7yv + (xv + yu)

√−7

2

となり、x, y, u, vの偶奇より αはx + y

√−7

2(x, y :奇数)の形である。

• 1 ≤ t ≤ a−1のとき(

1 +√−7

2

)t (1 −

√−7

2

)a−t

=x + y

√−7

2·x

′ + y′√−7

2=

xx′ − 7yy′ + (xy′ + x′y)√−7

4となり、x, y, x′, y′ :奇数, x ≡ y, x′ ≡ −y′ (mod 4)

より

(

1 +√−7

2

)t (1 −

√−7

2

)a−t

は x+y√−7 (x, y ∈ Z)の形であるので、α

は x + y√−7 (x, y ∈ Z)の形である。

a = 1のとき、t = 0, 1なので α = x + y√−7 (x, y ∈ Z)となる αは存在しない。

a ≥ 2のとき、α = x + y√−7 (x, y ∈ Z)となるのは 1 ≤ t ≤ a− 1のときで、このと

き t, t1, · · · , tk のとり方より αの個数は 2(a − 1)(e1 + 1) · · · (ek + 1)個。よって解の個数は 2(a − 1)(e1 + 1) · · · (ek + 1)個である。以上より示された。

証明終

m = −11,−19,−43,−67,−163のとき、K(√

m)の整数はx + y

√m

2(x ≡ y (mod 2))

です。

K(√

m)において、第一種の素数 pは p = ππと素元分解されますが、この分解におい

て π = x + y√

m (x, y ∈ Z)であるときすなわち p = x2 −my2となるような x, y ∈ Zが存在するとき、pを良い素数ということにします。(これは筆者の造語です。他で

は通用しません。)

78

定理 4.6

m = −11,−19,−43,−67,−163とする。x2 − my2 = nが Z解を持つための必要十分条件は、nの素因数分解n = pe11 · · · p

ejj p

ej+1j+1 · · · pekk q

f11 · · · qfll (−m)a (p1, · · · , pj : 良い素数でない第一種の素

数, pj+1, · · · , pk :良い素数, q1, · · · , ql :第二種の素数)において、[nが偶数かつ f1, · · · , flがすべて偶数]または [nが奇数かつ f1, · · · , flがすべて偶数かつ e1 + · · ·+ ej ≥ 2]であることである。

定理の証明の前に補題を一つ用意します。

補題 4.7

m ≡ 1 (mod 4)とする。x1, y1, x2, y2が奇数のとき

x1 + y1√

m

2· x2 + y2

√m

2,x1 + y1

√m

2· x2 − y2

√m

2

のどちらか一方がx + y

√m

2(x, y :奇数)の形で、もう一方が x + y

√m (x, y ∈ Z)の

形である。

証明x1 + y1

√m

2· x2 + y2

√m

2=

x1x2 + my1y2 + (x1y2 + y1x2)√

m

4,

x1 + y1√

m

2· x2 − y2

√m

2=

x1x2 − my1y2 − (x1y2 − y1x2)√

m

4x1x2, y1y2, x1y2, y1x2はすべて奇数で、(x1x2)(y1y2) = (x1y2)(y1x2)なので、

(x1x2, y1y2, x1y2, y1x2)はmod 4で (1, 1, 1, 1), (1, 1, 3, 3), (1, 3, 1, 3), (1, 3, 3, 1), (3, 1, 1, 3),

(3, 1, 3, 1), (3, 3, 1, 1), (3, 3, 3, 3)のいずれか。

それぞれの場合について分子をmod 4でみることにより示される。

証明終

定理 4.6の証明

K(√

m)の整数はx + y

√m

2(x ≡ y (mod 2))なので、x2 −my2 = nが解を持つこと

は、αα = nなるK(√

m)の整数 αであって α = x + y√

m (x, y ∈ Z)の形であるものが存在することと同値。

nの素元分解は　

n = πe11 π1e1 · · ·πekk πkekq

f11 · · · q

fll (

√m)a(−

√m)a

∼ πe11 π1e1 · · ·πekk πkekqf11 · · · qfll (

√m)2a

である。

よって、αα = nなるK(√

m)の整数 αが存在するとき f1, · · · , fl はすべて偶数であ

79

る。

逆に f1, · · · , flがすべて偶数であるとする。このとき　αα = n

⇔ α = ±πt11 π1e1−t1 · · ·πtkk πkek−tkqf12

1 · · · qfl2

l (√

m)a (t1, · · · , tk ∈ Z, 0 ≤ ti ≤ ei) となる。

α = ±πt11 π1e1−t1 · · ·πtkk πkek−tkqf12

1 · · · qfl2

l (√

m)a,

β = πt11 π1e1−t1 · · ·πtjj πjej−tj ,

γ = ±πtj+1j+1 πj+1ej+1−tj+1 · · ·πtkk πkek−tkqf12

1 · · · qfl2

l (√

m)a とする。

πj+1, · · · , πkはすべてx+y√

m (x, y ∈ Z)の形であるので、γ = X+Y√

m (X, Y ∈ Z)と書ける。

n = ααが偶数のとき、α =x + y

√m

2(x, y :奇数)であるとすると、m ≡ 5 (mod 8)

より αα =x2 − my2

4は奇数となり矛盾するので、α = x + y

√m (x, y ∈ Z)の形であ

る。よって x2 − my2 = nは解を持つ。n = αα が奇数のとき、(ββ)(γγ) = αα = nより γγ = X2 − mY 2 は奇数なので、X, Y はどちらか一方が奇数、もう一方が偶数である。

e1+· · ·+ej = 1すなわち j = 1, e1 = 1のとき、t1 = 0, 1であり、β =x + y

√m

2(x, y :

奇数)となるので、α = βγ =xX + myY + (xY + yX)

√m

2となり、x, y, X, Y の偶

奇より αはx + y

√m

2(x, y :奇数)の形である。よって x2 − my2 = nは解を持たな

い。

e1 + · · ·+ ej ≥ 2のとき x2 − my2 = nが解を持つことを示す。まず、e1 + · · · + ej ≥ 1のとき、πt11 π1e1−t1 · · ·π

tjj πj

ej−tj がx + y

√m

2(x, y : 奇数)

の形になるような t1, · · · , tj がとれることを e1 + · · ·+ ej に関する数学的帰納法で示す。

(1) e1 + · · · + ej = 1のとき　このとき j = 1, e1 = 1で、π1 は

x + y√

m

2(x, y : 奇数)の形なので、t1 = 1とすれ

ばよい。

(2) e1 + · · · + ej = s − 1のとき成り立つと仮定する。e1 + · · ·+ ej = sのとき、e1 + · · ·+ ej−1 + (ej − 1) = s− 1なので、帰納法の仮定より πt11 π1

e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1πtjj πj

ej−1−tj がx + y

√m

2(x, y : 奇数)の形とな

るような t1, · · · , tj がとれる。πj は

x + y√

m

2(x, y :奇数)の形なので、補題 4.7より

πt11 π1e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1π

tjj πj

ej−1−tj πj,

πt11 π1e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1π

tjj πj

ej−1−tj πj

80

のどちらかはx + y

√m

2(x, y :奇数)の形である。

よって e1 + · · · + ej = sのときも成り立つ。(1), (2)より示された。

e1 + · · ·+ ej ≥ 2のとき、e1 + · · ·+ ej−1 + (ej − 1) ≥ 1なので

πt11 π1e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1π

tjj πj

ej−1−tj

がx + y

√m

2(x, y :奇数)の形になるような t1, · · · , tj がとれる。

πj はx + y

√m

2(x, y :奇数)の形なので、補題 4.7より

πt11 π1e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1π

tjj πj

ej−1−tj πj,

πt11 π1e1−t1 · · ·πtj−1j−1 πj−1ej−1−tj−1π

tjj πj

ej−1−tj πj

のどちらかは x + y√

m (x, y ∈ Z)の形である。すなわち βが x + y√

m (x, y ∈ Z)の形になるような t1, · · · , tj がとれる。したがって、αα = nなる αであって α = x + y

√m (x, y ∈ Z)の形であるものが存

在する。よって x2 − my2 = nは解を持つ。

証明終

これでm < 0のときは終わりです。

4.2.2 m > 0のとき

m > 0のとき、定理 3.1より、x2 − my2 = nが解を持つならばそれは無限個あります。解を持つ条件を調べましょう。

m ≡ 2, 3 (mod 4)のとき、K(√

m)の整数は x + y√

m (x, y ∈ Z)で、次が成り立ちます。

定理 4.8

m ≡ 2, 3 (mod 4)とし、K(√

m)の基本単数を ǫ0 とする。

nの素因数分解を n = pe11 · · · pejj q

f11 · · · qfkk r

g11 · · · rgll (p1, · · · , pj : 第一種, q1, · · · , qk :

第二種, r1, · · · , rl :第三種) とすると　

• N(ǫ0) = 1のとき x2 − my2 = n, x2 − my2 = −nのどちらか一方のみが Z解を持つ⇔ f1, · · · , fk がすべて偶数

• N(ǫ0) = −1のとき x2 − my2 = n, x2 − my2 = −nがどちらも Z解を持つ⇔ f1, · · · , fk がすべて偶数

81

が成り立つ。

証明

K(√

m)の整数は x+y√

m (x, y ∈ Z)なので、x2−my2 = nが解を持つことはαα = nなるK(

√m)の整数 αが存在することと同値。

第一種の素数 pは p = ǫππ (ǫ :単数, π :素元)と書けて、N(π) = ±pなので p = ±ππである。

第三種の素数 pは p = ǫπ2 (ǫ :単数, π :素元)と書けて、N(π) = ±pなので p = ±ππである。

よって、nの素元分解は　

n = ±πe11 π1e1 · · ·πejj πj

ej qf11 · · · qfkk ρ

g11 ρ1

g1 · · ·ρgll ρlgl

と書ける。

したがって、αα = ±nなるK(√

m)の整数 αが存在するとき f1, · · · , fk は偶数である。

逆に f1, · · · , fk が偶数であるとする。このとき、αα = ±nならば

α = ǫπt11 π1e1−t1 · · ·πtjj πjej−tj q

f12

1 · · · qfk2

k ρu11 ρ1

g1−u1 · · ·ρull ρlgl−ul (ǫ :単数)

であり

αα = ǫǫπe11 π1e1 · · ·πejj πjej q

f11 · · · q

fkk ρ

g11 ρ1

g1 · · ·ρgll ρlgl

である。

N(ǫ0) = 1のとき、ǫǫ = ǫN0 ǫ0

N = (ǫ0ǫ0)N = 1より

αα = πe11 π1e1 · · ·πejj πjej q

f11 · ·