正の整数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

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

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

f:id:hby:20191231155527p:plain

前回

６８★ 早稲田実業高

次回

７０★★★ 巣鴨高

written by k

*1:「オイラーのφ関数」『フリー百科事典　ウィキペディア日本語版』https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0

2020-01-02

中学生でも解ける外伝高校入試難問６８★ 早稲田実業高

中学生でも数学

新年になったので、高校入試が終わるまで高校入試の難問を紹介することにします。

↓↓↓ 去年もやっています ↓↓↓

３０★★　巣鴨高

３５★　　灘高

３６★★★巣鴨高

３８★★　都立西高

問題
★

nは自然数とする。 $P=n^2+10n-56$ が素数となるとき、Pの値を求めよ。

ヒント、着眼点

整数問題、特に素数が絡む問題はたいてい因数分解します。

$P=n^2+10n-56=(n-4)(n+14)$

とできます。

以下、解答

解答

P=19

解説

$P=n^2+10n-56=(n-4)(n+14)$

ここで、nは自然数だから、P=(n-4)(n+14) が素数となるためには、

n-4=1, n+14=(素数)

となるしかない。このときn=5, n+14=19となって、P=19

初回なので優しめの問題。2014年度の小問からでした。

前回

６７★★ 2016年埼玉大

次回

６９★★ 渋谷教育学園幕張高

written by k

2020-01-01

【数学小話】３：４：５の直角三角形の鋭角は何度？

数学小話数学

3辺が全て整数である直角三角形の最初の例として有名な3:4:5の直角三角形。1:1:√2とか1:2:√3とか、鋭角が特別な値なものも習いますが、この3:4:5の直角三角形は鋭角が何度であるかは中学校では一切触れられません。今回は高校数学までの知識で、この角度を考察していきます。

f:id:hby:20191216123635j:plain

問題. 上の図におけるθは何度だろうか？

1. (整数)度

2. 整数ではなく、(有理数)度

3. (無理数)度

答えは3です。角度は(無理数)度です。ちなみに、θ≒53.130102354...度です。

方針、下準備
証明
- step1
- step2 補題
- step3
考察他の整数比の直角三角形

方針、下準備

度数法で $\theta=(\frac{n}{m})°$ と表されるとき、弧度法では $\theta=\frac{n}{180m}\pi$ となるので、改めて $\frac{q}{p}=\frac{n}{180m}$ と置きなおして、
$\theta=\frac{q}{p}\pi$ とします。これで、
「θが(無理数)度」=「θは(無理数)×πラジアン」
であることが確認できました。これからは弧度法で考えていきます。

証明の方針としては、
$\theta=\frac{q}{p}\pi\ (p,\ qは互いに素な整数)$ と書けたと仮定し、矛盾を導きます。

$\theta=\frac{q}{p}\pi\ (p,\ qは互いに素な整数)$ と書けたとしたら、
$\cos{(p\theta)}=\cos{(p\times\frac{q}{p}\pi)}=\cos{(q\pi)}=\pm1$
となるはずです。qπは(整数)×πなので、cosが±1になるわけです。
ここに矛盾が潜んでいます。

f:id:hby:20191216124528j:plain

また、すぐわかるように、
$\cos{\theta}=\frac{3}{5},\ \sin{\theta}=\frac{4}{5}$
です。ここから出発して、
$\cos{2\theta},\ \cos{3\theta},\ \dots$
の値を求めます。

証明

step1

自然数nに対して、
$a_n=5^n\cos{n\theta},\ b_n=5^n\sin{n\theta}$
と定義する。この2つの数列について漸化式を作る。
このa_n,b_nが常に5で割り切れない整数であることを示す。

初項は、
$a_1=5\cos{\theta}=3,\ b_1=5\sin{\theta}=4$

漸化式を考えたい。
$a_{n+1}=5^{n+1}\cos{(n+1)\theta}\\=5^{n+1}\cos{(n\theta+\theta)}\\=5^{n+1}(\cos{n\theta}\cos{\theta}-\sin{n\theta}\sin{\theta})\\=5^{n+1}(\frac{3}{5}\cos{n\theta}-\frac{4}{5}\sin{n\theta})\\=5^n(3\cos{n\theta}-4\sin{n\theta})\\=3a_n-4b_n$
よって、
$a_{n+1}=3a_n-4b_n...①$

同様にやれば、
$b_{n+1}=4a_n+3b_n...②$

が得られます。実際にa_n,b_nを求めると、このようになります。

f:id:hby:20191216131740j:plain

確かにa_n,b_nは5で割り切れない整数のようです。では数学的帰納法でそれを示します。a_nは常に5で割って3余り、b_nは常に5で割って4余ることに注目しましょう。*1

step2 補題

a_nは常に5で割って3余り、b_nは常に5で割って4余る整数である。

証明

$a_{n+1}=3a_n-4b_n$
$b_{n+1}=4a_n+3b_n$
を用いて、a_nは常に5で割って3余り、b_nは常に5で割って4余ることを数学的帰納法で示す。

n=1のとき、 $a_1=3,\ b_1=4$ より成り立つ。...①
n=kのとき、 $a_k\equiv3,\ b_k\equiv4\ (mod\ 5)$ が成り立つとすると、
n=k+1を考えると、
$a_{k+1}=3a_k-4b_k\equiv9-16=-7\equiv3\ (mod\ 5)\\b_{k+1}=4a_k+3b_k\equiv12+12=24\equiv4\ (mod\ 5)$
より成り立つ。...②

①②より、数学的帰納法から、全てのnについて、a_nは常に5で割って3余り、b_nは常に5で割って4余る。

ということで、a_nは常に5で割って3余り、b_nは常に5で割って4余ることが示されました。ここまできたらあと一歩です。

$a_n=5^n\cos{n\theta}$ より、
$\cos{n\theta}=\frac{a_n}{5^n}$
となりますが、 $a_n$ は5で割り切れない整数なので、全てのnについて、
$\cos{n\theta}=\frac{a_n}{5^n}$
は整数でない有理数です。...(＊)

step3

さて、
$\theta=\frac{q}{p}\pi\ (p,\ qは互いに素な整数)$ と書けたと仮定すると、
$\cos{(p\theta)}=\cos{(p\times\frac{q}{p}\pi)}=\cos{(q\pi)}=\pm1$
となります。しかし、(＊)より、 $\cos{p\theta}$ は整数でない有理数なので、±1と等しくなりえない。よって矛盾。したがって
θ=(無理数)×π
である。

ということで、θは(無理数)度であることが示されました。

考察他の整数比の直角三角形

3辺の比が整数比である直角三角形は他にも無数にあります。

$3:4:5\\5:12:13\\7:24:25\\8:15:17$

などなど。

$m,\ n$ を整数として、
$a=m^2-n^2,\ b=2mn,\ c=m^2+n^2$
とすることで、ピタゴラス数を好きなだけ作ることができることは有名ですが、

どの整数比の直角三角形の鋭角も(無理数)度か？

という疑問が生じます。この予想は正しいのかどうか、皆さんはどう思いますか。

気力があったら続くかも？

次回が出来ました。全ての整数比直角三角形の鋭角が(無理数)度であることを示します。

続３：４：５の直角三角形の鋭角は何度？

written by k

*1:※-7は5で割って3余ります。余りは2ではありません。負の数の割り算の余りについてはめんどくさいのでここでは触れません。

日比谷高校のススメ

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