第476回 シーズン48 エピソード6

平方剰余とルジャンドル記号（後編）

図書館にて

ミルカ「平方剰余（へいほうじょうよ）」

テトラ「へいほう……じょうよ？」

僕「平方剰余？」

ミルカ「素数 $p$ を法とする平方剰余。君とテトラが探しているものはそれだ」

テトラ「《表》の解答は、 $b^2 - 4ac$ がいわば《実数の世界の平方数》であることが条件で、 $b^2 - 4ac \GEQ 0$ と書けました……」

僕「《裏》の解答は、 $b^2 - 4ac$ がいわば《$p$ を法とする世界の平方数》であることが条件。 でも、 $b^2 - 4ac \GEQ 0$ のようなシンプルな形までは書けていない……」

ミルカ「君が言ったその《$p$ を法とする世界の平方数》にはすでに名前がある。 《$p$ を法とする平方剰余》だ。定義はこうなる」

平方剰余

僕「なるほど。 $n = m^2$ だったら平方数。 $n \equiv m^2$ だったら平方剰余。 確かに《$p$ を法とする世界の平方数》といえそうだね」

テトラ「ちょ、ちょっとお待ちください。 具体例を作らないと、ピンと来ません……たとえば、 $p = 7$ として例を作りますっ！」

僕「おおっ！」

テトラ「素数 $p = 7$ として考えます。 つまり、《$7$ を法とする平方剰余》がどんな数なのかを調べます。 整数 $n$ は $p=7$ と互いに素という条件がありますし、いまは《$p$ を法とする世界》で考えていますから、 $$ n = 1\COMMA 2\COMMA 3\COMMA 4\COMMA 5\COMMA 6 $$ で考えることにします……で、いいですよね？」

ミルカ「もちろん」

僕「いいよ」

$p = 7, n = 1$

テトラ「$n = 1$ とします。ええと、はい、 $n = 1$ は $7$ を法とする平方剰余といえます！」

ミルカ「それはなぜ」

テトラ「平方剰余の定義からいえます。 $p = 7, n = 1$ のとき、たとえば $m = 1$ とすれば、 $n \equiv m^2\pmod p$ が成り立ちます。 $$ 1 \equiv 1^2 \pmod 7 $$ ということです。ですから $n = 1$ は $7$ を法とする平方剰余です」

ミルカ「よし」

$p = 7, n = 2$

テトラ「$n = 2$ とします。これは……どうなんでしょうか。 $2^2 = 4$ ですし、 $3^2 = 9$ ですから……あっ、 これでいけそうです。 $p = 7, n = 2$ のとき、たとえば $m = 3$ とすれば、 $n \equiv m^2\pmod p$ が成り立ちます。 $$ 2 \equiv 3^2 \pmod 7 $$ がいえます。 $3^2 = 9$ ですが、 $7$ で割った余りは $2$ だからですっ！　次は $n = 3$ ですが……」

僕「ねえねえ、テトラちゃん、 先に《$m^2$ を $p$ で割った余り》の表を作った方がよさそうだよ」

テトラ「確かに！　結局 $m$ を動かして調べるんですもんね。 《$m^2$ を $p$ で割った余り》つまり $\BAR{m^2}$ の表を作ります……」

$m^2$ を $p$ で割った余り（$p = 7$）

僕「……」

テトラ「この表を見ると、 $\BAR{m^2}$ は $1,4,2$ という値を取ることがわかります。 ですから、《$7$ を法とする平方剰余》は $1$ と $2$ と $4$ だけですねっ！」

ミルカ「それでいいのだが、厳密に言うなら $1$ と $2$ と $4$ だけではない。 $1,2,4$ のいずれかと合同な整数はすべて《$7$ を法とする平方剰余》だ」

テトラ「確かに、定義からするとそうなります。 $1,2,3,4,5,6$ の範囲という条件を付けるなら、 《$7$ を法とする平方剰余》は $1,2,4$ だけです」

ミルカ「それは正しい」

テトラ「これ、おもしろいですね。 $1$ と $4$ は《整数の世界の平方数》になっています。 だって、 $1 = 1^2$ だし、 $4 = 2^2$ だからです。 でも、 $2$ に関しては《整数の世界の平方数》ではありません。どんな整数を持ってきて二乗しても $2$ にはなりませんから。 でも、 $2$ は《$7$ を法とする平方剰余》にはなっているんですね……」

$7$ を法とする平方剰余

ミルカ「いまテトラが平方剰余を調べてくれた。 $1\LEQ n \LEQ 6$ で考えるなら、

• $1,2,4$ は $7$ を法とする平方剰余である。
• $3,5,6$ は $7$ を法とする平方非剰余である。

テトラ「ちょっと気になったんですが、 《非平方剰余》ではなくて《平方非剰余》というんですね」

ミルカ「数学書にはそう書いてあるな。理由は私も知らない」

テトラ「英語では何と言うんでしょう」

ミルカ「平方剰余はquadratic residueで、 平方非剰余はquadratic non-residue」

テトラ「nonの位置について対応はしてるんですね」

僕「……」

テトラ「先輩？」

$m^2 \equiv(p-m)^2 \pmod p$

僕「さっきテトラちゃんが《$m^2$ を $7$ で割った余り》の表を作ってくれた。 そのとき、 $m$ と $\BAR{m^2}$ はこうなってたよね。

$$ \begin{array}{|c|cccccc|} \hline m & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \BAR{m^2} & 1 & 4 & 2 & 2 & 4 & 1 \\ \hline \end{array} $$

$1,4,2$ と $2,4,1$ になってる。これ、対称性があるね！」

テトラ「まるで、『か・る・い・い・る・か』という回文みたいです」

僕「軽いイルカ？」

ミルカ「一般化できる。こういうことだな。これは難しくない」

テトラ「難しく……ないですか？」

僕「《定義にかえれ》でいけそうだよ。 $$ m^2 \equiv (p-m)^2\pmod p $$ は、 $$ m^2 - (p-m)^2 = pk $$ となる整数 $k$ が存在することと同値。 ところで、 $$ m^2 - (p-m)^2 = m^2 - (p^2 -2pm + m^2) = p(2m - p) $$ だから、 $k = 2m-p$ とすればいいね」

テトラ「なるほど……」

素数 $p$ が $0$ のよう

僕「たとえば、いま出てきた二つの式を見る。 $$ \begin{xalignat*}{1} m^2 &\equiv (p-m)^2 \pmod p \\ m^2 &= (0-m)^2 \end{xalignat*} $$ すると、 二つの式はぴったり呼応しているように見える。 《$p$ を法とする世界》では、 $p$ がまるで $0$ のような働きをすることがあるよね……」

ミルカ「ふむ」

僕「$p$ の倍数で割り算ができないのもそうだったし……」

テトラ「確かにそうですね。《$p$ を法とする世界》では、 $p$ がまるで $0$ のよう……」

僕「ちょっと待って！　 そうか。 $6$ は $-1$ だよね？　 ということは《余り》って、 正と負に分けられるんじゃない？」

ミルカ「その通り。 $(p-1)/2$ を超えたなら、 $-p$ シフトすればいい。 そのような剰余を、 通常の《最小非負剰余》に対して 《絶対的最小剰余（ぜったいてきさいしょうじょうよ）》という」

僕「あっ、名前があるのか！　そりゃそうか……」

テトラ「せせせ先輩方っ！　テトラを置いていかないでくださいっ！」