Day. 11 それぞれの登り方
皆さん、大量の何かを数える時、大体は五個ずつか十個ずつ塊を作って数えますよね。あまりに多いと塊がいくつあるか分からなくて、結局正確な総数は分からない……なんて経験がありませんか？
そんなあなたに、秘密兵器を教えましょう。連立合同式です。
それは、学校からの帰り道でのことだった。
町の真ん中にある小さな山の中には、古い神社があるのだが、麓の鳥居から社のある所まで、長い階段が続いている。わたしがその鳥居の前を通りがかったとき、子ども達のはしゃぐ声が階段の上の方から聞こえてきた。学校帰りに遊んでいたみたいだ。
どんな遊びかというと、三人でジャンケンをして、勝った人が、出した手の形に応じた段数だけ階段を上がって、先にてっぺんに辿り着いた人が勝ち、というものだ。
懐かしいなあ……と、楽しそうに階段を登っていく子ども達の姿に、わたしは感慨を覚えた。わたしが小学生の時も、同級生がこんな感じの遊びをしていた記憶がある。
まあ、わたし自身はやった記憶がないんだけどね。そもそもジャンケンをする相手に恵まれていなかった小学生時代を思い出して、感慨と同時に空しさを覚えたわたしがいた。
「……ということがあったんですよね」
翌日になってわたしは、マス部で昨日のことを雑談同然に話した。今日も蘭子と杏里とわたしの、三人だけのだらだらした活動が始まる。
「他人事なのに懐かしくなっちゃいました」
「清々しい笑顔で自虐するな。聞いてるこっちが空しくなるわ」
「いやいや、今はクラスに友達もいますし（約一名）、部活でも他の部員といい関係になれていますし（約二名）、現状に満足しているから笑顔で言えるんですよ」
「注釈で挿し込まれている数字を見てもそんなことが言えるのか？」
蘭子は憐憫の視線を向けながら呆れている。誰だよ、余計な数字をわたしのセリフに挿し込んだのは。
「でも分かるなあ、懐かしいって気持ち」杏里はふわっと微笑む。「わたしも小学生のとき、蘭子ちゃんとよく一緒にやってたし」
「わたしはやってませんけどね」
「もうやめろ」短く突っ込む蘭子。「そんなこともあったかな。よく覚えてないや」
「高学年になってからはやらなくなったからね」
「だがそのゲームのルールは覚えているよ。ジャンケンで勝った方の手の形になぞらえた言葉の、文字数の分だけ階段を上がるんだろう？ グーはグルタミン酸、チョキはチョリソー、パーはパセリだったか」
「何ですかその明らかに子ども向けじゃないチョイスは！」
あれって確か、昔の子どもが憧れていたおやつに当てはめていたはず。なんで蘭子が真っ先に思いついたのが、味覚のバグったような組み合わせなのやら。甘味が一切ないどころか、一つはもはや食べ物ですらない。調味料だ。
その謎は、幼馴染みの杏里が明かしてくれた。
「その組み合わせって確か、わたし達が昔使っていたルールだったような……」
「ああ、そういえば私と杏里で違うルールを作って遊んでいたんだっけ。まあ当時は小学生のガキンチョだったからな、こういうおふざけもしたものさ」
小学生のふざけ方じゃないんだよなぁ……この先輩たちの過去を知れば知るほど、二人が気の合う変人同士だと思い知らされる。さすが、日暮れまで駐車場の車のナンバーを使ってMake10で遊んでいただけのことはある。
「確かあの時は、チョキとパーが同じ文字数だから、全部バラバラの文字数になるように言葉を変えてみようって、蘭子ちゃんが言い出したんだよね」
「なんでバラバラにする必要があったんですかね」
「だんだん思い出してきた。文字数を全部互いに素にした方が、ゲーム性が上がると思ったからだ。グルタミン酸とチョリソーとパセリなら、文字数が7と5と3だから、途中で同じ段で止まることがかなり少なくなりそうだからな」
そんな理由か……幼稚園児の時から数学好きの蘭子らしい、数学絡みの発想が原因だった。
「それ、楽しかったですか？」
「意外と楽しんでいた気がする」
と、別に意外でもない答えを返す蘭子。しかし一緒に遊んでいた杏里はというと。
「途中から何やってるんだろうって思い始めたりしたけどね」
「文字数の調整を優先して変なチョイスしたら、そりゃそうなりますよ」
「だが、この三つの言葉に設定したことで、なかなか面白いことが起きたよ」
「面白いこと？」
蘭子の言う“面白いこと”は、杏里と先ほどのルールで階段を上がる遊びをしていたとき、偶然に起きた状況だという。
何度かジャンケンを繰り返して、杏里はゴールまであと3段、蘭子は杏里より6段下にいた。杏里はここでジャンケンに勝てばゴールできるが、通常のルールなら、蘭子はチョキかパーで勝たないと杏里に追いつけない。この状況なら杏里はチョキを出すだろう。蘭子がチョキとパーのどちらをだしても、勝つか、最悪でも引き分けになるからだ。そして蘭子はそのことを見越して、グーを出して勝ち、残り6段でリーチをかける、という戦略が取れる。
「…………」
ところが、蘭子が作ったルールだと、杏里に追いつくにはグーで勝つしかない。チョキやパーでは差を縮められても、杏里が依然有利であることに変わりはない。だから杏里は蘭子がグーを出すと考えて、勝つためにパーを出すだろう。蘭子もそう考えて、せめて少しでも近づくためにチョキを出そうとする。だがもし杏里もそれを読んでいたなら、グーを出してくるかもしれない。蘭子がそれを見越してパーを出して勝っても、残りは6段、杏里の優勢は変わらない。杏里がダメージの少ない手を選ぶと考えた蘭子は、杏里の勝ちを無くすためにパーを選んだ。
結果、杏里がチョキを出したことで、蘭子は負け、杏里が先にゴールしたという。
「アホじゃないですか」バッサリと言い切ったわたし。「最初から一番上がれるグーを出せば、最後にチャンスが巡ってきたでしょうに」
「いやあ、策士策に溺れるとはまさにこのこと。杏里にとっては、グーを選んだ方がダメージも低いから、戦略的にグーを出すと思ったんだが、杏里はそんなの関係なく、適当に選んだ手で勝ったんだよ。私は身をもって知ったのさ。ナッシュ均衡は必ずしも最適解とは限らないとね……」
「ナッシュ均衡？」
「ゲーム理論の言葉だよ。戦略を変えても利得が大きくならないために、両者とも戦略を変える必要がない状態を指すの」
なるほど。杏里は勝てばゴールできる状況だから、負けたときの影響が一番小さいグーを選ぶと踏んで、蘭子は杏里に勝たないと終わる状況だから、グーに勝てるパーを選んだ。これがナッシュ均衡にあたる。しかし結果的には蘭子が負けているのだから、考えすぎも考えものである。
「まあ、面白いといえば面白いですね。通常のルールだと、同じようにはならないでしょうし」
「どんなルールでもナッシュ均衡はあるものだけど、その形は違ってくるでしょうね。あ、そういえばそのゲームの後、このルールを使って、階段が何段あるか調べようって話になったんだっけ」
「あー、あったな、そんなこと。二人でひたすら、階段を駆け上がりながら、『ぐ・る・た・み・ん・さ・ん』とか『ち・よ・り・そ・お』とかを何度も連呼していったんだよな」
「ふふっ、懐かしいなあ」
二人で子どもの頃の微笑ましい思い出話を語らっているが、想像するだにシュールな光景だな。ぐ・る・た・み・ん・さ・ん、を連呼しながら階段を登っていく小学生って、どう見てもただの変人だし。
「というか、階段の段数を調べるなら、普通に数えていってもよかったのでは？」
「小学生の背丈だと、百段弱でも途方もないように見えて、普通に数えるのが億劫だったんだよ。その点、この方法なら、3段ずつ、5段ずつ、7段ずつ数えていって、最後に何段余ったか調べるだけでいいから、比較的ラクだったのさ」
あれ、この話、どこかで聞いたような……n段ずつ数えていった余り、という言葉が、わたしは妙に引っかかった。
「ちなみに私たちが実際に登って数えた結果、3段ずつだと1段余り、5段ずつだと2段余り、7段ずつだと6段余った。このことを式で表すとこうなる」
蘭子は椅子から立ち上がり、ホワイトボードに数式を書いた。
x≡1 (mod 3)
x≡2 (mod 5)
x≡6 (mod 7)
「やっぱり、連立合同式でしたか……」
少し前に、マス部のメンバー三人に、わたしの友人の瑠衣を加えた四人で、市民プールへ遊びに行ったとき、流れでトーシェント関数の話を聞くことになった。その際に出てきたのが、modの値が異なる複数の合同式を並べた、連立合同式である。説明しないまま置き去りにした話もあったから、そのうち続きをやるのだろうと思ってはいたが、それが今だったか。
「つまりお二人は、小学生の時から連立合同式のことをご存じだったんですね。しかもその解き方も分かっていたから、段数を数えるのに使えると思った」
「まあ整数の計算だけだったし、小学生でも比較的取っつきやすい分野ではあったからな」
うぅむ……かなり奇妙で変わっている分野だと思うけど、本質は結局割り算の余りだから、小学校の算数の知識があれば理解には困らない。全面的な賛同も反対もできないから複雑な気分だ。
「それに、私も杏里も、小学生の時から和算に触れる機会が多くてね……このタイプの連立合同式は、和算の題目の一つでもあるから知っていたのさ」
「和算って確か、江戸時代の数学ですよね。なんで触れる機会が多かったんですか？」
「あれ、知らなかった？ 杏里の親戚が、近所にある五豊神社の宮司やら権禰宜を務めていて、その関係で杏里も神社の仕事を頼まれることが昔からあったんだよ」
「杏里先輩、巫女さんとかやってたんですか!?」
入部して二ヶ月余り、初めて知った驚きの事実であった。杏里は少し恥ずかしそうに答える。
「正式な巫女は別の人が務めているんだけど、祭祀のお手伝いに駆り出されることはあったよ。お神楽を奉納したり、氏子の皆さんに御神札をお渡ししたり」
「巫女さん姿の杏里先輩……見てみたいです♡」
ちょっと想像するだけでも、巫女の格好やお神楽の衣装を身に纏った杏里は、上品で美しく、神話に出てくる女神の如し。実際にこの目で見たら、うっとりと見蕩れてしまうかもしれない。今のわたしのように。
「十一月のお祭りにも出ると思うから、ぜひおいで」
「ちゃっかりお客さんを確保したな」
と、いらん一言を挟んでくる蘭子。
「ところで、神社だと和算に触れる機会が多いんですか？」
「全ての神社がそうではないけど、和算と深い繋がりを持つ神社はいくつもあるよ。江戸時代は、数学の問題が解けると、閃きをくれた神様への感謝を込めて、問題を書いて額に入れて、神社に奉納することがあったの」
「いわゆる『算額』というやつだな。だから規模の大きい神社だと、この算額を公開して、和算に親しむためのイベントを催すこともある。五豊神社でも、毎年旧正月の時期に、和算関連のイベントをやってるよ」
「そのイベントでお二人は和算に触れていたんですね」
「とはいえ、算額に書かれる問題のほとんどは図形の問題で、連立合同式の問題が書かれた算額を、私は一度も見たことがない」
「え？ じゃあどこで連立合同式を知ったんですか」
「最初に神社のイベントで和算を知ってから、二人で図書館に行って、和算のことを色々調べたんだ。そこで、和算の名著である『塵劫記』の存在を知って、その中の題目の一つである『百五減算』に興味を持ったんだ」
「百五減算？」
「これのこと」
そう言って蘭子が曲げた指で差したのは、さっき書いたこの式だった。
x≡1 (mod 3)
x≡2 (mod 5)
x≡6 (mod 7)
「……連立合同式の別名ってことですか」
「正確には、modが3と5と7である連立合同式をそう呼んでいる。なぜか江戸時代の日本人はこの組み合わせを特に好んでいたんだ」
自分だって小学生の時からその組み合わせにこだわっていたくせに……棚上げもいいとこ。
「ちなみに百五って……」
「3と5と7の最小公倍数、この3つはどの2つをとっても互いに素だから、結局3と5と7の積で105だ。連立合同式の解は、各合同式のmodの値の最小公倍数が、新たなmodの値になるからな」
「つまり、この連立合同式の解は、mod105で表されるってことですか？」
「そうよ」答えたのは杏里だ。「合同式の右辺の値が何であっても、全ての式を満たす整数は、必ず105の間隔で現れるの。だから本によっては、『百五間算』と書いていることもあるわ」
「ああ、それなら合同式っぽくて分かる気がします。じゃあ、百五減算というのはどこから……？」
「それは、実際に連立合同式を解いてみれば、何となく分かるはずだよ」
「解き方を知らないから分かりません！」
「堂々とキメ顔で言うなよ……」
蘭子は呆れたように言った。だって連立合同式という概念自体、つい先日知ったばかりなのに、その解き方まで把握しているはずがあるまい。少し考えてみても、どうやって解けばいいか皆目見当もつかないので、わたしは自信を持って分からないと言える。
え？ そんなことに自信を持つなって？ ほっといてくれよ。
「実は、百五減算の解き方自体は、6世紀頃の中国ですでに見つけられているの」
「6世紀!? しかも中国!?」
「その頃に著された『孫子算経』という本に、百五減算に関する最初の記述があったと言われているの。孫子算経を含めた、唐の時代までの算術書をまとめて『算経十書』と言うんだけど、日本の『塵劫記』はその中の一つから影響を受けているの」
「へえ……」
「でも、孫子算経でも塵劫記でも、一般化した連立合同式の解法までは言及されていない……なぜなら、あらゆる連立合同式を解くには、トーシェントが持つ神秘的な性質、『オイラー師匠の定理』が不可欠だからだ！」
蘭子は手のひらを前に突き出すポーズを決めながら、威勢よく言い放った。尊敬を通り越してもはや崇拝している数学者の名前が出て、一気にテンションが爆上がりしたらしい。対照的にわたしと杏里の視線は冷めているが。
……なお、言うまでもないが、正式な定理の名前に、師匠はつかない。
「オホン」蘭子は一度咳払い。「では、連立合同式の前に、まずはオイラーの定理から説明しよう」
あっ、冷めた空気を感じ取って、師匠をつけるのをやめましたね。
「茉莉、28671は、3で割り切れるか？」
「えらく突然ですね。えっと……」
「3で割り切れるかどうかは、各桁の数の合計が3で割り切れるか調べれば分かるよ」
杏里はすかさずアドバイスをくれた。おかげですぐに答えが出せた。2+8+6+7+1=24なので……。
「そっか、合計は24で3の倍数だから、元の数も3で割り切れますね！」
「はい正解。では次に、28671を3で割った商の、末尾の数字はいくつだ？」
「えっ!?」
いきなりの変化球にわたしはたじろいだ。末尾、つまり一の位の数字を求めるなら、きちんと割り算の答えを出すしかないのでは……頭の中で何とか必死に、28671÷3を計算しようとして、蘭子に止められる。
「いや、バカ正直に割り算しなくても分かるから。九九表の3の段を思い出してみな。末尾が1になる場所は一つしかないだろう？」
3の段の並びは……3,6,9,12,15,18,21,24,27
「そっか！ 末尾が1になるのは、3×7の時だけだから、28671÷3の商の末尾は、7以外にありませんね」
「これと同じことが、末尾が他の数字の時にも言えることに気づいた？」
「え？」もう一度九九の3の段を思い出す。「ホントですね！ 一の位が全て違うから、商の末尾が必ず一つに絞り込めます！」
「3の段だけじゃないよ。1の段、7の段、9の段でも同じく、一の位が全て異なっているよ」
1の段……1,2,3,4,5,6,7,8,9
7の段……7,14,21,28,35,42,49,56,63
9の段……9,18,27,36,45,54,63,72,81
杏里の言うとおり、これらも一の位が全て異なっている。
「今の今まで気づきませんでした……」
「まあ、意識しなけりゃなかなか気づけないだろうな」
「ん？ 一の位だけに注目するのは、mod10で考えるのと同じですよね」
「そうね。しかも今挙げた1,3,7,9は、どれも10と互いに素なんだよ」
「何か重要な繋がりがありそうですね、これは……！」
隠れた繋がりに気づいた刑事や探偵の気分になったので、ちょっとキメ顔でかっこつけてみた。
「その繋がりを定式化したことで生まれたのが、オイラーの定理だよ」
スルーされた。
「今分かったことをまとめると、こうなる」
“10以下”の各自然数に、“10と互いに素な数”をかけて、10で割った余りは、“10以下”の自然数に一対一で対応する。
「そして、私たちが今から知りたいのは、これを一般化した内容だ」
“n以下”の各自然数に、“nと互いに素な数”をかけて、nで割った余りは、“n以下”の自然数に一対一で対応する。
「この予想を、合同式で表すとこうなる」
nと互いに素な自然数αに対して、
1×α≡b1 (mod n)
2×α≡b2 (mod n)
3×α≡b3 (mod n)
:
:
n×α≡bn (mod n)
このとき、
{1,2,3,…,n} = {b1,b2,b3,…,bn}
「最後の式は、要素の順番は違うかもしれないけど、集合としては一致している、という意味だ」
「これってつまり、b1からbnの中に、同じ数がないってことを示せばいいんですね、杏里先輩？」
「そうね、右辺の集合の中にあるのはn以下の自然数で、全部でn個あるから、だぶりがないと分かれば、集合として一致しているといえるよ」
これは……それこそトーシェントの話の時に、似たような証明をした気がする。うん、なんだかできそうな気がしてきた。
「わたし……たぶんこれ、示せます」
「おっ、やってごらん」蘭子は楽しそう。
「n以下の自然数aとa'が、さっきの方法で、同じ数bに対応しているとすると、こういう式が作れます」
わたしはホワイトボードに数式を書いていく。
a×α≡b (mod n)
a'×α≡b (mod n)
「合同式は左辺同士、右辺同士でそれぞれ引き算ができるので……」
(a-a')×α≡0 (mod n)
「これは、左辺がnで割り切れる、ということを示しています。でもαはnと互いに素なので、a-a'がnで割り切れないといけません。ここで、aとa'はどちらも1以上n以下の自然数なので、その差はnより小さくなります。nより小さいnの倍数は0だけなので……」
a-a'=0 つまり a=a'
「となって、結局aとa'は同じ数、ということになります。以上です」
「おー、すごーい♡」
「うむ、細かい条件の不足はあるが、証明としては上等だろう」
杏里は拍手で讃え、蘭子は腕を組んで頷いた。みみっちいレベルの余計なひと言がなければ、わたしも素直に喜べたというのに……。
「とはいえ、ほぼ同じ内容の話を以前にしているし、これだけでは茉莉が力をつけたとは断言できないな」
「むぅ、厳しい……」
「だから茉莉にはもう一つ、あることを証明してもらおう」
「……大変な予感しかしないのですが」
「ここまでの話で、n以下の自然数は、『nと互いに素な数をかけてnで割った余りを出す』という操作で、やはりn以下の自然数に一対一で対応すると分かったわけだが、その対応の仕方には偏りがあることに気づいたか？」
「偏り？」
「例えば、3をかけて10で割った余りを出す場合だと……」
①1→3, 3→9, 7→1, 9→7
②2→6, 4→2, 5→5, 6→8, 8→4, 0→0
「これ……10と互いに素な数のグループと、そうでない数のグループ、それぞれの中で対応関係が完結していますね」
「このことはnがどんな自然数でもいえること（ただしn≧2）なんだが、そのことを示せるか？」
「…………」
示せそう、と思った。必要な条件は目に見えて揃っていて、上手く繋ぎ合わせたらいけそうな気がする。必要なのは合同式と互いに素の使い方、そして背理法だ。
「たぶん、やれます」
そう答えると、蘭子は満足そうに微笑む。もう何も心配はいらない、と言わんばかりに。
完全な見通しはまだできていないが、とにかくやってみよう。わたしは再びホワイトボードに向き直り、数式を書いていく。
「さっきと同様に、nと互いに素な自然数αを用意して、まずはnと互いに素でない数に、αをかけてnで割ることを考えます。つまり、こうです」
nと互いに素でないaについて、
a×α≡b (mod n)
「示したいのは、このbがnと互いに素でない、ということです。ここで、aとnは互いに素でないので、1以外に共通の約数があります。それをdとおきます。そして、合同式は等式に書き換えることができるので……」
a=a'×d n=n'×d とおく。
a×α≡b (mod n) ⇔ a×α-b = n×l（lは整数）
b = a×α-n×l = a'×d×α-n'×d×l = d×(a'×α-n'×l)
「……となるので、bも同じくdを約数に持つので、nとは互いに素でない、ということになります。次に、aがnと互いに素である場合に、bがnと互いに素になることを示します。使うのは背理法です。bがnと互いに素でないと仮定して、この二つの、1でない共通の約数をdとおきます」
b=b'×d n=n'×d
「すると、さっきの式をもう一度使って……」
a×α-b = n×l（lは整数）が成り立つので、
a×α = b+n×l = b'×d+n'×d×l = d×(b'+n'×l)
「左辺のa×αもdで割り切れるということになります。しかし、aもαもnとは互いに素なので、二つともdとは互いに素になります。もしdとの共通の約数が1以外にあるなら、dの倍数であるnもその数を約数に持つので、nと互いに素でなくなってしまいますから。dと互いに素な整数同士をかけたものが、dで割り切れるはずはないので、これは矛盾です。つまり最初の仮定が間違っているので、bもnと互いに素、ということになります。……ど、どうでしょう」
「完璧だよ、茉莉ちゃん」
「うん、いいんじゃないか。ほとんどは以前に見せたテクニックの流用だが、複雑でもちゃんと使いこなせている」
蘭子は素直に褒めることができないのだろうか……拍手で褒めたたえてくれる杏里のことを、少しは見習ってほしい。
「さて、いよいよ定理の証明の最終段階だ。nと互いに素な各自然数に、やはりnと互いに素なαをかけてnで割った余りを出すと、nと互いに素な自然数と一対一で対応すると分かった」
「これらφ(n)個の合同式全てを、左辺同士、右辺同士でかけ合わせると、両辺には、順序が違うだけの同じ乗算があって、しかもそれはnと互いに素な自然数だけをかけ合わせたものだから、当然nと互いに素な数になる」
「左辺がmod nで0と合同、すなわちnの倍数となるには、α^φ(n)-1の部分がnで割り切れないといけない。よって、この関係が成り立つ」
αがnと互いに素のとき、
α^φ(n)≡1 (mod n)
「これが初等整数論の至宝、オイラーの定理だ」
「額に入れて飾りそうな扱いですね……」
「いや、蘭子ちゃんはたぶん、もうやってる」
蘭子をよく理解している杏里がそう言うなら、きっとそうなのだろう。好きな数式を御札に書いて祭壇に飾ると、以前に言っていたくらいだし。
「それで、この定理をどう使って、連立合同式を解くんですか」
「あぁ、そういえばそういう話だったな」
おい、言いだしっぺが忘れるなよ。興が乗るとどこまでも脱線する蘭子は、解説に夢中になって本題を忘れることがたまにある。
「まずは簡単に、二元連立合同式から解いてみよう。mとnが互いに素だとして、こんな合同式を考える」
x≡a (mod m)
x≡b (mod n)
「ここで最初に考えたいのは、二元連立合同式の二つの特殊なパターンだ」
x1≡1 (mod m)
x1≡0 (mod n)
x2≡0 (mod m)
x2≡1 (mod n)
「片方が1と合同で、もう片方が0と合同、という組み合わせですか？」
「そうよ。手始めに、x1の値を求めてみよう。mod nで0と合同ということは、x1はnの倍数なので」
x1=n×y1
「……と表せる。これをmod mの方の式に入れると」
n×y1≡1 (mod m)
「ここで、nとmは互いに素なので、オイラーの定理から次の式が成り立つ」
n^φ(m)≡1 (mod m)
「二つの式を見比べれば、y1の値はすぐに分かる」
y1 = n^(φ(m)-1)
「よってx1の値は……」
x1 = n×n^(φ(m)-1) = n^φ(m)
「ちょっと待ってください」蘭子の説明を途中で止めた。「確かさっき、連立合同式の解は、各modの値の最小公倍数を法とすると言っていましたよね。この場合だと、mod mnでの解を求めないといけないのでは？」
「おっ、気づいたか。実はこの方法で解を出しても、たいていの場合はmnより大きな値になる。それでも合同式の解としては間違っていないが、普通はmnより小さい自然数になるよう調整するものだ。具体例で確かめてみよう。この連立合同式を、さっきの方法で解いてごらん」
x1≡1 (mod3)
x1≡0 (mod5)
「m=3、n=5だから、こうなって……確かに15より大きくなりますね」
x1 = 5^φ(3) = 5^2 = 25
「だから最後はmod15で、0～14の範囲に収まるように調整する。これで解が求められた」
x1≡25≡10 (mod15)
「本来、連立合同式の解は無数にあるが、全て特定の値を法として合同になる。つまり、全ての合同式を同時に満たす整数が一つでも見つかれば、それと合同な整数全てが解になる」
「その中で一番小さい0以上の整数を、解の代表者にするってことなんですね。あっ！」
ここでわたしは気づいた。実際に連立合同式を解けば分かると言われた、あの疑問の答えに。
「そっか、百五減算の“減”はここからきているんですね。今の要領で解の一つを求めても、それは105より大きくなってしまう。それを104以下に収めるためには、105ずつ減らして合同な整数を求める必要があるんだ！」
「そういうことね」と、杏里。
「おーい。最初の疑問の答えに辿り着いたのはいいが、話はまだ終わってないぞー」
あっ、そうでした。蘭子の言ったとおり、今やっているのは連立合同式の特殊なパターンであって、他の場合についてはまだ扱っていない。
「とまあ、連立合同式の片方が1でもう片方が0というパターンは、今の要領で解を求められると分かったわけだが、それ以外のパターンは、この特殊な場合の解を使って解くことができる。これがその式だ」
蘭子はホワイトボードに、一般解を求める式を書き込んだ。
x≡a (mod m)
x≡b (mod n)
この連立合同式の解は、
x≡a×x1+b×x2 (mod mn)
「あれっ、意外とあっさりしてますね」
「合同式が二つだけだから、そう見えるだけじゃない？」
「この解が元の連立合同式を満たすことは、すぐに示せるよ。x1やx2は、mod mとmod nで0や1になるから……」
a×x1+b×x2≡a×1+b×0=a (mod m)
a×x1+b×x2≡a×0+b×1=b (mod n)
「なるほど、確かに解になってますね。先に特殊なパターンを考えておくことで、他のパターンで複雑な計算をしなくて済むんですね」
「その特殊なパターンの解も、オイラーの定理を使えば簡単な式で表せるから、そのまま最後の式に代入しても構わない。x1と同様に、x2もオイラーの定理を使って、このように解けるから……」
x2=m×y2と表せるので、m×y2≡1 (mod n)
オイラーの定理から、y2 = m^(φ(n)-1)
よって、x2 = m^φ(n)
「結局、二元連立合同式の解はこの形になる」
x≡a (mod m)
x≡b (mod n)
この連立合同式の解は、
x≡a×n^φ(m)+b×m^φ(n) (mod mn)
「おー、文字の種類が減って、一発で求めやすくなりましたね。これ、オイラーの定理を知らなかったら、このシンプルな形には辿り着けませんね」
「だろう？」と、得意げな蘭子。「だが、二元連立合同式の話はまだ終わっていない」
「え？ まだ何かあります？」
「さっきはさらっと言っただけだが、この連立合同式を満たすxの値がすべて、mod mnで合同になることは、まだ一度も示していないだろう？」
「ホントだ！ ちゃんと示してもいないのに、しれっとここにmod mnって書いてますよ！」
「しれっとって……だけど、このことを証明するのに手間はかからない。まずは、連立合同式を満たす整数が他にもあるとして、それがmod mnで合同になることを示そう。xの他にx'が連立合同式を満たすとして」
x≡a (mod m)
x≡b (mod n)
x'≡a (mod m)
x'≡b (mod n)
「modの値が等しい式同士で引き算をすると」
x-x'≡0 (mod m)
x-x'≡0 (mod n)
「つまりx-x'は、mとn両方の倍数で、この二つが互いに素だから、結局mnの倍数となる」
「差がmnの倍数ということは、xとx'がmod mnで合同ということですね」
「ああ。これで他に解があるとすれば、それはmod mnで合同になると分かった。次に、mod mnで合同な全ての整数が、連立合同式の解になることを示す。解の一つとしてxが見つかったとして、任意の整数kを使って」
x'=x+kmn
「という整数を作り、これが解になることを確かめればいい」
「そっか、これも簡単に分かりますよ。mod mだとxはaと合同で、mの倍数は0と合同なわけだから……」
x'=x+kmn≡a+0≡a (mod m)
x'=x+kmn≡b+0≡b (mod n)
「となります。mod nの方も同様です」
「うむ、これで必要なことはすべて示せた。ここまでの話は合同式が二つの場合だけだったが、同じことは合同式がいくつあってもいえる。modの値がどの二つをとっても互いに素、という条件下で……」
x≡a1 (mod m1)
x≡a2 (mod m2)
:
:
x≡ak (mod mk)
この連立合同式の解は、mod(m1×m2×…×mk)で必ず一つ存在する。
「これこそが、『中国剰余定理』と呼ばれるものだ」
「ついに出ましたね、中国剰余定理！」
「さっき話に出た『孫子算経』で最初に言及されたことから、その名前がついてるんだよ」
市民プールでトーシェントの解説をしていたとき、トーシェントの乗法性を示すときに使った定理だが、結局その時は「複雑すぎる」という理由で、証明が後回しになっていた。合同式が二つの時だけだが、これでようやく証明を果たしたことになる。確かに結構長くて複雑な証明だった……。
ちなみにオイラーの定理は一般の有限群に、中国剰余定理は環のイデアルに拡張できて、これらの拡張されたバージョンをオイラーの定理や中国剰余定理と呼ぶこともあります。
「さて、長い回り道をしてしまったが、ここまでのやり方を使って、この連立合同式を解いてみるとしよう」
蘭子が指で示したのは、最初に書いた三元連立合同式。
x≡1 (mod 3)
x≡2 (mod 5)
x≡6 (mod 7)
「まずは、特殊な場合を考えるんですね」と、わたし。「一つだけ1で、残りが0となるような場合を……」
「次はオイラーの定理を使って、特殊な場合の解を求めていくわね」と、杏里。
x1=(5×7)^φ(3)=35^2≡70 (mod105)
x2=(3×7)^φ(5)=21^4≡21 (mod105)
x3=(3×5)^φ(7)=15^6≡15 (mod105)
「後は、これら特殊な場合の解と、各合同式の値を、それぞれかけて足し合わせれば……できました！」
x=70×1+21×2+15×6=70+42+90≡97 (mod105)
「確か例の階段は百段弱って言ってましたから、段数は97段で決まりですね」
「うん、ちゃんと答えを出せたな。ちなみに孫子算経や塵劫記では、mod3と5と7の場合に限って、それぞれの余りに70と21と15をそれぞれかけて足し合わせ、105ずつ減らす、という結論だけが書かれている」
「かく言うわたし達も、百五減算の存在を知ったばかりの時は、この結論だけを使って階段の段数を求めていたのよね」
「理屈を知らないと、何かの手品かと思ってしまいますね……」
なぜ70と21と15を使うのか、その理由を納得できるまで探るには、連立合同式の解を求める過程と、オイラーの定理の証明まで知る必要がある。小学生にはなかなか高いハードルだが、この二人だったら小学生の時分でもひょいと跳び越えられそうだ。わたしではたぶん厳しいけど。
ところで、ここまでの話には一つ、しっくりこない所がある。わたしは軽く挙手してから、その事を先輩たちに尋ねた。
「そういえば先輩方、一つ気になることがあるのですが」
「ん、なに？」
「最初に蘭子先輩は、連立合同式を満たす整数は、各modの値の最小公倍数を法として合同だと言っていたじゃないですか」
「あぁ、そのことか」
蘭子はすぐに質問の意図に気づいたけど、念のためわたしは聞きたいことを最後まで告げた。
「でも中国剰余定理の前提は、各modの値がどの二つをとっても互いに素、というものでしたよね。その場合、最小公倍数は全ての値の積になります。わざわざ最小公倍数と言わなくても、全ての値の積と言えばよろしいのでは？」
「なるほど、言いたいことは分かった。私が最小公倍数という言葉を使ったのは、modの値が互いに素でない場合も含めているからだ」
「え？ でもその場合だと……」
「そう。オイラーの定理が成り立つとは限らないから、一般に解があるとは限らない。でも、解が存在する場合には、やはり同じように、ある整数を法として合同な他の整数も、同様に連立合同式の解になる。その“ある整数”が、各modの値の最小公倍数なんだよ」
「中国剰余定理の証明の、最後にやったことを思い出してみて」と、杏里。「解が他にもあるとすれば、その差はmとnの両方の倍数だと分かったでしょ」
「そっか、普通はそれって最小公倍数のことですよね。互いに素だったらmとnの積になりますけど」
「つまり、modの値が互いに素という条件がない場合、連立合同式の解が存在するならば、それらはmodの値の最小公倍数を法として合同だと言えるんだ」
正確には、mとn両方の倍数は“公倍数”ですが、公倍数は全て最小公倍数の倍数になります。
「なるほど……より一般化した連立合同式を意識するなら、mとnの積よりも、最小公倍数の方が、統一感がありますね」
「互いに素という条件もいらないしな」
「でも、互いに素という条件がないと、解がない場合もあるんですよね。それはちょっと困りますね」
わたしは眉じりを下げて、困ったように弱々しく笑う。互いに素という条件があれば、解の存在について気にすることなく、連立合同式が解けるのだが……まあ、解のない連立合同式に行き当たることなんて、現実にはそうそうないだろうけど。
「いや、解があるかどうかを、解く前に確かめる方法ならあるよ」
「あるんですか!?」
「でもせっかくだから、その方法は茉莉が自力で見つけてみるといい」
「最後の最後で投げないでくださいよ!?」
ここまでの説明だってついていくのに必死だったわたしに、蘭子はさらっと酷なことを言ってきた。オイラーの定理や中国剰余定理の時みたいに、先輩たちの誘導があるわけじゃないのに、自力で必要な条件を見つけ出すとか、どんな無理ゲーだ。
しかし蘭子は楽観的だった。ポンとわたしの肩に手を置く。
「大丈夫だって。いろいろ試していくうちに、それっぽいものを見つけられるさ。オイラーだってそうやって定理を発明したわけだし」
「数学界の二大巨星の一人と一緒にしないでくださいよ」
「まあ、いきなりやれと言われても厳しいだろうし、最低限必要なものは渡しておくよ」
そう言ってなぜかロッカーの中を漁り始める蘭子。一応数学の話のはずだし、物理的に必要なのは紙と筆記用具だけで、それ以外の物品が必要になるとは思えないのだが……というか、どうせくれるなら考え方のヒントをくれよ。
蘭子がロッカーからやっとの事で取り出して、わたしにくれたもの。それは、ちょっと大きめでしっかりとした、透明なビニールシート。
「…………」
「それ、消耗品だから好きに使っていいよ」
消耗品、ねぇ……そんなの言うまでもないのだが。こんなものをもらっても、ぶっちゃけ反応に困る。
「あと、油性ペンと定規とハサミは持ってるよな。それらがあればバッチリだ」
「工作でもしろと？」
「別に工作に使っても構わないが、どうせならそのビニールシートを使って、こんな表を作るといい」
「これは、mod3とmod5の連立合同式の、対応する解を表にまとめたものだ。究極、計算をしなくてもこの表を見れば解を出せる」
「おー、二元連立合同式しか使えませんけど、これは便利ですね。……え？ この表を、ビニールシートと油性ペンと定規とハサミで作れと？」
「そうだ」
「ペンと定規はまだ分かりますけど、なんでビニールシートとハサミも必要なんですか」
「ん、それはな……ただのヒントだから、教えない♪」
それはそれはものすごく悪い顔で、蘭子は楽しそうに言った。……こん畜生めぇ。
危うくやさぐれた口調になりかけたわたしに、優しく声をかけてくれるのは、我が愛しの女神、杏里であった。
「要するにね、連立合同式の解の表は、計算しなくても作ることができるってことなの」
「えっ、そうなんですか？」
「うん。よく表を観察して、どうやって作ったらいいか考えてみて」
「分かりました！ やってみます！」
「前から思っていたが、態度が変わりすぎじゃないか……？」
やる気十分で敬礼するわたしに、呆れたような視線を向けてくる蘭子。意地の悪いことをしておいて何を言う。
「まあ、いつもの宿題と同じく、時間制限は設けないから、手を動かしながら気ままにゆっくりと考えればいい。うちは呑気に駄弁るだけのマス部だからな、茉莉は茉莉のペースで、着実にステップを踏んでいけばいいんだ」
そう言って、ニカッと歯を見せて笑う蘭子。その笑顔に意地の悪さは欠片もなく、ただ純粋に、わたしが自分の足で数学の階段を登っていくことを、楽しんでいるみたいだ。
マス部はいつもそうだ。ぐだぐだと、とても役に立ちそうにない、受験にも出ない、風変わりな数学の話ばかりを繰り広げている。そんなマス部に、制約や苦労は似合わない。わたしはわたしの登り方で、ゆっくりと、肩の力を抜きながら取り組めばいい。
「……はい！」
気分の軽くなったわたしは、蘭子にも清々しく笑いかけた。
「もっとも、私や杏里も自分のペースで登っているから、追いつかれるとは思ってないが」
「なんで最後にいい雰囲気を台無しにしますかね」
「あははっ」
わたしと蘭子のコントみたいなオチに、杏里が楽しそうに笑った。今日も今日とて、マス部は平和である。
＊ ＊ ＊
一方で、平和とはとてもいえない日常を送っている人も、このつばき学園高校には存在する。日々の業務に忙殺されながら、特に深く関わっているわけでもない部活動の、面倒な事務手続きを担っている、そんな存在。
その人は、今日も今日とて、職員室で一枚の書類とにらめっこしていた。
「科学研究発表会……去年に続き、うちは存在しない科学部でなく、数学を扱う部が参加するわけか。発表の中身についてはなんにも助言できないから、君たちで頑張ってくれるとありがたいのだが」
辟易とした表情で呟く、ひとりの女性教師。
荒川千百合、担当は現代文。そしてなぜか、数学研究クラブ、通称マス部の顧問である。
最後の最後で新キャラ登場です。もちろんこの人も例に漏れず、有名な数学者の名前をもじっています。数学者の名前をもじって名付けよう、と決めてしまったせいで、いつもキャラの名前を考えるのに苦労します。
顧問の荒川先生は次回のエピソードで本格参戦する予定ですが、その前に……連立合同式の解の表の作り方、皆さんは分かりますか？ 答えはafterにて。
