after Day. 11
連立合同式のより一般的な解き方は、解の表を作って観察することで見えてきます。さあ皆さんも、透明なシートと油性ペンと定規とハサミを用意して、Let's try!
マス部で連立合同式の解き方を学んだその日、またも面倒な宿題を携えて帰宅したわたしは、その凄絶な光景に愕然とした。眉間にしわが寄り、口角が下がり、一気に血の気が引く感覚がした。
我が家のリビングでは、フローリングの床に四つん這いになっている姉の八重子が、一面に散らばった色とりどりのビーズを拾い集めている最中だった。一見しただけでも、床に散らばったビーズは、千個を優に超えているだろう。
わたしの帰宅に気づいた姉が、涙目になってわたしに懇願してきた。
「もんちゃ～ん……手伝っておくれぇ～」
「何やってんのよ、お姉ちゃん……」
我が家の生活の中心となる部屋の床がこんな状態では、面倒でも放っておくわけにいかない。丸みを帯びているビーズを床に落としたなら、たぶんあちこちに転がってしまっている。二人で拾い集める方が効率的なのは明らかだった。
わたしも床に膝をついて、ちまちまとビーズを拾いながら、姉に尋ねる。
「仕方ないなあ……このビーズどうしたの」
「覚えてない？ 昔、お母さんにせがんで買ってもらったやつだよ。あの頃にちょうどクラフトビーズのブームが来ていたから、めっちゃ駄々こねていたよね」
「……お姉ちゃんがね」
言われて思い出した。他人事のように思い出を語っている姉こそ、クラフト専門店で床に寝転がってあーだこーだと駄々をこねて暴れていた張本人だ。物心がついて間もない頃のわたしが、そんな姉を冷めた目で見ていて、子どもながら反面教師というものを覚えた瞬間であった。
「私はもうとっくに遊ばなくなったけど、大学でクラフト同好会に入ってる友達が、次の学祭に向けた作品づくりで大量のビーズが必要だっていうから、うちにあるやつをあげようと思って」
拾ったビーズを瓶の中にザラッと入れながら、姉は事の次第を説明する。話には聞いたことがあるけど、大学のサークルって本当に多種多様なのだな。つばき学園高校も変な部活が多いけど、大学はきっとその比ではないのだろう。
「ふうん……タダであげるの？」
「展示するだけで売りに出すわけじゃないし、放っておいてもゴミになるだけの代物だしね。損得抜きで分け合い与え合うのが、“友達”ってものなのよ」
「友達が少ないわたしへの当てつけかな？」
ドヤ顔で友達について語る姉に、わたしは少しイラッとした。姉はわたしと違い、高校でも大学でも、友達を作るのに苦労していない。
「まあそれで物置からビーズの瓶を引っ張り出して、中身が劣化していないか確かめるために蓋を開けようとしたら、思いのほか固くてね……力加減を間違えて、蓋を開けた瞬間に手を滑らせてしまって……で、この有り様ってわけ」
「なるほどね。たぶん最後に蓋を閉めたの、お父さんだわ……適当なくせに馬鹿力だから」
「蓋も容器もプラスチック製だし、どこかしら変形していたんだろうねぇ」
まったく、うちの父が余計なことをしてくれたものだ。最後に使ったのはたぶん十年くらい前だから、およそ十年越しの嫌がらせだ。
無駄な恨み言はさておき、わたし達は十分近くかけて、ようやく全部のビーズを拾い集め、プラスチックの瓶の中に突っ込んだ。もっとも、家具の隙間とかに入った可能性もあるから、本当にこれで全部なのか分からないが。
「ふう……これである程度は拾えたかな」
「全部じゃないかもしれないけど、いいの？」
「小さいときに何個か使っているし、たぶんその時にも多少は無くしているから、元から全部揃っていたわけじゃないよ。あいつらだって、余り物なのは承知の上で受け取るつもりだから、この場で少し減ったところでどうとでも」
「お姉ちゃん、そんなだから無くし物が多いんだよ。それに、クラフトの材料にするなら、個数は把握しておく必要があるんじゃない？ 瓶には1200個って書いてあるけど、絶対それより少ないし」
「……この小さくて大量のビーズを、数えろと？」
「地道にやっていけば、どうにかなるんじゃない？」
「絶・対・無・理！」険しく圧の強い顔になる姉。「1000個近くあるビーズをちまちま数えるとか、時間がいくつあっても足りんわ！」
「いや、一日もあればお釣りがくると思うけど……」
「その一日があったらだらだらのんびり過ごしてやるわ！」
「勉強しなよ大学生」
姉が家で勉強とかをしている所って、未だに見たことがないけど、ちゃんとやっているのかな。というか大学生ってそんなに暇なのか。
「クラフト同好会の友達にそんな手間を負わせるくらいなら、この場でちゃんと個数を把握してから渡した方がいいんじゃない？」
「もうめんどくさいからもんちゃんやって～」
「めんどくさい事を妹に押しつけるな」
姉の面倒くさがりは今に始まったことじゃないが、押しつけられる方は業腹というものだ。わたしの不平を横目に、姉はビーズの瓶をテーブルに放置して、いつものソファーに向かった。
まったく、仕方のない姉だ。わたしはため息をつきながら、ビーズを数えるための準備を始める。
「お姉ちゃん、なるべく大きいお皿とかない？ このビーズが全部入るやつ」
「台所にある調理用のバットでも使えば？」
「…………」
ソファーに腰かけて、顔だけこちらに向ける姉のなおざりな答えに、わたしは閉口した。いい反論の言葉が思いつかないのが情けない。
結局わたしは台所のバットを持ってきて、その中にビーズを全て移した。そしてまずは、3個ずつ拾い上げて瓶の中に戻していく。拾って戻す回数はカウントせず、ただ無心で作業するので、まあまあ速い。最終的にバットの中に残った個数を、手元のメモパッドに記録していく。
「余りは1個か……次は5個ずつ、っと」
「もんちゃん、どういう数え方してるの？」
「3個ずつ、5個ずつ、7個ずつ、8個ずつ拾って瓶に戻して、余った個数を記録してる。連立合同式を使えば、840間隔で値が求められるはず」
「なんじゃそりゃ」
経済学部の姉は恐らく初耳であろう、連立合同式の解き方の話を、わたしはかいつまんで説明した。証明の中身はすっ飛ばして、大体の結論だけだが、今はそれだけで充分だろう。
「はあ～……江戸時代の人たちって変わってるなあ。数学が娯楽だなんて。どんだけ娯楽が少なかったんだろうね」
「失礼なこと言わない」
「で、その連立合同式ってのを作って解けば、ちまちま数えなくても個数が分かるの？」
「840以上の差があったら分からないけど、瓶の大きさに比べてそれほど減ってないから、たぶん分かると思うよ。いま数えたら、3個ずつだと余りは1個、5個ずつだと余りは2個、7個ずつだと余りは5個、8個ずつだと余りは4個だったから……」
姉に説明している間にも作業を続け、バットに残った個数を記録してから、わたしはメモパッドに連立合同式を書いた。
x≡1 (mod 3)
x≡2 (mod 5)
x≡5 (mod 7)
x≡4 (mod 8)
「こんな連立合同式を解けばいいってことになる」
「……解けるの、それ？」
「式が4つのパターンは初めてだけど、たぶん同じ要領で解けると思う。ちょっとやってみるね」
「ちょっとコンビニ寄ってくるね、みたいなノリでやるのか……」
さすがにそこまで軽くはないと思うけど、一段階レベルを落とした具体例をすでにやっているから、特に苦も無く計算を進められそうだ。
十分もかけずに答えは出た。
「できた。mod840で292だから、ビーズは全部で1132個だね」
「マジで解いちゃったよ、うちの妹……」
途中計算はここに書きません。皆さんもぜひチャレンジして、この答えが正しいことを確かめよう。
「そんじゃ、忘れないうちに瓶のラベルにでも書いておいて」
「お姉ちゃん、人任せにしすぎ」
「でもなんだかんだ言ってちゃんとやってくれるもんちゃんが好きよ♡」
「…………」
やらなければ黙ってくれるかと思ったけど、たぶんそのまま忘れられるので、結局わたしがラベルに個数を書いた。ラベルの表面が薄いプラスチックなので、油性ペンで書き込む。
と、ここで宿題のことを思い出した。
「あっ、そうだった。マス部でまた宿題が出されたんだった……」
「もうすっかりお馴染みだねぇ。さっき言ってた、連立合同式絡み？」
「うん。透明なビニールシートと油性ペンと定規とハサミを使うんだって」
「え？ 何それ、工作？」
姉が怪訝な顔をするのも分かる。わたしも未だにこの宿題の意図が見えない。
「よく分からないけど、こんな感じの表を作ってほしいみたい。連立合同式の解が分かる表だって」
「ふうん、これでどんな連立合同式でも解けるの？」
「3で割った余りと5で割った余りが分かっている時だけね」
「……おや？」
姉は何かに気づいたみたいに、目を丸くする。
「ねえ、そのビニールシートって、今持ってる？」
「うん。蘭子先輩にもらったやつがカバンに」
「ちょっと貸して。ついでに定規と油性ペンも」
「いいけど……何するの？」
「もしかしたら、こうやったら作れるんじゃないかと思ってね……」
わたしから手渡されたビニールシートをテーブルに広げて、姉はその上に定規を宛てがい、油性ペンで線を引いていく。
ビニールシートに定規で線を引くこととか、そうして表を作ることは予想していたが、どんな表を作るかまでは考えついていなかった。数学に明るくない姉が、一見して気づいた事とは一体……。
「さっきの表だけど、0から順に辿ったら、常に斜めに並んでいたんだよ。だから……最初はこんな感じの表なんじゃないかと思ったの」
「15×15のマスに、0から14までを対角線上に並べたの？」
「で、この表を、3×5の長方形に切り分ける」
姉はハサミを使って、まずは表全体を切り抜いて、次に3×5の長方形に切り分けた。これで15枚の、空白だらけの表が書かれたビニール片が出来上がる。
「そしてこの中から、数字が書かれているやつだけを集めて、重ねれば……ほら、さっきの表ができた」
「ホントだ！ すごい！」
透明なシートを使うことで、下に重ねられた表の数字も透けて見えて、全てのマスに0から14の数字が収まった。しかも連立合同式の解の表と、ぴったり一致している。皆さんもぜひ、同じ材料を用意して確かめてみよう。
「ふふー、どうよ。お姉ちゃんはすごいだろう」
「いや、すごいのは表の作り方の方だよ」
「…………」
調子に乗って胸を張る姉を無視して、わたしはビニール片で作られた表に注目していた。まあ、これに初見で気づくのは、なかなかだと思うけどね。難しく考えず、ただ表を眺めていたからこそ、この方法に辿り着けたともいえるが。
ふむ……先輩たちの言っていた通り、解の表は計算なしで作ることができた。この方法なら、modの値が互いに素でない場合の表も、同様に作れるかもしれない。
善は急げ、だ。わたしはビニールシートの残っている所に、定規で表の枠を書いていく。今度はそうだな……mod6とmod9でやってみよう。最小公倍数は18だから、まずは18×18のマスを作って、左上から右下までの対角線上に、0から17までを書き込んでいく。
こんな感じの表ができた。
次に、6×9の長方形になるように裁断し、数字が書かれているものだけを集めて、重ねてみる。
うーん、なるほど。作っている最中も思ったが、やはり空欄が多い。
「おっ？ 今度はずいぶん空白が多いね」
「空白の所はつまり、解がないってことだね」
「解がない場合もあるんだ……」
「二つのmodの値が互いに素でない……つまり共通して割り切れる数が1以外にあるときは、解がないこともあるんだって。解があるときとないときを見分ける方法を見つけるのが宿題だったんだけど……」
「これを見ると、確かに何かしら法則がありそうだね」
「斜めに並んでいるのはさっきと同じだけど、縦と横はどちらも2マスおきに並んでいる……ということは、6で割った余りと9で割った余りが、mod3で合同ってこと？」
というわけで、解の表から分かったことをまとめると、こうなった。
x≡a (mod6)
x≡b (mod9)
この連立合同式は、a≡b (mod3)のとき、解が存在する。
「当然だけど、最後の3はこの連立合同式限定だよね」
「うん……この3がどこから来たのか分からないと、答えにならないね。一番可能性が高いのは、6と9の最大公約数だけど……」
「ああ、確か、両方を割り切る最も大きい数だっけ？」
姉のこの発言を蘭子が聞いたら、「正確には、与えられた整数を同時に割り切る最大の自然数だな」とでも言うのだろう。そんなことが簡単に想像できるくらいには、わたしも数学の言葉遣いに慣れてきたと思う。
「とにかく、書いてまとめてみよう。現時点での予想は……こんな感じ」
x≡a (mod m)
x≡b (mod n)
この連立合同式は、
a≡b (mod gcd(m,n))のとき、またその時に限り、
mod lcm(m,n)でただ一つ解が存在する
※gcdは最大公約数(the greatest common divisor)、lcmは最小公倍数(the least common multiple)
「先に具体例を見たからまだ理解できるけど、複雑だなぁ……お姉ちゃんついていけねーわ」
姉は恐らくここで付いてこれなくても、この先困ることはないだろう。わたしは宿題として出されているから、予想を立てるだけじゃなく、きちんと証明もしなければならない。正しいかどうかも分からないし、証明が見つかっているのかも知らないが、蘭子が宿題として出すのなら、たぶん証明は可能なのだろう。
というわけで、ドロップアウトした姉を放置して、わたしは手元のメモパッドに書き込みながら、証明の方法を探っていく。
式がぐちゃぐちゃにならないように、mとnの最大公約数をg、最小公倍数をlとおこう。まずはaとbがmod gで合同のとき、解が存在することを示す……これはたぶん、mとnが互いに素の時と同様、直接に解を構成する式を作ればいい。
aとbは、gで割った余りが等しいのだから、
a=gq+r, b=gq'+r (r<g)
という形で書ける。もちろんrは0以上の整数だ。
mとnが互いに素の時は、aとbの片方が1でもう片方が0という、特殊な場合を使っていた。互いに素という条件がなければ、どんな場合を考えたらいいだろう……。
互いに素という条件があるとき、最終的な解はax1+bx2という形になっていた。元の合同式に当てはめたとき、x1とx2は、片方が1でもう片方が0だから、うまくaやbだけが残ったのだ。ということは、mod mおよびmod nで考えたとき、うまくaやbだけが残るように、解の形を考えればいいことになる。
「んー、アイスうっめ」
姉はソファーに腰かけて、アイスを食っていた。わたしは別に後回しでもいいけれど、聞こえよがしに呟くのはやめてほしい。
えっと、つまり……mod mではgq+r、mod nではgq'+rとなるように、解の形を決めればいい。rは当然最後につくだろうし、aとbを元にして解く以上、qとq'も使いたい。ということは、片方がgでもう片方が0となるように、特殊な場合を考えればいいことになる。
ならば例えば、こんな連立合同式を考えたらどうだろう。
x1≡g (mod m)
x1≡0 (mod n)
x2≡0 (mod m)
x2≡g (mod n)
そして、最終的な解の形を、x1q+x2q'+rという形にすれば……。
x1q+x2q'+r≡gq+r = a (mod m)
x1q+x2q'+r≡gq'+r = b (mod n)
「やった！ これで解の形を作る事ができたから、解は存在すると言っていいはず！」
「お、できた？ もんちゃんもアイス食べる？」
「……いや、まだいい」
まだ全部終わったわけじゃないのに、姉は甘味休憩に巻き込もうとしてくる。ちょっと神経を逆撫でされたが、証明もあと一息だし、落ち着けわたし。
さて、さっきは勢いで、解は存在するはずなんて言ってしまったが、よくよく考えたらそれは、特殊な場合の連立合同式に解があることが前提となる。その事を証明しなければ、解が存在するとは言えない。
だが、恐らくこれは、オイラーの定理を使えば何とかなる！
x1≡g (mod m)
x1≡0 (mod n)
例えばこの連立合同式の場合、x1はnの倍数だと分かるので、x1=n×y1とおくことができるから……。
n×y1≡g (mod m)
この合同式を解けばいいということになる。
ここでオイラーの定理を使いたいところだが、今回はmとnが互いに素という条件がないので、このままだと使えない。だけど、m/gとn/gだったら互いに素だから、オイラーの定理が使えるはず。gはmとnの最大公約数だから、m/gとn/gを同時に割り切る2以上の整数はもうないのだ。
m/gとn/gに関してオイラーの定理を使うと、
(n/g)^φ(m/g)≡1 (mod m/g)
この式は等式に置き換えるとこうなる。
(n/g)^φ(m/g) = km/g + 1
全体をg倍すれば、
g×(n/g)^φ(m/g) = km + g
この式の左辺は、mで割った余りがgだから、合同式に再び置き換えると、
g×(n/g)^φ(m/g)≡g (mod m)
累乗の部分を少し分解して変形すると、
g×(n/g)×(n/g)^(φ(m/g)-1)≡g (mod m)
n×(n/g)^(φ(m/g)-1)≡g (mod m)
最初の合同式と比較すれば、y1の値が分かるから、これでx1の値も分かる。
y1 = (n/g)^(φ(m/g)-1)
x1 = n×(n/g)^(φ(m/g)-1)
= g×(n/g)^φ(m/g)
同じ要領でx2の値も求められるから、やはり特殊な場合の連立合同式にも、解は確実に存在する。
これで解の存在は示せた。解がmod lで一つしか存在しないことは……すでにマス部の部室でやったからいいか。
最後に、a≡b (mod g)の時だけ、解が存在することを確かめる。要するに、解が存在するなら必ずaとbがmod gで合同になる、ということを示せばいい。
aとbをそれぞれgで割った余りが、実は等しいと分かればいいのだから、
a=gq+r (r<g)
b=gq'+r' (r'<g)
このようにおいておき、r=r'を導く。
連立合同式に解が存在するとして、その解の一つをcとおくと、
c≡a (mod m)
c≡b (mod n)
ここからどうやって進めようか……式同士で足したり引いたりしてみる？ いやいや、modの値が違うならそれはできない。
……おっと、すでにaとbを別の形にするための式があるじゃないか。試しにこの式を代入してみよう。
c≡gq+r (mod m)
c≡gq'+r' (mod n)
うーん……これでも上手くいく気がしないなぁ。せめて、rとr'がmod gあたりで合同だと示せたらいいんだけど、結局、modの値が異なる合同式では足し引きできないから堂々巡り……。
いや、待てよ？ 合同式のままでダメなら、いっそ等式に置き換えてみたらどうだろう。いま作った合同式を、等式に置き換えると……。
c = km+gq+r
c = k'n+gq'+r'
※kとk'は整数。
「…………」
じっと見ていたら、なんかいける気がした。
さっきわたしは考えた。mod gでrとr'が合同だと示せたらいいのに、と……そしてgとは、mとnの最大公約数。逆に言えば、mとnは両方とも、gの倍数ということだ。
つまりさっきの式から、このことがいえる。
c≡r (mod g)
c≡r' (mod g)
rとr'は、mod gで同じ整数と合同なのだから、推移律から、rとr'もまた、mod gで合同といえる。
「rとr'は両方ともgより小さいから、mod gで合同なら、この二つは同じ数になる。つまりaとbは、gで割った余りが等しいのだから、mod gで合同ということだ。証明終了！」
「おー、お疲れさーん。アイス食べる？」
「食べる！」
ひと仕事終えて頭をだいぶ使ったし、ホッとしたらお腹も空いてきた。そろそろ作業が終わると察して戻ってきた姉が、わたし用のアイスを持ってきていたので、ありがたく頂く。
メモパッドに書いていたから、数式ばかりが乱雑に書かれている。後でノートに清書しておこう。そしてここで自信を持って、(二元)連立合同式の解が存在するための必要十分条件をまとめる。
x≡a (mod m)
x≡b (mod n)
この連立合同式は、
a≡b (mod gcd(m,n))の時、またその時に限り、
mod lcm(m,n)において解が一つだけ存在する。
う～ん……ひと仕事終えた後のアイス、うまっ。
酷使した頭をクールダウンさせてくれる、アイスの甘味に舌鼓を打っていると、とっくにアイスを食べ終えていた姉が、テーブルの上に置いていたビーズの瓶を手に取った。
「それじゃ、これは忘れないうちにカバンにでも仕舞っておくわ」
「あ、待って、お姉ちゃん。それまだ蓋閉めてない」
部屋に戻ろうとする姉を、わたしは呼び止めた。
その直後に、悲劇は起きた。
ぐにっ。
「痛ったあッ！」
不運にも姉は、どこかから転がってきた、拾い損ねたビーズを踏んづけてしまった。足の裏に激痛が走った姉は跳び上がり、その弾みで、蓋をしていなかったビーズの瓶を、思い切り空中に放り投げた。
瓶から飛び出た1000個近い(正確には1132個の)ビーズが、雹のようにわたしの顔面に叩きつけられる。そして、また床に散らばった。
「…………」
「…………ごめん」
わざとじゃないのは分かっている。でも、糖分の補給が間に合ってないうえに、甘味の摂取と脳のクールダウンを妨げられたわたしは、ブチ切れた。
「掃除機持ってきて全部吸い取れ！ でもって今度はお姉ちゃんだけで数え直し!!」
「ごめんってばぁ～～！」
夕飯の時間を返上して姉が数え直した結果、ビーズは1129個だった。
……惨劇は、なおも続く。
……皆さんも、こまごまとしたものはきちんとまとめて管理するようにしましょう。
さて、ここまで合同式に関する話を長く続けてきましたが、いよいよ次は、合同式が最も威力を発揮する、教科書には載らない整数のある性質について語られます。この時のために、合同式の基本的な性質やオイラーの定理について、長々と説明してきたのです。Day.7から張り巡らせた伏線を、ようやく回収する時が来ました。
というわけで、次回の更新を待たれよ。
