次のような頻出問題をどう解くかというのが今回のテーマです。
1から100までの整数のうち、3でも5でも割り切れない整数は全部で何個ありますか。(普連土2022算数)
このタイプの問題はベン図で考えるのが定石です。
「3でも5でも割り切れない整数」の個数は、「3または5の倍数」の個数を全体から引くことで求められる。
❶100までに3の倍数は33コ(100÷3=33あまり1)、5の倍数は20コ(100÷5)ある。
❷3と5の公倍数(=15の倍数)が6コある(100÷15=6あまり10)ことに注意する。
❸「3または5の倍数」は33+20-6=47コある(重なり❷を忘れずに引く)。
❹よって「3でも5でも割り切れない整数」の個数は100-47=53コ
ここからが本題ですが、このような「AでもBでも割り切れない数の個数」問題のなかには、オイラー関数の考え方を知っているとより早く正解にたどりつけるものがあります。
たとえば次のような問題。
オイラー関数が使えるパターン(帝京2022)
1から200までの整数のなかで、4でも5でも割り切れない数は▢個あります。
200× ¾ × ⅘ = 120個
「オイラーのファイ関数」というものをベースにした考え方ですが、その仕組みをざっくり説明すると次のとおり(規則性を学習した小学生なら理解できるはずです)。
「4で割り切れる数は4コに1コ、規則的にあらわれる。逆に4で割り切れない数は4コに3コ、規則的にあらわれる。同じように5で割り切れない数は5コに4コ、規則的にあらわれる。
そこで1から20までの20コ(4と5の最小公倍数)を考えると
20×¾×⅘=12
という計算で、20コ中12コが4でも5でも割り切れない数だとわかる。この規則性は1から200(4と5の公倍数)までに広げてもそのまま利用できる。」
ポイントは2点あり、①「4でも5でも」の4と5のように割る数は互いに素(公約数を持たない)であること、②「1から200まで」のように範囲は1からある公倍数ちょうどまでであることです。原則として、この2つの条件がそろったときだけオイラー関数が使えます。
少し工夫すればオイラー関数が使えるパターン(金蘭千里2018前期A)
1から100までの整数のうち、5でも7でも割り切れない整数は▢個ある。
冒頭の問題とほぼ一緒の問題です。オイラー関数が使える2条件のうち、①(互いに素)は問題ないが、②(公倍数ちょうどまで)をクリアしておらず、ベン図で考えるのが原則となります。
ただ、いったんその範囲を公倍数ちょうどまで広げれば、やはりオイラー関数の考え方が使えます。
問題文「1から100までの整数」をいったん「1から105までの整数」(105は5と7の公倍数)に広げて考える。すると
105× ⅘ × ⁶⁄₇ =72
より「5でも7でも割り切れない整数」は「1から105まで」のなかに72個ある。そして101から105までのなかに「5でも7でも割り切れない整数」が4コ含まれている(101、102、103、104。5の倍数は100→105、7の倍数は98→105と飛ぶため)のでこれを除くと 68個
オイラー関数の考え方を規則性の考え方に取り込んで使うパターン(早稲田中2021)
1から2021までの整数の中で、12でも18でも割り切れない整数は何個ありますか。
12と18は互いに素ではないのでオイラー関数はそのままでは使えず、その考え方だけ借用します。
1から36(12と18の最小公倍数)までに12で割り切れるのが3コ、18で割り切れるのが2コあるから、12または18で割り切れる数は 3+2-1(重なり)=4コ ある。この残り32コが割り切れない個数。つまり「12でも18でも割り切れない整数」は、36コ中に32コ、規則的にあらわれる。
そこで2021にいちばん近い36の倍数を探すと、2021÷36=56あまり5より、まずは2016(=36×56)までに「12でも18でも割り切れない整数」は何個あるかを計算すると
2016× ³²⁄₃₆ =56×32=1792コ
そして2017から2021までの数はすべて「12でも18でも割り切れない整数」なので(12の倍数は2016→2028、18の倍数は2016→2034と飛ぶため)この5コを足して 1797個