PieceCHECK(2023-15) 互いに素な自然数の個数
いつもご覧いただきまして、ありがとうございます。KATSUYAです。
お知らせ
拙著シリーズ『Principle Piece 数学B・C～数列～』販売開始しました！
YouTube動画をUPしました。今回は一橋大学からで、互いに素な自然数の個数を求める問題です。
思考時間は5分、目標解答時間そこから約15分です。
こちらの記事では、動画の中で紹介した解説(答え)を少し丁寧にした答案を、静止画像にて掲載しておきます。
解答
解説
１～ｎのうち、ｎと互いに素である自然数の個数を題材にした問題です。
よくある題材ですが、(3)はとある背景を知っていると因数分解に気づけるので、かなり素早く解くことが出来ます。
言い換えると、nを素因数分解したうえで、その素因数を持たない(その倍数でない)数字を数えるということです。
(1)はいいでしょう。$${1024=2^{10}}$$は数学を受験するなら必須です。2しか素因数を持っていないので、奇数であればOK。
(2)は$${2015=5・13・31}$$となります。13、31は気づきにくいですが、年度の数字を題材にした問題は出ますので、受験年度の素因数分解は覚えておくべきでしょう。
求めるものは、5でも13でも31でも割り切れないものの個数です。補集合の出番ですね。
「・・・でも・・・でも～ない」の構文→補集合で考えよ
3つの集合の和集合を考え、全体から引くパターンです。ここまでは傍ら問題集レベルでしょう。
(3)は文字になりましたが、素因数は2つしかないので、(2)のときよりも式はラクです。あとは、$${\displaystyle \frac{E(n)}{n}}$$が因数分解出来ることに気づけると、p≧2、q≧3だけから簡単に示すことが出来ます。
1～nまでのうち、nと互いに素であるものの個数はオイラー関数と呼ばれます。大学入試でも頻出の題材で、計算式１発で出すことが出来ます。
下は、$${n}$$が3つの素因数$${p,q,r}$$から成る場合の例です。
これにより、(1)は$${1024×\left(1-\displaystyle \frac{1}{2}\right)}$$、(2)は$${2015×\left(1-\displaystyle \frac{1}{5}\right)\left(1-\displaystyle \frac{1}{13}\right)\left(1-\displaystyle \frac{1}{31}\right)}$$で簡単に計算出来ます。検算に使えますね＾＾
(3)のように素因数に指数が入っていても同じです。素因数の種類が2つしかなければ、互いに素な自然数の個数は$${n×\left(1-\displaystyle \frac{1}{p}\right)\left(1-\displaystyle \frac{1}{q}\right)}$$となります。できます。今回はそれをｎで割っていますので、割合になっているだけです。この知識を持っていると、むしろ解答のように因数分解するのが自然というわけです。
同じ考え方の問題が同じ一橋大で出題
ところで、こちらの問題は文章も短く、内容の分かりやすさから多くのチャンネルで取り上げられて話題になったため、記憶に新しいと思います。2021年の一橋大学の問題で、1000以下の素数が250個以下であるというものです。
こちらの問題は、「素数なら少なくとも2,3,5で割り切れないけど、それがだいたい全体の$${\displaystyle \frac{4}{15}\right)}$$ぐらいあるので、そこからさらに素数でないものを削る」という方針で求められます。
全体のうちどれぐらいあるかを計算するのに、オイラー関数を知っていると簡単に求められるわけです。2,3だけで割り切れないものは、まさに今回出したように、$${\bm{\displaystyle \frac{1}{3}\right)}}$$の割合で存在します。これだと250個まで減らすのはメンドウだとすぐにわかります。
なお、こちらの問題もオイラー関数によって、1000ではなく1050(2,3,5,7の公倍数)までで、2,3,5,7で割り切れないものが240個と簡単に出せます。
同じ大学が、(見た目こそ違うように見えますが)たった6年のブランクで同じ分野の、同じ考え方で解ける問題を出題することがあるわけです。
過去問はただ解いて終わりではなく、こういった背景まできちんと研究できているかどうかで差がつくことがよくわかる問題でしたね。
こちらのサイトでは、私が毎年入試数学の講評をしています。背景あるものは出来る限り書いていますので、ぜひ参考にしてみてください。
・古い年度のものはこちらのサイトです。
新しい年度(目安：2016年度以降)のものはこちらで講評しています＾＾
１．解けた人・・・今後の勉強はじっくり演習をしましょう。
２．解けなくて原則を知っていた人・・・拙著『Principle Piece』シリーズで該当するページを熟読し(詳細が書いてあります)、入試演習用の問題集で思考時間を長くする演習をしましょう。
３．解けなくて原則も知らなかった人・・・原則集めからやる必要があります。拙著『Principle Piece』シリーズのような原則習得タイプの問題集で演習しましょう。
Piece CHECKシリーズは、出来あがった答案からは見えない部分を解説していくことで、「なぜそうやって解くのか」「いったいどこからそんな答案が生まれるのか」が分かることを意識して書き上げた参考書です。
関連する拙著『Principle Piece』シリーズ
https://note.com/principle_piece/n/nf90a10941a4e
大手ネットショップBASEでも、デジタルコンテンツとして販売しています。
※ここより先には内容はございません。本記事に価値を感じていただけた方は、ポチっとしていただけると大変うれしいです。(もちろん、任意です)
ここから先は
¥ 100
この記事が気に入ったらサポートをしてみませんか？