中学生でも解ける外伝 高校入試難問69★★ 渋谷教育学園幕張高
↓ここからカテゴリー別に記事を見ることができます。↓
新年になったので、高校入試が終わるまで高校入試の難問を紹介することにします。
↓↓↓ 去年もやっています ↓↓↓
問題
★★
正の整数xに対して、1からxまでの整数のうち、xとの最大公約数が1であるものの個数をf(x)とおく。
例えば、f(5)は、1から5のうち5との最大公約数が1であるものは1,2,3,4の4つであるからf(5)=4である。
f(6)は、1から6のうち6との最大公約数が1であるものは1,5の2つであるからf(6)=2である。次の各問に答えよ。
(1) f(15)、f(16)、f(17)をそれぞれ求めなさい。
(2) p、qを互いに異なる素数とするとき、
① f(p) をpを用いて表しなさい。
② f(pq) をp、qを用いて表しなさい。
③ f(pq) をf(p)、f(q)を用いて表しなさい。
ヒント、着眼点
(1)は時間を書ければ誰でもできるので省略。
(2) どうすれば分からないときは実際にp,qを具体的な素数に置き換えて計算してみるのがよいでしょう。何なら、p=3,q=5の場合は(1)で結果を出しているので、これをみてヒントを得るのもよいです。
以下、解答
解答
(1) f(15)=8, f(16)=8, f(17)=16
(2) ① f(p)=p-1 ② f(pq)=pq-p-q+1 ③ f(pq)=f(p)f(q)
解説
(1)
15と互いに素なのは、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
の8つなので、f(15)=8
16と互いに素なのは、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
の8つなので、f(16)=8
17と互いに素なのは、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17
の16つなので、f(17)=16
(2)
① f(p)は、f(17)の結果で推測できます。1からp-1まで全てpとの最大公約数が1なので、
f(p)=p-1
② p,qは互いに異なる素数であることに注意します。あえてpqと最大公約数が1でない個数を数えます。
p=3,q=5の具体例から見てみます。pq=15なので、15と最大公約数が1でない自然数は、必ず3か5で割り切れるはずです。
まず、p=3の倍数は、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
5個あります。この5個というものは、
15÷3=5
としても出ます。つまりpq÷p=q個ということです。同様にq=5の倍数の個数は、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
3個あります。15÷5=3個です。ここで、15という数だけどちらにも登場していることに注意します。pqはpの倍数でもqの倍数でもあります。
これを一般化すれば、次が言えます。
pqと最大公約数が1でない数はpの倍数であるか、qの倍数である。
1からpqまでの整数のうち、pの倍数はq個、qの倍数はp個ある。pの倍数でもqの倍数でもある数は1つだけある。
1からpqまでの整数のうち、pqと最大公約数が1でないものの個数は (p+q-1)個
1からpqまでの整数のうち、pqと最大公約数が1であるものの個数は
pq-(p+q-1)=(pq-p-q+1)個
よって、f(pq)=pq-p-q+1
③ ①の結果から、
f(p)=p-1...ア
f(q)=q-1...イ
ここで、②の答えを因数分解すると、
f(pq)=pq-p-q+1=(p-1)(q-1)
ア、イを代入して、
f(pq)=f(p)f(q)
(ちなみにこの答えが正しそうであることは、f(15)=8, f(3)=2, f(5)=4だからf(15)=f(3)f(5)が成り立つことを確認すればわかる。)
なかなか興味深い互いに素という性質にまつわる問題でした。p,qという文字を使った表記に慣れていないと厳しいかもしれません。
参考① 互いに素な自然数の個数を求める公式
全ての自然数に対して、互いに素な自然数の個数を求める公式が存在します。
自然数nに対して、
と表されたとき、n以下のnと互いに素な自然数の個数は、
である。
これを知らなくても何の問題もありませんが、覚えておくとどこかで役に立つかもしれません。
この式を見てすぐわかることは、
互いに素な自然数の個数は、どんな素因数を持つかによって決まるのであり、同じ素因数をいくつ持つかによらない
ということです。これはかなり重要な整数の性質です。
参考② オイラーのφ関数
この問題に登場したf(x)というものは、オイラーのφ関数という名前でよく知られているものです。参考までに、φ(n)の最初の1000個の値を見てみましょう。
参考①で見たように、どんな素因数を持つかによって(同じ素因数をいくつ持つかにはよらない)φ(n)の値が決まるので、同じ種類の素因数を持つnは一列に並びます。
グラフの一番上に見える直線は素数が並んでいることや、直線 付近に多く点が集まっているであることなども分かります。
前回
次回
written by k