互いに素に関する問題【藤田保健衛生大・関西医科大・学習院大】

Contents

互いに素に関する問題3

2017年関西医科大・改$n$ を自然数とするとき，1から $n$ までの自然数で $n$ と互いに素であるものの個数を $f(n)$ と表す。このとき，$f(29)=\myhako$ であり，$f(2017)=\myhako$ である。また，$f(29\times2017)=\myhako$ である。

【考え方と解答】
$f(29)$ は29以下の自然数のうち，29と互いに素であるものの個数を表す。29は素数であるから1から28までのすべての整数と互いに素である。よって，$f(29)=28$
$f(2017)$ は2017以下の自然数のうち，2017と互いに素であるものの個数を表す。2017も素数であるから1から2016までのすべての整数と互いに素である。よって，$f(2017)=2016$

ヒロ

2017が素数であることがすぐに分かるかどうかで，解くまでの時間が変わる。

ヒロ

次のことを知っておくと良いだろう。

素数判定ある整数 $n$ が素数であるかを調べるときは，$n$ を $\sqrt{n}$ 以下の素数で割ったときに割り切れなければ，$n$ は素数である。

【2017の素数判定】
$44^2=1936,~45^2=2025$ であるから，$44<\sqrt{2017}<45$ したがって，2017を43以下の素数で割って割り切れるものを調べる。43以下の素数は

\begin{align*} 2,~3,~5,~7,~11,~13,~17,~19,~23,~29,~31,~37,~41,~43 \end{align*}

であり，2017をこれらの数で割っても，すべて割り切れることはないから，2017は素数であることが分かる。【最後の問題の考え方と解答】 $29\times2017$ 以下の自然数全体の集合を $A$ とする。$A$ の中に29の倍数は2017個あり，2017の倍数は29個ある。また，29と2017の公倍数は $29\times2017$ の1個だけであるから

\begin{align*} f(29\times2017)&=29\times2017-2017-29+1 \\[4pt] &=(2017-1)(29-1) \\[4pt] &=2016\times28 \\[4pt] &=56448 \end{align*}