7 : 15 平方剰余の相互法則

← 7‒14 p↑ もくじ i 7‒16 n →

平方剰余へいほうじょうよの相互法則

2003年 3月26日
記事ID d30326

平方剰余へいほうじょうよというのは難しそうな名前だが、 早い話が「平方数」のことだ。 ふつうの整数で 4, 9, 16, 25, ... などは平方数(ある整数の二乗)だが、3, 6, 14, 23 などは平方数でない(ある整数の二乗にならない)。

7を法とする世界で考えよう。7を法とすると、
02 = 0 ≡ 0
12 = 1 ≡ 1
22 = 4 ≡ 4
32 = 9 ≡ 2 (9を7で割ると2余る)
42 = 16 ≡ 2 (16を7で割ると2余る)
52 = 25 ≡ 4 (25を7で割ると4余る)
62 = 36 ≡ 1 (36を7で割ると1余る)
となっているので、この世界では、0, 1, 2, 4 が平方数だ。 また、3, 5, 6 は平方数でない。「7を法とする平方数」「7を法とする平方数でない数」のことを、 「7の平方剰余」「7の平方非剰余」というのだが、言葉遣いが難しいと分かりにくくなるので、ここでは「平方数」で通す。

以下で説明する平方剰余の相互法則は、古典的整数論においては「基本」であると同時に「数の神秘」であり、ひとつの山場ともなっている。 イデアル論の立場からは別に神秘的でなく透明に理解することができるので、二次体を導入してから平方剰余の相互法則に進むのが現代的かもしれない。 しかし、平方剰余の相互法則の意味そのものは中学生にも理解できる。 巨大素数を扱う暗号学の立場からは、相互法則はヤコビ記号を使うソロベイ・ストラッセン・テストの基礎となっている。 確率的素数判定であるから、このテストをすりぬける「オイラー擬素数」の概念も生じる。

RSA暗号系から派生したネタとして、 フェルマーの小定理擬素数ラビン・ミラーのテストと強擬素数についてすでに書いた。 これらは暗号システムそのものというより「どうやって暗号に使う巨大素数を用意するのか」という下準備のような話だった。 話のついでなので、擬素数つながりで、ソロベイ・ストラッセン・テストとオイラー擬素数にもふれよう。 そのため、今回は平方剰余の相互法則を導入しておく。次回ルジャンドル記号とヤコビ記号を導入してオイラー擬素数まで行く予定だ。 なお、ここでは具体例の観察だけで証明はつけないので、詳しくは将来、自分で勉強してほしい。

ある数が平方数であるかないか

上でみたように、7を法とすると、0, 1, 2, 4 は平方数、3, 5, 6 は平方数でない。このことを次のように略記しよう:
0 R 7
1 R 7
2 R 7
4 R 7
3 N 7
5 N 7
6 N 7

a R b とは x2≡a (mod b) を満たす x が存在するということであり、 a N b とは x2≡a (mod b) に解がないことを言っている。

問題: 17 R 13 か?
解答: はい。mod 13 では 17≡4 だから x2≡4 (mod 13) に解があるか考える。2を二乗すれば4なので解がある。22 = 4 ≡17 (mod 13)
問題: 13 R 17 か?
解答: はい。82 = 64 ≡ 13 (mod 17)(64を17で割ると3余り13なので)

第一の例から分かるように、13を法として4が平方数か?ということと17が平方数か?ということは、同じ意味になる。 4≡17 (mod 13) だからだ。つまりAが平方数かどうか?と尋ねているとき、実際にはAという特定の数について尋ねているというより、 Aと合同なすべての数から成る集合(剰余類)について尋ねている、と考えても良い。

問題: 6は17を法として平方数か? 言い換えれば 6 R 17 か、それとも 6 N 17 か?
ちからまかせにやるには、全部の可能性をかたっぱしからチェックすれば良い。
02 ≡0
12 ≡1
22 ≡4
32 ≡9
42 ≡16
52 ≡8
62 ≡2
72 ≡15
82 ≡13
92 ≡13
102 ≡15
112 ≡2
122 ≡8
132 ≡16
142 ≡9
152 ≡4
162 ≡1
……17を法とする世界では何を平方しても6にはならないことが分かる。したがって答は「いいえ」だ。6 N 17 である。

ところで、さらによく観察すると、この場合、1の平方と16の平方は等しく、2の平方と15の平方は等しく……以下同様に、 nの平方と(17-n)の平方は等しくなっている注1。これは当たり前のことで、
(17-n)2 = 172 - 2·17·n + n2 ……①
の右辺第一項、第二項は17で割り切れるので、17で割った余りという観点ではこれらは0に等しく、
(17-n)2 ≡ n2 (mod 17)
だからだ。ということは、1の二乗、2の二乗……と計算していくと、半分の17/2より先では新しいものは出ない。 言い換えれば、上の計算結果では、0は別にして、右辺には同じ数がぜんぶ2回ずつ現れる。 したがって、17を法とする世界では、すべての元が平方数ということは不可能で、0を除外した16個の要素のうち半分が平方数、 残りの半分が非平方数だ注2。実際、上の結果から、0は別にして、1, 2, 4, 8, 9, 13, 15, 16 の8個が平方数である。 法が17でなくても①と同様の式は成り立つので、かたっぱしから調べるにしても法の半分までで止めて良い。

注1: 正確な用語を使えば「等しい」のではなく「合同」だが、わざとぼかしている。

注2: 平方と非平方の個数が半々になることをきちんと言うには、1以上・法/2以下の二つの数 a, b について、a2≡b2 ⇔ a=b を証明する必要がある。実際には、法が素数ならこれが成り立つ。

ここで、与えられた整数 a が b を法として平方数になるかならないか、ちからまかせに調べる関数をとりあえず作っておく。

function test( a, b ) {
    a %= b;
    for( var i=0; i <= b/2; i++ ) {
        if( i*i % b === a ) return "R";
    }
    return "N";
}

この関数は、与えられた2数 a, b について、a R b なら "R" を返し、 a N b なら "N" を返す。

交換法則が成り立つか

与えられた2つの数 a, b が、a R b であるか a N b であるか。 つまり、a は平方数 (mod b) であるかどうか。 あとから説明するように、a, b はともに3以上の素数と仮定して良い。 それ以外の場合も、3以上の素数の計算に帰着させられるからだ。

a, b を3以上の素数として、a R b なのか a N b なのか一覧表を作ってみよう。 とりあえず20未満の範囲で実行する。

var Primes = [ 3, 5, 7, 11, 13, 17, 19 ];

var d = document;

d.write("<table>");
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    d.write("<tr>");
    for( var j = 0; j < Primes.length; j++ ) {
        var b = Primes[j];
        if(test(a,b)=="R") d.write( "<td style='background:#cff'>" + a + "R" + b + "<\/td>");
        else d.write( "<td style='background:#fcc'>" + a + "N" + b + "<\/td>");
    }
    d.write("<\/tr>\n");
}
d.write("<\/table>");
3R33N53N73R113R133N173N19
5N35R55N75R115N135N175R19
7R37N57R77N117N137N177R19
11N311R511R711R1111N1311N1711R19
13R313N513N713N1113R1313R1713N19
17N317N517N717N1117R1317R1717R19
19R319R519N719N1119N1319R1719R19

この表を観察すると、左上から右下への対角線にそって、だいたい対称になっている。 a R b なら b R a 、a N b なら b N a であることが多いようだが、多少、例外もある。 この問題をハッキリさせるため、次の形式で表を出力してみる。

var Primes = [ 3, 5, 7, 11, 13, 17, 19 ];

d.write("<table>");
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    for( var j = 0; j < i; j++ ) {
        d.write("<tr>");
        var b = Primes[j];
        if(test(a,b)=="R") d.write( "<td style='background:#cff'>" + a + "R" + b + "<\/td>");
        else d.write( "<td style='background:#fcc'>" + a + "N" + b + "<\/td>");

        if(test(b,a)=="R") d.write( "<td style='background:#cff'>" + b + "R" + a + "<\/td>");
        else d.write( "<td style='background:#fcc'>" + b + "N" + a + "<\/td>");

        d.write("<\/tr>\n");
    }
}
d.write("<\/table>");
5N33N5
7R33N7
7N55N7
11N33R11
11R55R11
11R77N11
13R33R13
13N55N13
13N77N13
13N1111N13
17N33N17
17N55N17
17N77N17
17N1111N17
17R1313R17
19R33N19
19R55R19
19N77R19
19N1111R19
19N1313N19
19R1717R19

(7, 3), (11, 7), (19, 3), (19, 7), (19, 11) の組み合わせでは、 式の2つの数字を入れ替えると R か N か?の性質が変わる。 これらの数が入っていても、(7, 5) や (13, 7) は問題なく交換できている。 同じ素数でも、5, 13, 17 が入っている場合は交換法則が成り立ち、3, 7, 11, 19 同士では成り立たない。 いま、5, 13, 17 を「バニラ素数」と呼び、 3, 7, 11, 19 を「チョコレート素数」と呼ぶと、

交換できない、といっても、では予想がつかない結果になるのか?というと、そうではなく、 ここで「交換できない」という意味は、a R b なら b N a になり、a N b なら b R a になるということ、 つまり R と N が正確に入れ替わることを意味している。

4で割って1余る素数、4で割って3余る素数

5, 13, 17, ... のような「バニラ素数」の正体は、4で割って1余る素数であり、 3, 7, 11, 19, ... の「チョコレート素数」は4で割って3余る素数だ。 (素数なので4で割れば必ず余りが出る。2を除外して奇数を考えているので、4で割って2余ることはなく、必ず1か3余る。) 目で見て分かりやすくするために、バニラ素数とチョコレート素数を区別して表示させてみよう。

function display( a, b ) {
    var test1 = test( a, b );
    var test2 = test( b, a );
    var A = flavor( a );
    var B = flavor( b );

    if( test1 === "R" ) {
        d.write('<td style="background:#cff">' + A + 'R' + B + '<\/td>');
    } else {
        d.write('<td style="background:#fcc">' + A + 'N' + B + '<\/td>');
    }

    if( test2 === "R" ) {
        d.write('<td style="background:#cff">' + B + 'R' + A + '<\/td>');
    } else {
        d.write('<td style="background:#fcc">' + B + 'N' + A + '<\/td>');
    }

    if( test1 === test2 ) {
        d.write('<td style="background:#fff; color:green">入れ替えても同じ<\/td>');
    } else {
        d.write('<td style="background:#ffd; color:red; font-weight:bold">入れ替えると逆転<\/td>');
    }

    if( a % 4 === 1 || b % 4 === 1 ) {
        d.write('<td style="background:#fff; color:blue">バニラを含む<\/td>');
    } else {
        d.write('<td style="background:#ffd; color:maroon; font-weight:bold">チョコレート同士<\/td>');
    }
}
function flavor( n ) {
    if( n % 4 === 1 ) return '<em style="color:blue; background:white">' + n + '<\/em>';
    else return '<strong style="color:maroon">' + n + '<\/strong>';
}

var Primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29 ];

d.write('<table>');
d.write('<tr><th>元の式<\/th><th>入れ替えた式<\/th><th>R か N か<\/th><th>式の内容<\/th><\/tr>\n');
for( var i = 0; i < Primes.length; i++ ) {
    var a = Primes[i];
    for( var j = 0; j < i; j++ ) {
        d.write("<tr>");
        var b = Primes[j];
        display( a, b );
        d.write("<\/tr>\n");
    }
}
d.write("<\/table>");
元の式入れ替えた式R か N か式の内容
5N33N5入れ替えても同じバニラを含む
7R33N7入れ替えると逆転チョコレート同士
7N55N7入れ替えても同じバニラを含む
11N33R11入れ替えると逆転チョコレート同士
11R55R11入れ替えても同じバニラを含む
11R77N11入れ替えると逆転チョコレート同士
13R33R13入れ替えても同じバニラを含む
13N55N13入れ替えても同じバニラを含む
13N77N13入れ替えても同じバニラを含む
13N1111N13入れ替えても同じバニラを含む
17N33N17入れ替えても同じバニラを含む
17N55N17入れ替えても同じバニラを含む
17N77N17入れ替えても同じバニラを含む
17N1111N17入れ替えても同じバニラを含む
17R1313R17入れ替えても同じバニラを含む
19R33N19入れ替えると逆転チョコレート同士
19R55R19入れ替えても同じバニラを含む
19N77R19入れ替えると逆転チョコレート同士
19N1111R19入れ替えると逆転チョコレート同士
19N1313N19入れ替えても同じバニラを含む
19R1717R19入れ替えても同じバニラを含む
23N33R23入れ替えると逆転チョコレート同士
23N55N23入れ替えても同じバニラを含む
23R77N23入れ替えると逆転チョコレート同士
23R1111N23入れ替えると逆転チョコレート同士
23R1313R23入れ替えても同じバニラを含む
23N1717N23入れ替えても同じバニラを含む
23R1919N23入れ替えると逆転チョコレート同士
29N33N29入れ替えても同じバニラを含む
29R55R29入れ替えても同じバニラを含む
29R77R29入れ替えても同じバニラを含む
29N1111N29入れ替えても同じバニラを含む
29R1313R29入れ替えても同じバニラを含む
29N1717N29入れ替えても同じバニラを含む
29N1919N29入れ替えても同じバニラを含む
29R2323R29入れ替えても同じバニラを含む

バニラ素数同士や、バニラ素数とチョコレート素数は、ひっくり返しにしても R ないし N の性質は変わらないが、 チョコレート素数同士の場合、ひっくり返しにすると R だったものは N に、N だったものは R に変わる。 以上が「平方剰余の相互法則」の内容だ。

今回のまとめ

2つの素数 p, q について、
x2 ≡ p (mod q) …… ①
が解を持つかどうか?は、ひっくり返した
x2 ≡ q (mod p) …… ②
が解を持つかどうか?と神秘的な関係にある。

すなわち、p, q が両方とも ≡3 (mod 4) 型の素数であるときには、 ①と②のどちらか一方にのみ解があり、他方には解がない(つまり、①と②は「解を持つか持たないか」という属性が逆になる)。 p または q の少なくともどちらか一方が ≡1 (mod 4) 型の素数であれば、 ①と②はどちらも解を持つか、または、どちらも解を持たない(つまり、①と②は「解を持つか持たないか」という属性が一致する)。

例題

x2 ≡ 3 (mod 23977) …… ① には解があるか?

答: 3はチョコレート素数だが、もう一方の数23977は4で割ると1余り、バニラ味だ。 したがってひっくり返しても判定結果は変わらない。
x2 ≡ 23977 (mod 3) …… ② には解があるか?

23977≡1 (mod 3) だから、要するに
x2 ≡ 1 (mod 3) には解があるか?
と尋ねている。ということは ② には x = 1 という解があるので、①にも解がある。

ちなみに、①の具体的な解は 6033であり、60332 = 36397089 を 23977 で割ると3余る。 ソロベイ・ストラッセン・テストによる素数性判定では、①の形の式を実際に解く必要はなく、単に解があるかないかだけ知りたい。 したがって泥臭い数値計算をする必要はなく、今回説明した平方剰余の相互法則と、次回以降に説明するヤコビ記号の性質によって、 高速に判定を実行できる。 なお、両方とも4で割って3余る形の数でも、 判定のアルゴリズム上、支障はない。 その場合、ひっくり返すと「平方数か平方数でないか?」の性質が入れ替わる。

更新履歴

  1. 2003年3月26日: 初版
  2. 2013年6月16日: 「交換法則が成り立つか」のコードサンプルに含まれていた "</td>""<\/td>" に修正(6カ所)。
  3. 2013年12月16日: (1) 誤字脱字の修正: 「法が7でなくても」→「法が17でなくても」。「Aと合同なすべて剰余類」→「Aと合同なすべての数から成る集合(剰余類)」。 (2) 「平方数 vs. 平方剰余」は「数 vs. 剰余類」に対応する、という趣旨の記述を削除。そう定式化しても問題はないが、用語の説明としては正しくない。 (3) 結びの部分の、真意が分かりにくい表現を改善: 「計算上、支障はない」→「判定のアルゴリズム上、支障はない」。
  4. 2014年2月9日: “一方にのみ解があり、他方には解がない”という部分に、“つまり、①と②は「解を持つか持たないか」という属性が逆になる”という言い換えを追加。その他、微調整。
  5. 2014年6月9日: 「17-nの平方」→「(17-n)の平方」。補足説明のための注を2個追加。

この記事のURL

パブリックドメイン


ばびっと数え歌 シリア語編

2014年 2月 9日
記事ID e40209

「古典シリア語の数詞の1~10」を覚えるための数え歌。

歌詞は「ばびっと数え歌」専用ではなく、aḏ — Trēn の行を省けば「ゴンベエさんの赤ちゃんがかぜひいた/おたまじゃくしはカエルの子/まあるい緑の山手線」のメロディーでも歌えます。その場合、行の前半末尾が7音のものは【ゴンベ版】のように5音に縮めてください。「ともだち讃歌」風にも歌えますが、その場合は【ともだち版】のように偶数の数字の歌詞の末尾も短縮してください。

母音記号の付け方はカラバシ方式

数え歌

(1) aḏ — Trēn — aḏ, trēn, tlāṯā — aḏ

ܚܰܕ (aḏ) ードに息を吐く 初めの一歩はモーマンタイ

(2) aḏ — Trēn — aḏ, trēn, tlāṯā — Trēn

ܬܪܶܝܢ (trēn) TRAIN 電車に乗って 二人で旅行は楽しいな

【ゴンベ版】 ܬܪܶܝܢ (trēn) TRAIN 汽車の旅 二人で旅行は楽しいな

【ともだち版】 ܬܪܶܝܢ (trēn) TRAIN 汽車の旅 二人で旅行 (ハッド トレーン!)

(3) aḏ — Trēn — aḏ, trēn, tlāṯā — Tlāṯā

ܬܠܳܬ̥ܐ (tlāṯā) トラ(L)~サ(th)~ このつらさ さんざん数詞にゃ苦労する

(4) aḏ — Trēn — aḏ, trēn, tlāṯā — ʾArbʕā

ܐܰܪܒܥܐ (ʾarbʕā) あるバー やけ酒飲むぞ 4時から酔っぱらって良いご身分

【ゴンベ版】 ܐܰܪܒܥܐ (ʾarbʕā) あるバー やけ酒だ 4時から酔ってる良いご身分

【ともだち版】 ܐܰܪܒܥܐ (ʾarbʕā) あるバー やけ酒だ 4時から酔っちゃった (ハッド トレーン!)

*****

(5) aḏ — Trēn — aḏ, trēn, tlāṯā — amšā

ܚܰܡܫܐ (amšā) ムシャー ハムスター 5匹のムしゃ~ かわいいな

(6) aḏ — Trēn — aḏ, trēn, tlāṯā — Štā

ܫܬܐ (štā) だ シュターだ ロックシュター(ロックスター) ロックシュターはろくろ首

【ともだち版】 ܫܬܐ (štā) だ シュターだ ロックシュター ろくろ首 (ハッド トレーン!)

(7) aḏ — Trēn — aḏ, trēn, tlāṯā — Šaḇʕā

7時に ܫܰܒܥܐ (šaḇʕā) を浴びました シャヴシャヴ シャヴア゙ー(シャワー)を浴びました

(8) aḏ — Trēn — aḏ, trēn, tlāṯā — Tmānyā

8時のテレビは ܬܡܳܢܝܐ (tmānyā) (つまんねえや) 女優が出ても ܬܡܳܢܶܐ (tmānē)

【ともだち版】 8時のテレビは ܬܡܳܢܝܐ (tmānyā) (つまんねえや) 女優も ܬܡܳܢܶܐ (tmānē) (ハッド トレーン!)

(9) aḏ — Trēn — aḏ, trēn, tlāṯā — Tešʕā

9時は眠いぞ 茶を飲むぞ 茶こしがないから ܬܶܫܥܐ (tešʕā) あ゙~ (※「ティッシュで代用したら失敗」という意味)

(10) aḏ — Trēn — aḏ, trēn, tlāṯā — ʕesrā

とうで とうとうラスボス出たぞ ܥܶܣܪܐ (ʕesrā) デスラー 好敵手

【ゴンベ版】 とうとうラスボス おでましだ ܥܶܣܪܐ (ʕesrā) デスラー 好敵手

【ともだち版】 とうとうラスボス 好敵手 ܥܶܣܪܐ (ʕesrā) デスラー (ハッド トレーン!)

お好みで

ばびっと数え歌 シリア語編 > 更新履歴

  1. 2014年1月30日: メモした。
  2. 2014年2月5日: 記事作成開始。
  3. 2014年2月9日: 初版公開。
  4. 2014年2月16日: 「お好みで」に「4時から酔っぱらったら世の中良くならん!」を追加。
  5. 2014年2月23日: 「お好みで」に「ロックシュター(ワウ!)」、「ろくろ首(ワウ!)」を追加。
  6. 2014年3月2日: 太字の使い方を一部変更。

この記事のURL



アドレス = 英語の「クリスマス」の最初の5文字 + アットマーク + faireal.net