日比谷高校のススメ

日比谷高校出身者たちが日比谷高校の紹介や、勉強に関する様々なことを語ります。

中学生でも解ける外伝 高校入試難問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...ア

素数pを素数qに取り換えても同様に成り立つから、

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=p^a\times q^b\times r^c\times\dots

と表されたとき、n以下のnと互いに素な自然数の個数は、

n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})\dots

である。

 

これを知らなくても何の問題もありませんが、覚えておくとどこかで役に立つかもしれません。

この式を見てすぐわかることは、
互いに素な自然数の個数は、どんな素因数を持つかによって決まるのであり、同じ素因数をいくつ持つかによらない
ということです。これはかなり重要な整数の性質です。

 

参考② オイラーのφ関数

この問題に登場したf(x)というものは、オイラーのφ関数という名前でよく知られているものです。参考までに、φ(n)の最初の1000個の値を見てみましょう。

f:id:hby:20191231154212p:plain

*1

 

参考①で見たように、どんな素因数を持つかによって(同じ素因数をいくつ持つかにはよらない)φ(n)の値が決まるので、同じ種類の素因数を持つnは一列に並びます。

グラフの一番上に見える直線は素数が並んでいることや、直線y=\frac{1}{2}x 付近に多く点が集まっているであることなども分かります。

f:id:hby:20191231155527p:plain

 

 

 

 

 

前回

68★ 早稲田実業高

次回

70★★★ 巣鴨高

 

 

written by k

Copyright © 2017 日比谷高校のススメ All rights reserved.