本記事にはアフィリエイトリンク広告が含まれています。
ねとらぼで高校生の解いた数学の問題が話題になっていて、ちょっと面白かったので記事にしてみます。当該の問題はタイトルの通り「20の13乗を18で割った余りを求めよ」という問題なんだけれども、解いた本人の回答がこちら。
こういうのものすごく好きなんだけど、マジレスすると、こういうビジュアライズする才能があるひとは、デザイナーっていうよりアートディレクターとかすごく向いてると思いますね。
さて、この解答も面白いのだけれども、真面目に解くとどうなるんだろう?と思って少し考えてみることにしました。
頑張って20の13乗を計算する
いざ20の13乗を計算しようと思うと、13が絶妙に素数となっており、計算しにくくて良問といった感じですが、電卓を使って計算してみると、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/d1288201f8032556f2c1b73ff2004e8c.png?resize=696%2C55&ssl=1)
となるので、これを18で割ると
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/dc8f70e7fed83c43dd62ecb57f0c53e8.png?resize=696%2C44&ssl=1)
つまり、余りは2となります。ただし高校数学の場合、20の13乗を計算するのはテスト時間が勿体無いので、もっとスマートな解き方があるはず。あ〜こういうの苦手だったわ高校時代。
20の累乗の徐算に規則性はあるか?
ちょっと工夫するために20の1乗からはじめて、13乗までを考えて、そこから規則性を導きだせば、もうちょっと素早く計算できるはず。ということで、いくつか計算してみることにします。ちなみに、0乗というのは数学の定義上1なので都合が悪いため、今回は1から始まる自然数の累乗を考えます。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_3.png?resize=300%2C280&ssl=1)
これをそれぞれ18で割っていくと、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_4.png?resize=600%2C211&ssl=1)
となっていくところを見ると、いい感じの等比数列{2, 4, 8, 16, ・・・}になっていそうだし、これは規則性がありそうにも見えます。ただし、割る数(数学的には「法」と呼ぶ)が18なんで、余りが18を超えることはないはず。
よく見ると、20の累乗から0を省いた数が余りと一緒になりそう。ということは次の「20の5乗」は「3,200,000」だから、32と関係のある数字が出てきそうな気がしますね。ちなみに、32をさらに18で割ると1余り14。実際に計算してみると、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_5.png?resize=600%2C80&ssl=1)
となり、20の6乗を18で割ったときの余り「10」も、64を18で割ったときの余り「10(商は3)」と等しい。20の累乗からゼロを省いた数を並べると、{2, 4, 8, 16, 32, 64, 128, 256, ・・・}となっていくはずだけど、これはよく見たら2の累乗だ。ということはつまり、13番目に来るのは、2の13乗。これは手で計算できるレベル。つまり、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_6.png?resize=600%2C47&ssl=1)
となる。つまり「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乗はおそらくこんな形をしているはず。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_7.png?resize=529%2C76&ssl=1)
20の13乗は巨大な数になるはずだから、aはとても大きな自然数になる。一方で、bは余りなので、1から17の自然数(正確にはさっき確認した2, 4, 8, 10, 14, 16)のうちのいずれかになるはず。
そして「18a」という形をつくるために20を13乗する前に「18を含めるかたち」をつくってしまうことで、13乗した後に18がたくさん出てくる形を考えれば良い。つまり、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_8.png?resize=615%2C96&ssl=1)
というかたちに変形してしまえば、二項展開で18がたくさん出現して、割り算しやすくなるはずだ。この変形式を展開してみると、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_9.png?resize=600%2C184&ssl=1)
最後の項以外は全部18が含まれているはずなので、18でまとめてしまえば、18a+bの形に近づく。さらに、最後の項には先ほど出現した「2の13乗」も現れました。18でまとめられる部分は、18で割り切れるので、余りだけを考える場合は「2の13乗を割ることで、同等の計算」としても良いという結果に。
あとはさっきと同じ要領。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_6.png?resize=600%2C47&ssl=1)
となるはずなので、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_7.png?resize=529%2C76&ssl=1)
のb、つまり18で割ったときの余りは「2」となります。よって
「20の13乗を18で割ったときの余り」は「2」である。
ちなみに、2の13乗も下記のように展開できます。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_10.png?resize=600%2C232&ssl=1)
なので2の13乗も計算する必要なくて、2の13乗が「(18-2)の3乗×2」であることに気づくと、さらに計算が早くなります。最後の18で割り切れない項「16」を18で割ってあげると、余りは同じく「2」ですね。
合同式として解く
もっとシンプルにする方法は無いか考えていたのですが、そもそもこの「割った余りを計算せよ」という問題そのものが、整数の合同式として解けということを指しているのでは・・・と思ったのだけれども、なかなか思い出せなくて、苦労しました。
合同式は、特定の数(これを割る数、つまり「法」)で割った余りの数が同じなら、元の数は同じ(合同)とみなしても良いよ、という計算方法。例えば、今回の問題でいうと18を法としたとき、19は余り1、37も余り1なので、合同と言えます。これは下記のような式に表すことが可能です。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_11.png?resize=633%2C96&ssl=1)
上の式は37よりも19のほうが計算しやすいので、大きな数を左にもってきて、もう一方に小さな数をもってこれれば、巨大な計算をする手間が省ける。つまり
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_12.png?resize=600%2C90&ssl=1)
上の、最も計算がラクな(小さい)形のxを探してから、余りを計算すればラクなんじゃないかと。とまあ、ここまで読んだ方はお察しと思いますが、2の13乗っぽいですね。
20は18で割ると2、2も18で割ると2になるから「18を法としたときに20と2は合同」と言える。ここから発展して、「20の13乗と2の13乗が合同」だと計算がしやすくて非常に助かる。というわけで、a, b, nが整数のとき、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_13.png?resize=600%2C66&ssl=1)
が証明できれば良い。実際の高校数学では、証明されていて自明なものとして進めても良いっぽいですが、計算してみましょう。前提条件として「aとbは合同」なので、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_14.png?resize=600%2C59&ssl=1)
であることが言えます。ここからaのn乗とbのn乗を考えてみると、上のように、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_15.png?resize=600%2C50&ssl=1)
と展開していけるので、これを計算してみると、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_16.png?resize=600%2C117&ssl=1)
無事証明できました。つまり、「2と20は18を法として合同」よって「2と20それぞれをn乗した場合も合同」。これを式に表すとこうなる。
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_17.png?resize=600%2C40&ssl=1)
よって20の13乗を18で割ったときの余りは、2を13乗したときの余りと同じであるから、
![](https://i0.wp.com/www.naka-chang.net/wp-content/uploads/2018/08/2013_6.png?resize=600%2C47&ssl=1)
となり、
「20の13乗を18で割ったときの余り」は「2」である。
が計算できました。以上!