読者です 読者をやめる 読者になる 読者になる

アジマティクス

ここをこうするとおもしろい

「平方剰余」を「約数」になぞらえて理解する

突然ですけど、「平方剰余」って概念、わかりにくくないです? なんかググっても「平方剰余の相互法則」のことばっかり出てくるし。その法則がどうやら美しいことはわかったけど、もっと手前のところでつまづいてる人もいるんですよ! なんなんですかあなた! こっちは数学できないんですよ!

 

この記事は、「平方剰余の解説」というよりは、「自分はこんなふうに考えたら捉えやすかったよ」というあれです。ルジャンドルの記号は出てきません。そこまでいきません。

平方剰余

「平方剰余」というのはその実「平方数」のことです。平方数ってのは自然数を2乗した数のことで1,4,9,16,25,...ってやつのことですね。で、それの「剰余」ってわけなので「平方数をある数で割った余り」ということになります。例えば平方数を11で割った余りを考えると1,4,9,5,3,...という数列が出てきます。「11時間時計の世界での平方数」「11までしか数が存在しない世界における平方数」みたいな言い方をしたりもします。ここまでは特にわかりにくいことはない。数式で書くとこうなります。

x^2\equiv{a}\left(\operatorname{mod}p\right)が整数解をもつとき、apを法とする平方剰余、もたないとき平方非剰余という.

あ! ほら! わかりにくい! なんなのこれ!

約数になぞらえてみる

まぁ数式がわかりにくいってのは、英語わからない人が英語に文句言ってるようなもんなので、それは私の不徳の致すところであります。はい。

これは和訳するなら「pで割った余りがaであるような『x^2』という数は、しかも平方根をとると整数になる。そんなxが存在するなら、apを法として平方剰余」って感じでしょうか。7で割った余りが2であるような「なんかの数」で、しかも平方根をとると整数になるようなやつは例えば9とかがあるので2は7を法として平方剰余。

厳密さを確保するべく書かれた数式は、日常言語に比べてわかりにくくならざるをえないという面があることは否定できません。そこで、この定義を私たちのよく知っている「約数」になぞらえて考えてみることにします。

まず、「apを法とする平方剰余」というのを「apの平方剰余」という言い方をしていいことにします。「4は5の平方剰余」「13の平方剰余は1,3,4,9,10,12」といった具合です。

平方剰余:4は5の平方剰余

約数:4は12の約数

平方剰余:13の平方剰余は1,3,4,9,10,12

約数:18の約数は1,2,3,6,9,18

どちらも、元の数以下の有限個の数であることが共通しています。あ、これ以降は平方剰余/約数を求められるべき「元の数」を、平方剰余の話か約数の話かに関わらず「p」と呼ぶことにしましょう。素数に限らないのにpと呼ぶこともありましょうがそこはすいません。

11の平方剰余を、1から10までの10個の数の平方について求めてみます*1。1²を11で割った余り=1、2²を11で割った余り=4、3²を11で割った余り=9、っていうのを10まで続けていくと、1,4,9,5,3,3,5,9,4,1という数列が出てきます。このとき、「11の平方剰余は1,3,4,5,9」というわけです。かぶってる数を除いたんですね(小さい順にしてもいます)。「かぶってる数を除いた」というのはすなわち、平方数をpで割ったやつが「取りうる値」ということですね。つまり平方剰余ってのは数列として一つずつ順番に出てくるわけではなくて「取りうる値」のことなんだよと。当たり前だろお前って思う人もいるかもしれませんが、私自身はこの一言で随分見通しが良くなったのです。

約数の定義も平方剰余になぞらえて書ける

もう一つ私が誤解...というか混同していた点があるんですが、ちょっとその前にもう一点、平方剰余を約数になぞらえることができる点を挙げておきます。

冒頭で私がわかりにくい呼ばわりした数式「x^2\equiv{a}\left(\operatorname{mod}p\right)が整数解をもつ」というのは「\frac{x^2-a}{p}を整数にするような整数xが存在する」ということと同値です。「xが整数であるようなx^2からaを引いたものは、pで割ると整数になる」という意味です。このaってのがx^2pで割った余りと一致してるときのことを考えるわけですね。例えば5の平方である25から、4を引いたもの(21)は7で割ると整数になる、とか。

さらに例をいくつか。

x^2≡5\left(\operatorname{mod}11\right)が整数解をもつ⇔\frac{x^2-5}{11}が整数になる整数xが存在する(x=7とか。xに7を代入して確かめてみてください)

x^2≡9\left(\operatorname{mod}13\right)が整数解をもつ⇔\frac{x^2-9}{13}が整数になる整数xが存在する(x=3とか。)

x^2≡6\left(\operatorname{mod}13\right)が整数解をもつ⇔\frac{x^2-6}{13}が整数になる整数xが存在しない

「存在しない」を判断するのは骨が折れそうですが、それでも右辺は冒頭で書いた定義よりよっぽどわかりやすいと思います。x^2から余りの分をあらかじめ引いておけば、それはpの倍数になるので、pで割ると整数になる(整除)というわけです。

ここで、ためしに「約数」の方もこういう書き方で書いてみると、

\frac{ax}{p}を整数にするような整数xが存在するとき、apの約数という.(存在しないとき、apの非約数とまぁ普通は「非約数」なんて言い方しないけどとりあえずここではそう呼ぶ)

みたいな感じになるかと思います。

例。

\frac{8x}{24}は、xが3の倍数(整数)のとき整数になる。よって、8は24の約数。

\frac{7x}{24}は、xが非整数(\frac{24}{7}とか)のときしか整数にならない。よって、7は24の非約数。

「約数」という概念は平方剰余に比べて比較的わかりやすいのでこんな回りくどい書き方はしないと思いますが、こうするとなんだか平方剰余と似ているなって気もしてきます。

平方剰余:\frac{x^2-a}{p}を整数にするような整数xが存在するとき、apの平方剰余、存在しないとき平方非剰余

約数:\frac{ax}{p}を整数にするような整数xが存在するとき、apの約数、存在しないとき非約数

かたや和の形、かたや積の形って感じですかね。

で、私が混同していた点はどこなのかって話なんですが、この「x」についてなんです。

平方剰余の定義では、xという数は「整数かどうか(x^2平方根をとると整数になるかどうか)」という文脈でのみ登場するのであって、「apの平方剰余」という文にxはもはや出てこないんですね。整数\frac{x^2-8}{17}x^2に当てはまりそうなのは...例えば25。25-8を17で割ると1だし。25の平方根は5。うん。整数だ。xは整数だ。よって8は17の平方剰余。「8は17の平方剰余」っていう文にもはや「5」「25」は登場しない。ってことです。そこが私の混同ポイントでした。「こういう場合に5を17の平方剰余っていう...んじゃなくて〜えーと...」てな具合です。

ちなみにですが、これは約数でも似たことが起きてて、例えば「8は24の約数」っていう文に「3」は出てこないんですね。さっきの定義でいう\frac{8x}{24}が整数になるかどうかっていう文脈の中でのみ3(の倍数)は出てくるわけです。まぁ元の数pを約数で割ったものもまた約数なので、こっちは混同しない...というか「混同しても問題ない」ので、そこは少し平方剰余とは話が違うわけですが。

平方剰余:\frac{x^2-a}{p}が整数になるかどうか、という定義のもとで、「apの平方剰余」という文にもはやxは出てこない

約数:\frac{ax}{p}が整数になるかどうか、という定義のもとで、「apの約数」という文にもはやxは出てこない

この認識によって私の混乱はほぼ解消されたわけですが、こうやって約数になぞらえて考えているとちょっと新たに気になることも出てきました。

「倍数」の平方剰余ver.って?

apの約数」といったとき、「paの倍数」です。だったら「apの平方剰余」のとき、paの...なんていうの? 平方剰余の「逆」にあたる言葉って何?*2

私が調べられた範囲内ではどうもこの概念に与えられた言葉はないようです。この概念を仮に「平方剰余'(平方剰余ダッシュ)」とすると、例えば「7の平方剰余'は9,14,18,19,21,27,29,31,37,38,42,47...」という数列になります。これはつまり7を平方剰余としてもつ数の集合なわけです。3を約数としてもつ数の集合3,6,9,12...がすなわち3の倍数であることと同じですね。約数が有限個で倍数が無限個という点でも共通しています。

数列データベースであるOEISにもこの数列は存在します(A262932)が、「Numbers n such that 7 is a square mod n(mod nで7が平方数であるような数n)」みたいな書き方をしています。あれ? これ見つけちゃった? 新たな概念見つけちゃった? 数学史に名前残しちゃう感じ?

こういうときはだいたい、すでにアホほど先行研究が存在するか、別に役に立たないから今まで名前が付いてなかったかのどちらかなので、興奮するだけムダというものでしょう。

...あ、ほかにも例えば「約数の相互法則」みたいのも考えられるんじゃね? これはwwwうはwwwwおkwwww*3

おわりに

「平方剰余」を「約数」になぞらえて考えたことで、思わぬところに考えが転がっていきました。最後の方のくだりなんかいかにもここから楽しい整数論の世界が広がっているんだよって気がしてワクワクします。これを読んでいるみなさんに少しでもこのワクワクが伝われば幸いです。

参考文献

...の前に、平方剰余について調べるにあたりtwitterで いろいろ質問したりしていたところ、tsujimotterさん(@tsujimotter)、名無し.exeさん(@Natrium_exe)、クレイモアさん(@iClaymore)に助言をいただき、大変助かりました。この場を借りて感謝申し上げます。

参考文献は全部ネットです。

2-2. 時計の世界の整数論 - 2015/3/27 - YouTube ←前出のtsujimotterさんの発表の動画ですが、これさえ見とけば平方剰余に関してだいたいのことはつかめます。

平方数かどうかを高速に判定する方法 - hnwの日記 ←「取りうる」の文言はこちらから。

日々のつれづれ 平方剰余の理論と相互法則 ←「x^2-aがpで割り切れる」はこちらから。

平方剰余の相互法則 - faireal.net ←「平方剰余はすなわち平方数」はこちらから。

*1:11以降の数は、11で割ると結局0から10のどれかの数と同じになるので考える必要はありません。0≡11の倍数のことは基本的には考えません。

*2:相互法則の話ではないです。あれは「平方剰余」という概念があれば十分です。

*3:その場合は約数a元の数pだから「拡張約数」みたいのを考えないといけないかもしれない。