ねとらぼで高校生の解いた数学の問題が話題になっていて、ちょっと面白かったので記事にしてみます。当該の問題はタイトルの通り「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」である。

が計算できました。以上!

 

シリーズ記事執筆中!特集記事一覧

初心者おすすめのDJ機材からDJたちの歴史、これからのDJについて初心者おすすめのDJ機材、DJコントローラーからDJたちの歴史、これからのDJについて ロードバイク買ってみた!おすすめパーツやメンテナンスロードバイクやクロスバイク買ってみたからカスタムしてみた
Taicoclub(FFKT)からGOOUT、朝霧JAM参戦日記Taicoclub(FFKT)、GOOUT、朝霧JAMなどのキャンプフェスから登山まで 新しいDIY同人誌“ZINE”の歴史や作り方について
- DJはじめるなら、安心のDJスクールへ ! -無料レッスンはこちら