第472回 シーズン48 エピソード2

カレンダーの秘密（後編） ただいま無料

カレンダーの計算から合同式へ

僕「合同式（ごうどうしき）を使うと、 《曜日が同じである》 ことをめちゃめちゃすっきり書けるんだよ。 たとえば、 日付 $2$ と日付 $16$ が同じ曜日であることを、 $$ 2 \equiv 16 \pmod 7 $$ と書ける！」

ユーリ「ごーどーしき？」

僕「そう。便利だよ！」

ユーリ「そんなに便利なんだったら、先にそれを教えてよね！」

僕「ごもっとも……じゃあ、ちゃんと話すよ」

合同式

ユーリ「……めんどくさい話になってきた？」

僕「いやいや、何もめんどくさくないよ。 たとえば、これはどう？」

ユーリ「等式？　めんどくさくないよ。 $a$ と $b$ が等しい。 $a=b$ と書く。知ってるもん」

僕「合同式は等式とよく似ている。 $a$ と $b$ が $m$ を法として合同。それを $a\equiv b \pmod m$ と書く」

ユーリ「まあ……似てるっちゃ、似てる？」

僕「こんなふうに定義を書いた方がわかりやすいかな？」

ユーリ「おっ、似てる似てる！」

僕「具体的に見るとはっきりわかるよ。たとえば、この合同式は成り立つ。 $$ 8 \equiv 1 \pmod 7 $$ なぜかというと……なぜだかわかる？」

ユーリ「同じ曜日だから？」

僕「そうだね。カレンダーでいえばそう。 どんなカレンダーのどんな月でも $8$ 日と $1$ 日は同じ曜日になる。 それは、カレンダーを見ればわかる。 でもいまは定義に戻って考えよう。 こんなふうにね」

ユーリ「$k = 1$」

僕「そうだね。 $k = 1$ とすれば $8 - 1 = 7k$ が成り立つ。 つまり、 $8 - 1 = 7k$ となる整数 $k$ が存在する。 だから、 $8\equiv 1\pmod 7$ は成り立つ」

ユーリ「それって《同じ曜日の日付の差は $7$ の倍数になる》って言ってる？」

僕「そうだよ。カレンダーを見て《二つの日付が同じ曜日かどうか》を考えているときは、 《二つの日付の差が $7$ の倍数かどうか》を考えている。 言い方を変えると、 《二つの整数が $7$ を法として合同かどうか》 を考えているわけだ」

ユーリ「わかってきた！《$m$ を法として》の感じ。一週間が $m$ 日なんだね」

僕「じゃあ、これは成り立つ？」

ユーリ「$2 - 16 = -14$ だから、成り立つ！　 $k = -2$ でしょ？」

僕「そうだね。 $k = -2$ とすれば $2 - 16 = -14 = 7k$ が成り立っている。 だから、 $2$ と $16$ は $7$ を法として合同といえる」

ユーリ「……」

僕「……どうした？」

ユーリ「お兄ちゃん、 $0$ って $7$ の倍数だよね？」

僕「うん、 $0$ は $7$ の倍数だよ」

ユーリ「だったら、 $$ a \equiv a \pmod 7 $$ は $a$ が何でも成り立つ？」

僕「すばらしいな！　その通りだよ！」

ユーリ「だって、 $$ a - a = 0 $$ だから。差が $7$ の倍数。だから $a$ と $a$ は法のもとで平等」

僕「そうそう。ただ、『法のもとで平等』じゃなくて『$7$ を法として合同』だよ」

ユーリ「あっ！　ちょっと言い間違えただけじゃん！」

僕「それはともかく……ユーリの発見からも、 等式と合同式が似ていることがわかるね。 つまり、 $a = b$ なら $a \equiv b \pmod m$ が成り立つから」

ユーリ「同じ日は同じ曜日だから。 あー、でも曜日が同じでも同じ日とは限らないよね？」

僕「その通り。 $a$ と $b$ が合同だからといって、 $a$ と $b$ が等しいとは限らない。 たとえば、 $1\equiv8\pmod 7$ だけど、 $1\NEQ8$ だね」

ユーリ「ふむふむ」

同じ数を足したり引いたり

僕「$a = b$ という等式が成り立つとき、 $a + C = b + C$ も成り立つ。 つまり、同じ数を足してもいい」

ユーリ「当たり前」

僕「では、 $a \equiv b \pmod m$ という合同式が成り立つとき、 $a + C\equiv b + C\pmod m$ も成り立つだろうか？」

ユーリ「えーと……成り立つっしょ？」

僕「早いな！」

ユーリ「だって、 $a$ と $b$ が同じ曜日だったら、両方を $C$ 日動かしても同じ曜日だもん」

僕「なるほど。ユーリは $7$ を法として考えたわけだね。いいね！　ところで、 それは $m = 7$ 以外でもいえる？」

ユーリ「いえる！　一週間が何日でも同じことがいえるから！」

僕「ユーリはちゃんとわかっているんだね。 でも、数式でも確かめよう。定義に戻って証明するんだ」

ユーリ「なんで？　もうわかってるのに？」

僕「きちんと確かめるためだね」

ユーリ「ふーん」

僕「といっても、 $$ a \equiv b \pmod m \LONGIMPLIES a + C\equiv b + C\pmod m $$ を証明するのは簡単だよ」

ユーリ「あらま。簡単ですこと」

僕「だよね。これで合同な二つの整数に同じ整数 $C$ を足しても合同であることがわかった」

ユーリ「ふんふん」

僕「もちろん、 $C$ を引いても合同だね。 $C' = -C$ として $C'$ を足すと考えればいいから」

同じ数を掛ける

ユーリ「足し算、引き算……だったら、掛け算もできそう！ $$ a\equiv b\pmod m $$ のとき、 $$ aC\equiv bC\pmod m $$ になる？」

僕「どう思う？」

ユーリ「できる！　ユーリ、証明やってみる！」

僕「どう？」

ユーリ「できた！　お兄ちゃんのさっきの証明とおんなじだ！」

僕「いいねえ！」

ユーリ「これで割り算もできることがわかった！」

僕「おっと！　割り算もできるとはならないよ！」

ユーリ「へ？　 $C$ を掛けて成り立つんだから、 $C' = 1/C$ として $C'$ を掛ければいいじゃん？」

僕「そうはいかないよ。 $a\equiv b\pmod m$ が成り立つからといって、 どんな整数 $C$ でも $$ \frac{a}{C}\equiv\frac{b}{C}\pmod m $$ とはならない」

同じ数で割れる？

ユーリ「あー！　わかった。ゼロ割りになっちゃうかもしれない！　だから、 『どんな整数 $C$ に対しても $a/C\equiv b/C\pmod m$ が成り立つ』じゃなくて、 『ゼロ以外の整数 $C$ に対して $a/C\equiv b/C\pmod m$ が成り立つ』にすればいいね！」

僕「えらい！　よく気がついたね。でも、それではまだ不十分なんだ」

ユーリ「なんで？」

僕「まず第一に、 $a$ と $C$ が整数のとき、 $a/C$ が整数になるとは限らないから」

ユーリ「あっ……確かに。 $a=1$ と $C=2$ で $a/C = 0.5$ ってことか……」

僕「しかも、割り算の結果が整数になる場合でも、合同じゃなくなることがある」

ユーリ「へー……さっぱりわからん」

僕「たとえば、 $m = 6$ として考える。 $6$ を法とするということだよ。 このとき、 $$ 8 \equiv 2 \pmod 6 $$ が成り立つよね？」

ユーリ「$8 - 2 = 6$ で $6$ の倍数だから？」

僕「そうだね。では $8$ と $2$ をそれぞれ $2$ で割ってみよう」

ユーリ「ほんとだ。 $4 - 1 = 3$ だから $6$ の倍数じゃない……」

僕「だから、 $D$ を $0$ 以外の整数として、 $aD\equiv bD\pmod m$ だとしても、 $a\equiv b\pmod m$ になるとは限らない」

ユーリ「えー……なんで？　足し算はスッと引き算にできたのに、 掛け算はスッと割り算にできないの？」

僕「不思議に思うよね」

ユーリ「思う思う。数学ってもっと、こう、シュッと行くんじゃないの？ 　ミステリーじゃあ！」

僕「そのミステリーを考えてみよう」

ユーリ「おお！」

割り算は掛け算の逆演算

僕「$8\equiv 2\pmod 6$ のとき、《$2$ で割る》のがうまくいかなかった。 割り算は掛け算の逆演算だと考えると、《$2$ 倍する》のを考えたらいいと思う」

ユーリ「なんで？」

僕「こういう図を見ればわかるよね」

ユーリ「わからん。これなに？」

僕「これは $1,2,3,4,5,6$ をそれぞれ $2$ 倍して、 $1,2,3,4,5,6$ のどれと合同になるかを描いたんだよ。 $1$ を $2$ 倍したら $2$ に合同になるから、 $1\mapsto 2$ の矢印がある。 $5$ を $2$ 倍したら $10$ で、 $10$ は $4$ と合同だから、 $5\mapsto4$ の矢印がある」

ユーリ「ふんふん。そんで？」

僕「よく見ると、同じ数に二つの数から矢印が向かっていることがわかる。 $1$ と $4$ から $2$ に、 $2$ と $5$ から $4$ に、 $3$ と $6$ から $6$ に、それぞれ向かっている。 ということはだよ。たとえば、 $6$ を法としたとき、

$2$ 倍したときに $4$ と合同になる数は何ですか？

と言われても答えは一つに決まらない。 矢印は $2$ から来たのかもしれないし、 $5$ から来たのかもしれない」

ユーリ「ははー……」

僕「$2$ 倍したときに $4$ と合同になる数が別々のところからきちゃったら、 元に戻ることはできないよね。つまり $2$ で割ることはできない」

ユーリ「だったら、こーゆー図の方がいーんじゃないの？」

僕「あっ……そうだね。ユーリの言うとおりだ。 $2$ 倍したときにはこの黄色いマルのところでぶつかるから、 元に戻れない。だから $2$ で割ることはできない」

ユーリ「でもね、 割れないことがあるのはわかったけど、 だったら、割り算できないってこと？」

僕「言いたかったのは、割り算を考えるときには、 掛け算の逆を考えた方が……わかった、ちょっと仕切り直そう」

ユーリ「へいへい」

同じ数で割るには？

僕「いまは整数を考えているから、 《等式での割り算問題》をこんなふうに考えよう」

ユーリ「$D\NEQ 0$ ？」

僕「それでいいよ。等式だったら $D\NEQ0$ なら $D$ で割れる。 $aD = bD$ のとき $(a - b)D = 0$ だから、両辺を $D$ で割って $a - b = 0$ なので $a = b$ がいえるからだね。 問題は合同式だ。 いま考えたいのはこういう《合同式での割り算問題》になる」

ユーリ「$D\NEQ 0$ だけじゃダメ」

僕「うん。 等式だったら $0$ 以外で両辺を割れる。 でも合同式はそうじゃない。 割り算できるときもあれば、 割り算できないときもある。 たとえば、 $6$ を法として、 $$ 35 \equiv 5 \pmod 6 $$ が成り立つ。なぜなら $35-5=30$ は $6$ の倍数だから。 そしてこのとき $35$ と $5$ を $5$ で割った $$ 7 \equiv 1 \pmod 6 $$ も成り立つ。 なぜなら $7-1=6$ は $6$ の倍数だから。だから $6$ を法としたとき、 $5$ なら割り算ができるときがある」

ユーリ「$2$ で割ったら駄目だった。 $5$ で割ったらうまくいった」

僕「ちなみに、 $5$ 倍したときのユーリの図はこんなふうになる」

ユーリ「あっ、 $5$ 倍だとぶつからない！　だから $5$ で割れる？　……でも、なんで？」

僕「定義にかえって、具体的に考えてみよう。次の二つを見比べてみる」

ユーリ「……わかったかも？」

僕「何がわかった？」

ユーリ「$\spadesuit$ では、 $2$ で割ったから $6$ の方が割れちゃった！　だから、 $6$ の倍数になれなくなった。 でも、 $\heartsuit$ では、 $5$ で割っても $30 = 6\times 5$ の $6$ の方は割れたりしない。 だから、 $6$ の倍数のままになる」

僕「そういうことになる。 $D$ で割り算するときに、 法になっている $m$ はそのままになってないといけない」

ユーリ「$m$ が $D$ の倍数になってちゃダメなんだね！　 $\spadesuit$ では、 $m = 6$ が $D = 2$ の倍数だからうまくいかなかったんだ……」

僕「$m$ が $D$ の倍数になっていたらダメ。それは確かにそう。 でも、 $m$ が $D$ の倍数になっていなければ大丈夫というわけでもない。 たとえば、こんな場合もうまくいかない」

ユーリ「ほんとだ」

僕「$m = 6$ は $D = 4$ の倍数じゃない。でも $\clubsuit$ のところで $4$ で割るとうまくいかない」

ユーリ「$4$ で割ったときに $12$ が $3$ になった。 $6$ の倍数じゃなくなるのがダメなんだから、 $m=6$ と $D=4$ が同じ数 $2$ で割れちゃダメなんだよ」

僕「その通り。 $m$ と $D$ が《同じ数》で割れちゃダメ。 それを言い換えると、 $D$ の条件は、

　 $m$ と $D$ の最大公約数が $1$ である

になる。それには専用の言い方がある。

　 $m$ と $D$ が互（たが）いに素（そ）である

という言い方だね。 $m$ と $D$ が共通の素因数を持たないといってもいい」

ユーリ「たがいにそ」

僕「だから、合同式についてこんなふうにまとめることができる。 合同式では、割り算だけが条件付きになる」

ユーリ「ねー、お兄ちゃん……」

僕「何？」

ユーリ「等式のとき、割り算ができる条件は $D\NEQ 0$ だったよね？」

僕「そうだよ」

ユーリ「だったらさー……

　$\REDTEXT{$m$と$D$が互いに素}$

っていうのは

　$\REDTEXT{$D\NEQ0$}$

みたいなもの？ だって、それが割り算のための条件なんでしょ？」

僕「ユーリは賢いなあ！　その通りだよ！　

• 《合同式》の世界における《$D$ は法 $m$ と互いに素》
• 《等式》の世界における《$D\NEQ0$》

ユーリ「だよね！」

僕「否定を考えることもできるよ。 《互いに素である》というのは《最大公約数が $1$ である》ということだから、 《互いに素ではない》というのは《最大公約数が $1$ より大きい》になる。 つまりそれは《共通の素因数を持つ》ということだ！」

• 《合同式》の世界における《$D$ は法 $m$ と共通の素因数を持つ》
• 《等式》の世界における《$D=0$》

ユーリ「へえ……」

補足解説

$m$ と $D$ が互いに素であることは、 任意の整数 $a,b$ について $$ aD\equiv bD\pmod m \NARABA a\equiv b\pmod m $$ であることに必要十分です。

「僕」は、 $m$ と $D$ が互いに素であることの十分性は証明していますが、 必要性を証明していません。 以下では対偶法により必要性を証明します。