数学｜N進数表記のポイント｜受講生の質問と東大「理三」合格講師の回答

Q 「1188の全ての約数の積を2進数で表した時に末尾に0が何個続くか」

A この問題には２つポイントがあります。まず１つ目のポイントは、

「末尾に0が何個続くか」がその数字のどのような特徴を表しているのかを考えるところです。そのために、実験をしてみましょう。例えば2進数表記で「11000」と表される数字を10進法に直すときに、まず「1×2^4+1×2^3+0×2^2+0×2^1+0×2^0」を計算しますね。これを計算してしまわずに一歩踏みとどまってみましょう。

この数字では末尾に0が3個続きますが、この0によって上式の2^2以下の部分は全て消えてしまい、2^3以上の部分だけ残ることが観察できます。さらに「2^3以上だけ残る」という性質は、この数が「2^3で割り切れる」ことを意味しませんか？2^3より上の2^4とかの部分はもちろん2^3で割り切れますし、もし2^2以下の項が残っていれば2^3で割ってもその分だけ余りが出てしまいますもんね。

しかしこの「2^3で割り切れる」だけでは足りません。それだけだと、例えば「末尾に0が4個続く数」は2^4以上の項だけ残るので、これも含まれてしまうからです。ではそれを排除するためにはどうすればいいかというと、単純に「2^4では割り切れないが2^3で割り切れる」としてしまえば良いです。こうすれば末尾に0が3個続くもの以外を全て排除できますからね。さてこれをもう1回言い換えると、「2で3回割り切れる」となります。（「mでn回割り切れる（割れる）」という表現は慣例的に「mでn回割り切れるがn+1回は割り切れない」ことを意味します）

まとめると、「2進数表記で末尾に0が3回続く数」は「2で3回割り切れる数」ということになりそうですね。同じように考えれば以上のことを一般化できて、「ある数の2進数表記の末尾の0の個数は、その数が2で何回割り切れるかを表す」ことがわかります。そうなれば問題が少し簡単になり、本問は「1188の全ての約数の積は2で何回割り切れるか」を考えればいいことになりますね。もちろん1188の全ての約数を書き出してそれぞれの2で割り切れる回数を求めてそれを全て足し合わせてあげれば良いのですが、それはめんどくさいと思ったら次のようにするといいでしょう。

２つ目のポイントは、

素因数分解を考えることです。なぜそうなるかというと、なんの根拠もなく小さい方から約数を書き出すよりは、「2で何回割り切れるか」で約数を分類するのが良さそうですよね。すると、例えば「1188の約数のうちで2で1回割り切れるものの個数」などを考えることになります。ここで思い出されるのが、「約数の個数は素因数分解した際の各々の指数に1を足したものを全てかけたもの」という基本的な事実です。

素因数分解してみると約数の個数についての情報がわかりそうなのでとりあえずやってみると、1188=2^2・3^3・11^1となります。約数というのは、この素因数である2個の2、3個の3、1個の11から自由に取って組み合わせることによって作られますね。そう考えると、2でn回割り切れる約数は2をn個取ってきた約数ということになり、その個数は残りの3と11からどう取ってくるかの組み合わせの数だけあることがわかります。この3と11から取ってくる組み合わせはもちろん(3+1)(1+1)=8通りで、今回2は2個までしか取ってこれないので、「2で2回割り切れる約数」と「2で1回割り切れる約数」と「2で0回割り切れる（つまり割り切れない）約数」がそれぞれ8個あることになります。よって、これら全ての積が2で割り切れる回数は(2+1+0)×8=24となります。

ちなみに、10進数で考えると末尾の0の個数が10で何回割り切れるかを表すのは当たり前ですね。1回10で割ると一番下の0が消えてそれより上の部分が残るからです。N進数の場合も1回Nで割ると一番下の0が消えて上の部分が残ります。N進数の世界でN自身は「10」と表されるので10進数の世界で10で割るときと同じようにしていいからです。

【受験戦略・勉強法・勉強計画のまとめコンテンツのご案内】受験戦略や各教科の勉強法、勉強計画のまとめ記事については公式サイトのコンテンツ群
大学受験対策の総合サイト ▶　をご覧ください。

■大学受験のカラクリの分析解明、受験戦略、国・私大対策の勉強計画、各教科の勉強法を網羅
■多くの医学部・東大・旧帝大・難関国立・早慶合格者が熟読している受験戦略本
■大学受験勉強法本の決定版
あなたの第一志望校合格可能性を大きく高める
難関大学受験生必読の書

『あなたの第一志望校合格可能性を最大限に高められる
これ以上の指導は存在しない』
という指導を追求・実現した大学受験のネット塾＆リアル塾

（株）合格の天使　公式サイト ▶