本記事にはアフィリエイトリンク広告が含まれています。
ねとらぼで高校生の解いた数学の問題が話題になっていて、ちょっと面白かったので記事にしてみます。当該の問題はタイトルの通り「20の13乗を18で割った余りを求めよ」という問題なんだけれども、解いた本人の回答がこちら。
こういうのものすごく好きなんだけど、マジレスすると、こういうビジュアライズする才能があるひとは、デザイナーっていうよりアートディレクターとかすごく向いてると思いますね。
さて、この解答も面白いのだけれども、真面目に解くとどうなるんだろう？と思って少し考えてみることにしました。
頑張って20の13乗を計算する
いざ20の13乗を計算しようと思うと、13が絶妙に素数となっており、計算しにくくて良問といった感じですが、電卓を使って計算してみると、
となるので、これを18で割ると
つまり、余りは2となります。ただし高校数学の場合、20の13乗を計算するのはテスト時間が勿体無いので、もっとスマートな解き方があるはず。あ〜こういうの苦手だったわ高校時代。
20の累乗の徐算に規則性はあるか？
ちょっと工夫するために20の1乗からはじめて、13乗までを考えて、そこから規則性を導きだせば、もうちょっと素早く計算できるはず。ということで、いくつか計算してみることにします。ちなみに、0乗というのは数学の定義上1なので都合が悪いため、今回は1から始まる自然数の累乗を考えます。
これをそれぞれ18で割っていくと、
となっていくところを見ると、いい感じの等比数列｛2, 4, 8, 16, ・・・｝になっていそうだし、これは規則性がありそうにも見えます。ただし、割る数（数学的には「法」と呼ぶ）が18なんで、余りが18を超えることはないはず。
よく見ると、20の累乗から0を省いた数が余りと一緒になりそう。ということは次の「20の5乗」は「3,200,000」だから、32と関係のある数字が出てきそうな気がしますね。ちなみに、32をさらに18で割ると1余り14。実際に計算してみると、
となり、20の6乗を18で割ったときの余り「10」も、64を18で割ったときの余り「10（商は3）」と等しい。20の累乗からゼロを省いた数を並べると、｛2, 4, 8, 16, 32, 64, 128, 256, ・・・｝となっていくはずだけど、これはよく見たら2の累乗だ。ということはつまり、13番目に来るのは、2の13乗。これは手で計算できるレベル。つまり、
となる。つまり「2の13乗を18で割ったときの余り」である「2」は、「20の13乗を18で割ったときの余り」でもあるから、
「20の13乗を18で割ったときの余り」は「2」である
と解ける。
ただ、この解法もあんまりイケているとは言いづらい。というのもこの書き方だと、20の13乗と2の13乗の関係性について「18で割ると余りは必ず同じになる」ということを自明のこととして計算しているから（後から計算したら実際そうだったけど）、何らかの証明が必要かなとも思う。
二項定理の計算問題として解く
もう少し頭を使って、「どうにかして20の13乗から2の13乗を導き出して、ラクして解く」という解法を考えたい。
ところで、「20の13乗を18で割った余りを出す」ということは、20の13乗の大部分は18で割れると考えて良いということだ。つまり、20の13乗はおそらくこんな形をしているはず。
20の13乗は巨大な数になるはずだから、aはとても大きな自然数になる。一方で、bは余りなので、1から17の自然数（正確にはさっき確認した2, 4, 8, 10, 14, 16）のうちのいずれかになるはず。
そして「18a」という形をつくるために20を13乗する前に「18を含めるかたち」をつくってしまうことで、13乗した後に18がたくさん出てくる形を考えれば良い。つまり、
というかたちに変形してしまえば、二項展開で18がたくさん出現して、割り算しやすくなるはずだ。この変形式を展開してみると、
最後の項以外は全部18が含まれているはずなので、18でまとめてしまえば、18a+bの形に近づく。さらに、最後の項には先ほど出現した「2の13乗」も現れました。18でまとめられる部分は、18で割り切れるので、余りだけを考える場合は「2の13乗を割ることで、同等の計算」としても良いという結果に。
あとはさっきと同じ要領。
となるはずなので、
のb、つまり18で割ったときの余りは「2」となります。よって
「20の13乗を18で割ったときの余り」は「2」である。
ちなみに、2の13乗も下記のように展開できます。
なので2の13乗も計算する必要なくて、2の13乗が「（18-2）の3乗×2」であることに気づくと、さらに計算が早くなります。最後の18で割り切れない項「16」を18で割ってあげると、余りは同じく「2」ですね。
合同式として解く
もっとシンプルにする方法は無いか考えていたのですが、そもそもこの「割った余りを計算せよ」という問題そのものが、整数の合同式として解けということを指しているのでは・・・と思ったのだけれども、なかなか思い出せなくて、苦労しました。
合同式は、特定の数（これを割る数、つまり「法」）で割った余りの数が同じなら、元の数は同じ（合同）とみなしても良いよ、という計算方法。例えば、今回の問題でいうと18を法としたとき、19は余り1、37も余り1なので、合同と言えます。これは下記のような式に表すことが可能です。
上の式は37よりも19のほうが計算しやすいので、大きな数を左にもってきて、もう一方に小さな数をもってこれれば、巨大な計算をする手間が省ける。つまり
上の、最も計算がラクな（小さい）形のxを探してから、余りを計算すればラクなんじゃないかと。とまあ、ここまで読んだ方はお察しと思いますが、2の13乗っぽいですね。
20は18で割ると2、2も18で割ると2になるから「18を法としたときに20と2は合同」と言える。ここから発展して、「20の13乗と2の13乗が合同」だと計算がしやすくて非常に助かる。というわけで、a, b, nが整数のとき、
が証明できれば良い。実際の高校数学では、証明されていて自明なものとして進めても良いっぽいですが、計算してみましょう。前提条件として「aとbは合同」なので、
であることが言えます。ここからaのn乗とbのn乗を考えてみると、上のように、
と展開していけるので、これを計算してみると、
無事証明できました。つまり、「2と20は18を法として合同」よって「2と20それぞれをn乗した場合も合同」。これを式に表すとこうなる。
よって20の13乗を18で割ったときの余りは、2を13乗したときの余りと同じであるから、
となり、
「20の13乗を18で割ったときの余り」は「2」である。
が計算できました。以上！
