合同算術を直観的に理解する（時計の算数と、余りがすべてを決める理由）

いま9時で、飛行機は5時間後に出発します。「14時」と答える人はいません。2時と答え、しかも考えずにそう答えます。時計の文字盤に14はないからです。時間は12で一周して、また始まります。時計が読めるようになった日から、あなたはずっと合同算術をしてきました。ただ、記号に出会っていなかっただけです。

これがこの話題のすべてです。一周する数を1つ決め、完全な一周はすべて忘れ、どこに着いたかだけを覚えておく。それが記事1本に値するのは、この1つの習慣、つまり余りだけを残すという習慣が、正面から挑むと手に負えない問題を解いてしまうからです。70桁の数の下一桁、巨大な数が9で割り切れるかどうか、クレジットカードの番号が有効かどうか、そして意図した読み手だけが元に戻せるように文章をかき混ぜる方法まで。

この記事は、その描像です。余りとは本当は何なのか、なぜ計算する前に小さくしてよいのか、負の数やべき乗では何が起きるのか、そして唯一の正直な難所である割り算はどこから来るのか。

余りとは、残り物ではなく、着いた場所

標準的な定義は、$a \bmod n$ とは $a$ を $n$ で割ったときの余りである、と言います。これは正しく、そしてこの話題が面倒に感じられる原因でもあります。「余り」という言葉は、割り算のあとに残った切れ端、付け足しのように聞こえるからです。

もっとよい描像があります。$n$ 個の目盛りが打たれた円形のトラックを思い浮かべてください。目盛りには $0$ から $n-1$ までの番号が付いています。$a \bmod n$ を求めるには、$0$ から出発してトラックを $a$ 歩だけ進みます。止まった場所が答えです。目盛りが5個のトラックを17歩進むと、3周ちょうど（15歩）回ってからさらに2歩なので、目盛り2で止まります。よって $17 \bmod 5 = 2$ です。完全な周回の数が商であり、着いた場所が余りです。

この描像は、定義にはできないことを2つしてくれます。まず、余りが必ず $0$ から $n-1$ の範囲に収まります。目盛りはそれしかないからです。そしてもう1つ、見た目がまるで違う2つの数が mod $n$ で「同じ」になりうる理由を説明してくれます。$2$、$17$、$102$、$5{,}000{,}002$ は、目盛り5個のトラックではどれも目盛り2で止まります。互いの差は周回のぶんだけであり、トラックは周回を覚えていないのです。

数学者はこの考えを合同式として書きます：

$$17 \equiv 2 \pmod{5}$$

「17 は、5目盛りのトラックの上で 2 と同じ場所に着く」と読んでください。三本線は等号ではありません。17 と 2 は等しくないからです。この記号は、トラック上の位置だけを問題にする問いに対しては、この2つが取り替え可能だと言っています。正確に言えば、$a \equiv b \pmod{n}$ とは $n$ が $a - b$ を割り切るということであり、それは2つの数の差が周回の整数個ぶんだという意味にすぎません。

足し算と掛け算は、いまどこにいるかしか気にしない

合同算術を単なる珍しい話ではなく道具にしているのが、次の事実です。2つの数を足してから余りを求めるつもりなら、先に余りを求め、それを足して、もう一度小さくしてよいのです。答えはまったく同じです。引き算と掛け算でも同じことが成り立ちます。

トラックの上では当たり前のことです。17 を足すとは17歩進むことで、それは3周と2歩です。3周は出発点に戻ってくるだけで何も変えないので、17 を足すことは 2 を足すこととまったく同じ効果を持ちます。数の中に隠れている周回はただのおもりであり、足し算を通っても掛け算を通ってもおもりのままです。$n$ の倍数に何を掛けても $n$ の倍数だからです。

$a = qn + r$、$b = pn + s$ として書き下せば：

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

最初のかっこの中にあるものはすべて周回です。生き残るのは $rs$ だけなので、$ab \bmod n$ は $rs \bmod n$ です。余りが、その問いに必要な情報をすべて担っています。

Math Zen の算術トピックのコツが、全部の値を計算するのではなく一歩ずつ小さくしなさいと言うのは、これが理由です。$123 \times 456 \bmod 7$ を求めたいとしましょう。56,088 まで掛け算してから7で筆算の割り算をすることもできます。あるいは $123 = 119 + 4$ だから $123 \equiv 4$、$456 = 455 + 1$ だから $456 \equiv 1$ と気づけば、答えは $4 \times 1 = 4$ です。小さな2回の簡約が、4桁の掛け算を置き換えます。習慣はこうです。余りにしか興味がないなら、数を $n$ より大きく育てないこと。

負の数は逆向きに歩く

トラックの描像は、多くの人がつまずく場面も扱えます。$-3 \bmod 5$ はいくつでしょうか。

目盛り5個のトラックで、0 から3歩うしろへ歩きます。4 を通り、3 を通り、2 に着きます。だから $-3 \equiv 2 \pmod{5}$ です。負の数はただ反対向きに歩くことであり、負の数を直観的に理解すると同じ考えで、余りは相変わらず着いた場所、相変わらず $0$ と $n-1$ のあいだにあります。

近道は、正になるまで周回のぶんを足すことです。$-3 + 5 = 2$ です。$-14 \bmod 5$ なら 15（3周ぶん）を足して 1 を得ます。電卓やプログラミング言語は負の余りについて意見が分かれ、$-14 \bmod 5$ に $-4$ を返すものもあるので、試験では必ずトラック上の非負の目盛りとして答え、信用する前に自分の電卓の約束を確かめてください。

引き算も同じ話です。$3 - 8 \pmod{5}$ は $-5$ で、これはちょうど1周ぶんうしろなので、答えは 0 です。あるいは先に小さくして、$8 \equiv 3$ なので $3 - 3 = 0$ です。

巨大なべき乗の下一桁

この話題を知っておく価値があると人に納得させるのが、この問題です。そしてこれは、先に小さくするという規則の直接の結果です。

数の下一桁はその数の mod 10 です。十の位、百の位、それより上はすべて10の倍数であり、目盛り10個のトラックでは 0 に戻ってくるからです。だから「$7^{100}$ の下一桁は何か」は「$7^{100} \bmod 10$ は何か」という問いであり、$7^{100}$ を計算する必要は一度もありません。

代わりに、7 のべき乗が10目盛りのトラックを歩くのを、毎回小さくしながら見ていきましょう：

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

1 に着いた瞬間、周期が始め直されます。7, 9, 3, 1, 7, 9, 3, 1 と並び、周期は 4 です。$100 = 4 \times 25$ なので、100乗目は完全な1周期の終わり、$7^4$ と同じ場所に座り、その下一桁は 1 です。

どの底も mod 10 で周期を持ち、ほとんどは短いものです。2 のべき乗は 2, 4, 8, 6 を巡ります。3 のべき乗は 3, 9, 7, 1 を巡ります。5 と 6 のべき乗は動きません。方法はいつも同じです。進みながら小さくして周期の長さを見つけ、指数を周期の長さで割り、その割り算の余りが、周期のどこにいるかを教えてくれます。これは指数の、掛け算を繰り返すという考えを、直線ではなく円形のトラックの上で走らせたものです。

9 の各桁の和による判定法が成り立つ理由

各桁を足した数が9の倍数なら、その数は9で割り切れる。誰もがそう習い、ほとんど誰も理由を習いません。合同算術は、これを一行の議論にします。

10 は9目盛りのトラックでは1周と1歩です：$10 \equiv 1 \pmod{9}$。すると $100 = 10 \times 10 \equiv 1 \times 1 = 1$ であり、10 のどのべき乗も 1 と合同です。だから $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ のような数は $4 + 5 + 2 + 7 = 18 \pmod{9}$ と合同で、18 は9目盛りのトラックでは $0$ なので、4,527 は9で割り切れます。各桁の和は手品ではありません。mod 9 で見たその数そのものなのです。

3 の判定法も同じ理由で成り立ちます。$10 \equiv 1 \pmod{3}$ でもあるからです。11 の判定法は $10 \equiv -1 \pmod{11}$ から来ます。これが10のべき乗を $1$ と $-1$ で交代させ、各桁の交代和を与えるのです。暗記しなさいと言われた割り切れるかどうかの規則は、どれも「10 のべき乗を小さくする」という1つの事実を、別々のトラックに当てはめたものです。

検査数字：財布の中の合同算術

どのISBNにも、どのクレジットカード番号にも、どのバーコードにも、余りであることだけを仕事にしている数字が末尾に付いています。

13桁のISBNの最後の数字は、1 と 3 を交互に掛けた13桁すべての重み付き和が $0 \pmod{10}$ と合同になるように選ばれます。1桁打ち間違えれば、その和は10目盛りのトラックの別の場所に着き、読み取り機が受け付けません。クレジットカードは Luhn アルゴリズムを使います。少し賢い重み付けで、隣り合う2桁が入れ替わった場合もほとんど捕まえられますが、やはり和を mod 10 で調べているだけです。

これらは、はるかに大きな応用のつつましい親戚です。現代の暗号は、とても大きな $n$ を法として数をべき乗することはやさしいのに、秘密の鍵なしにその過程を逆向きにたどるのはやさしくない、という事実に支えられています。上で $7^{100}$ のためにやった周期探しは同じ操作であり、それを数百桁の数まで大きくしたものです。そして進みながら小さくするという規則だけが、それを計算できるものにしています。

割り算でトラックが荒れる

足し算、引き算、掛け算は、トラックの上でも数直線の上とまったく同じようにふるまいます。割り算はそうではなく、この話題が悪名を得ているのはここだけです。

ふつうの数直線では、4 で割るとは $\tfrac{1}{4}$ を掛けることであり、それは4を掛けると1になる数です。12目盛りのトラックに、4を掛けると1に着く目盛りはあるでしょうか。全部試してみましょう。$4 \times 1 = 4$、$4 \times 2 = 8$、$4 \times 3 = 12 \equiv 0$、$4 \times 4 = 16 \equiv 4$ となり、4, 8, 0 という型が永遠に繰り返します。1 には決して当たりません。だから12目盛りのトラックでは、4 で割るということ自体が存在しないのです。

理由は、4 と 12 が共通の約数を持つことです。4 の倍数から出発して、12 の周回を足したり引いたりしても、やはり 4 の倍数のままなので、12 の倍数のちょうど1歩先に着くことはできません。代わりに 5 を試しましょう。$5 \times 5 = 25 = 24 + 1 \equiv 1$ なので、5 は12目盛りのトラックでは自分自身が逆数であり、5 で割ることには何の問題もありません。規則はこうです。$a$ が mod $n$ で逆数を持つのは、$a$ と $n$ が 1 以外の共通の約数を持たないとき、ちょうどそのときだけです。

この規則には、目を引く帰結があります。$n$ が素数なら、$1$ から $n - 1$ までのどの数もそれと共通の約数を持たないので、ゼロでないすべての目盛りが逆数を持ち、自由に割り算ができます。素数のトラックは、4つの演算すべてが動くトラックです。素数が無限にあることがその供給を保証している素数が、数論と暗号の中心に座っているのは、これが大きな理由です。

間違いはどこから来るのか

合同算術の部品は少なく、それに応じて間違いも具体的です。

1つめは、底ではなく指数を小さくしてしまうことです。$7^{100} \bmod 10$ では、7 を mod 10 で小さくしてもよく（すでにそうなっています）、周期の長さが分かったあとで指数をその長さで小さくしてもよいのですが、100 を mod 10 で小さくして $7^0$ を計算してはいけません。指数は別のトラック、大きさが周期の長さであるトラックに住んでおり、2つのトラックを混ぜることが、この話題で最もありふれた間違いです。

2つめは、負の余りです。$-14 \bmod 5$ は 1 であって $-4$ ではありません。トラック上では同じ位置ですが、約束された名前はそのうち1つだけで、模範解答が求めているのは非負のほうです。

3つめは、逆数の有無を確かめずに割ることです。合同式の両辺から共通の因数を約せるのは、その因数が法と何も共有していないときだけです。$4 \times 2 \equiv 4 \times 5 \pmod{12}$ は両辺が 8 なので正しいのですが、4 を約して $2 \equiv 5$ と結論することはできません。それは偽です。約すときに捨てる周回は、もとのトラックの周回でなければならないのです。

4つめは、最後に小さくするのを忘れることです。7目盛りのトラックで $rs = 21$ を得て 21 と書くのは、厳密には間違いではありませんが、答えにもなっていません。答えはトラック上の目盛りであり、21 は3周ぶんなので、目盛りは 0 です。

Math Zen が果たす役割

Math Zen の算術トピックには合同算術のための区画があり、進み方は記号ではなく「先に小さくする」習慣のまわりに組み立てられています。はじめの問題は小さな法でのただの余りと合同式を尋ね、「自分はどこに着くのか」が自動になるまで続きます。中ほどの区画には負の数と積が混ざってきて、そこでの要点は掛ける前にすべての因数を小さくし、非負の余りで答えることです。あとの区画は下一桁と周期の長さの問題で、これは競技の問題用紙や入試に出てくるもの、そしてべき乗を丸ごと計算しようとする人を罰するものです。

セッションが短く、問題が間隔を置いて戻ってくるので、数学の練習における間隔反復で述べたように、周期探しは調べ直す手順ではなく反射になります。ほとんどの人は、章を1つ読めば埋まるような合同算術の穴を持っているのではありません。描いてもらえなかった1つの絵、つまりトラックと、やっていない40回ほどの反復を持っているのです。

核心のまとめ

合同算術とは、$n$ 個の目盛りが打たれた円形のトラックの上の算術です。余りは $a$ 歩進んだあとに着く場所であり、完全な周回は忘れられ、2つの数が同じ目盛りに着くとき、それらは合同です。周回は和にも積にも何も寄与しないので、足す前や掛ける前にどの数も自分の余りに置き換えてよく、このたった1つの許しが、$7^{100}$ の下一桁のような不可能に見える計算を、手でたどれる短い周期に変えます。割り切れるかどうかの判定法は、10 のべき乗を mod 9、3、11 で小さくしたものです。検査数字は、打ち間違いを捕まえる余りです。割り算は、その数がトラックと共通の約数を持たないときにだけ働き、だからこそ素数のトラックは特別なのです。

合同算術の問題が行き詰まったら、トラックを描いてください。それぞれの部品がどこに着くかを問い、進みながら小さくし、指数は指数のトラックに置いておく。答えは $0$ と $n - 1$ のあいだの目盛りであり、数式よりも先に絵がそこへ連れて行ってくれます。