彼らは数学しか勉強できない

合同式の基本と応用

　久しぶりの休日、俺は愛華に合同式を教えることにした。高校数学では必修になっていないが、合同式は知っておいて損はない。

「合同式は余りに関する演算（計算）のことだ。数学用語は言葉だけじゃピンと来ないから例を出そう」

　10≡1(mod 3)

「記号の『≡』って普通図形で使うよね」

「学校で習わないだけで、整数論でも合同の記号はよく使われてる」

　図形の「≡」は、2つの図形は同じ形である、という意味だが、合同式で使われる「≡」は、2つの数を同じ数で割った余りは等しい、という意味だ。

「括弧の中にあるmod 3は何？」

「mod（モッド）は余りを意味する『modulo（モジュロ）』の略称。3は割る数のことなんだけど、合同式では法と呼ばれる」

「へぇ。じゃあ、この式は10を3で割った余りは1ですよって意味？」

「簡単に言えばそうだな」

　ちなみに、式の読み方は『10は3を法として1と合同』や『10と1は3を法として合同』とか『10合同1modulo3』など複数ある。ここでは2つ目を採用した。

「ってことは、法が4なら10≡2、7なら10≡3か」　

「そう。肝心の合同式の計算だが、和、差、積の性質は単純だ」

　整数a、bにおいて、pを法(mod p)としてa≡b、c≡dのとき

　a＋c≡b＋d

　a－c≡b－d

　ac≡bd

　また、pを法(mod p)としてa≡bのとき、mを整数として

　a（　m）≡b（　m）

　が成り立つ。

「数式は具体的な数字を当てはめた方がピンときやすい。右側は計算結果でmodの表記は全部省略した。最初に法を書いてるからな」

　7を法(mod 7)として、12≡5、8≡1のとき

　12＋8≡5＋1　20≡6

　12－8≡5－1　4≡4

　12・8≡5・1　96≡5

　5を法(mod 5)として、12≡2のとき

　12（　2）≡2（　2）　144≡4

「割り算の計算をするときは注意がいる。例えば、8≡2(mod 6)は両辺を2で割ると4≡1(mod 6)だが、この式は成立しない」　

「どういうときに成立するの？」

「結論だけ言うと、a、bが互いに素、もしくはpが素数のときに成立する」

　15≡7(mod 4)　　15と7は互いに素。

　15＝3・5より、5≡7/3(mod 4)、3≡7/5(mod 4)（7/3、7/5はそれぞれ3分の7、5分の7）

　8≡2(mod 3)　法が素数

　4≡1(mod 3)

「8≡2(mod 3)の割り算は分かるんだけど、分数の合同はピンと来ない……」　

「そうだろうな。でも、逆算したら両方合ってるのが分かる」

　5≡7/3(mod 4)、3≡7/5(mod 4)　両辺にそれぞれ15を掛ける。

　75≡35(mod 4)、45≡21(mod 4)　ともに式が成立している。

「合同式では負の数を使えば、11≡4(mod 7)と11≡－3(mod 7)のように2通りの表現が出来る」

　　　11≡4(mod 7)

　 11－7≡4－7(mod 7)　両辺から7を引く。

　　　 4≡－3(mod 7)

「2つの式が一緒なんだ。なんか不思議」

「負の数も扱った方が、問題を解く上で計算が楽になることがある。これも例を出したほうが早い。曜日で考えよう」

　俺はスマホを取り出し、各年の曜日を調べた。

「かなり遡るが、2001年1月1日は月曜日だ。これを参考に2017年1月1日の曜日を求める」

「なんで過去の曜日？」

「別にいいだろ。一年は365日だから7で割った余りは1だ。つまり、一年後の曜日は次の曜日と同じになる」

「でも、閏年もあるよ」

「その通り。2001年から2017年までに閏年は4回（2004、2008、2012、2016）あったから、正しくは1・16＋4≡20≡6(mod 7)」

　よって、2017年1月1日の曜日は月曜日の6日後で日曜日。

「20≡－1(mod 7)で考えると、月曜日の1日前だから日曜日。結果は同じだが、こちらの方が早く求められる」

「私は1から順番に数えた方が楽だなぁ」

「それは心理的な問題だろ。これは身近な例で出したけど、累乗の方が実感が湧くと思う」

　俺はそう言ってから、2つの式をノートに記した。

　17≡5(mod 6)、17≡－1(mod 6)

「すでに説明したから分かると思うが、この2つの式は同じものだ。17の8乗を6で割った余りをそれぞれ求めて効率性を比較する」

　17≡5(mod 6)

　17（　8）≡5（　8）(mod 6)

　17（　8）≡390625(mod 6)

　17（　8）≡1(mod 6)

　17≡－1(mod 6)

　17（　8）≡(－1)（　8）(mod 6)

　17（　8）≡1(mod 6)

「17≡－1(mod 6)が圧倒的に楽じゃん」

「だろ。これが100乗とかになったら、前者は計算量が膨大になる」

「確かに。今思ったけど、17（　8）は計算しなくていいの？」

　俺はガクリを肩を落とした。説明を聞いていなかったのか。いや、俺の説明不足か。

「合同式は『2つの数を同じ数で割った余りはともに等しい』という意味だ。だから計算するのは右辺と左辺のどちらかでいい」

　17（　8）≡5（　8）(mod 6)だと、17（　8）≡1(mod 6)だった、つまり17（　8）と5（　8）を6で割った余りはともに1になる。

「今度は合同式を使って簡単な証明をしてみよう」

　2桁以上の整数において、各位の和が3で割り切れるとき、その数自身も3で割りきれることを示せ。

「これ、3の倍数の判定法でよく使われるやつだよね」

「ああ。合同式を使わなくても普通に示せるけど、練習のために選んだ。まずは3桁の整数で示そう」

　3桁の整数を100x＋10y＋zとおいて、10≡1(mod 3)より100x≡x(mod 3)、10y≡y(mod 3)　つまり、100x＋10y＋z≡x＋y＋z(mod 3)

　x＋y＋z≡0(mod 3)ならば、100x＋10y＋z≡0(mod 3)となり題意を満たす。

「今回は3桁で示したけど、10≡1(mod 3)だから、10を何乗しようが3を法として1と合同になる。つまり、4桁以上の整数でも同様のことが言える」

「合同式を使わない証明は？」

「そう来ると思ったよ。さっきと同じように100x＋10y＋zで説明する」

　100x＋10y＋zを3(33x＋3y)＋x＋y＋zと変形する。

　3(33x＋3y)は3の倍数だから、x＋y＋zが3の倍数なら、100x＋10y＋zは題意を満たす。4桁以上の整数も同様。

「うーん……合同式の方が式を変形しなくてもいいから楽だけど、後半の方が文が短いからすっきりした感じがする」

「問題の内容にもよるけど、剰余に関する問題は合同式を使うことを薦（すす）める」　

　これで終わってもいいが、あと一つ応用問題を解いておきたい。

「よし、最後は数学オリンピックの問題で締めくくろう。あ、ちなみに予選問題だ」

「えぇ……。数学オリンピックって予選の時点で難しいって聞いたことあるよ」

「確かに難しいが、解くのは高校生なんだから、そこまで難しい知識は必要としない」

「数学好きの人は、でしょ」

　2500以下の正の整数のうち、一の位が3または7であるものすべての積をXとする。

Xの十の位を求めよ。

「予選で出題された問題は2011以下だったんだけど、キリよく2500にした。まずは一の位が3または7である数字がいくつあるかを調べる」

　一の位が3の数　3、13、23、33、43……

　一の位が7の数　7、17、27、37、47……

「数字を見れよく分かるように、どちらも数字が10ずつ増えているから、これは等差数列だ」

「それは覚えてる。3と7は初項なんだよね」

「正解。一般項a_nは、初項a、公差をd、項数をnとしてa＋d(n－1)で導き出せる」

　一の位が3の数　a_n＝10n－7

　一の位が7の数　a_n＝10n－3

「2500以下だから、最大値はそれぞれ2493、2497だ。これをa_nに代入して項数を求める」

　10n－7＝2493　10n－3＝2497

　　10n＝2500　　　10n＝2500

　　　n＝250　　　　n＝250

「どっちも250なんだ。これ全部掛けるの？」

「んなわけねぇだろ。次に規則性を見つける」

　注目するべきは十の位が同じ数のペアの掛け算。

　3・7　

　13・17

　23・27

　33・37

　43・57

「速算術で十の位が同じで一の位の和が10のとき、こんな計算法がある」

　13・17の計算結果を求めたいとき、十の位と一の位を切り離して考える。

　まず一の位はそのまま計算して3・7＝21

　十の位はどちらかに1を加えて積を計算する。つまり1・(1＋1)＝2

　よって、13・17＝221

「速算術の原理は単純なんだがここでは割愛する。重要なのは、この計算法でいくと、23・27、33・37、43・47、それより先の計算結果は、すべて下二桁が21だと分かる」

　項数はともに250だから、Xの下二桁は21（　　250）(mod 100)を計算すれば求められる。

「250乗って……筆算じゃ計算しようがないじゃん」

「Xの値をすべて求める必要はない。計算するのは下二桁だけでいい」

　少し手間はかかるが、下二桁だけならそれほど時間はかからない。

　21≡21(mod 100)

　21（　2）≡41(mod 100)

　21（　3）≡61(mod 100)

　21（　4）≡81(mod 100)

　21（　5）≡1(mod 100)

「21（　5）で1と合同になるということは、その2乗、つまり2の25乗も1と合同になる」

　より正確には指数が5の倍数のとき、100を法として1と合同になる。

　250＝5・50より、21（　　250）≡21（　　　5・50）≡1(mod 100)

「1は01とも見なせるから、21（　　250）は下二桁が01だと分かった。求めたいのは十の位だから、答えは0となる」

「予選でこんなにレベル高いの？　本選はこれより難しんでしょ」

「難易度は年度によって変わるから何とも言えないが、予選よりは難しくなるだろうな」

　数学オリンピックでは整数問題が多く出題されるから、合同式を知っていた方が有利になる。もちろん、難関大学の入試問題でも同様だ。……使うか使わないかはその人次第だけど。