トップ› 基礎問題› 数学A› 整数問題› オイラーの関数› 問題 2

数学A オイラーの関数問題 2 解説

方針・初手

$f(n)$ は $1,2,\ldots,n$ のうち $n$ と互いに素なものの個数であるから、$n$ の素因数で割り切れる数を除けばよい。

（1）は包除原理で数える。（2）は $f(n)\mid n$ という条件を、素因数分解における $2$ の指数に注目して絞り込む。

解法1

(1)

$N=p^a q^b r^c$ とおく。$p,q,r$ は相異なる素数なので、$N$ と互いに素でない数は、$p,q,r$ の少なくとも1つで割り切れる数である。

$1,2,\ldots,N$ の中で、$p$ の倍数は $N/p$ 個、$q$ の倍数は $N/q$ 個、$r$ の倍数は $N/r$ 個である。

また、$pq,qr,rp,pqr$ の倍数の個数もそれぞれ

$$ \frac{N}{pq},\quad \frac{N}{qr},\quad \frac{N}{rp},\quad \frac{N}{pqr} $$

である。

したがって、包除原理より

$$ \begin{aligned} f(N) &=N-\frac{N}{p}-\frac{N}{q}-\frac{N}{r} +\frac{N}{pq}+\frac{N}{qr}+\frac{N}{rp} -\frac{N}{pqr} \\ &=N\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right). \end{aligned} $$

ここで $N=p^a q^b r^c$ だから、

$$ \begin{aligned} f(p^a q^b r^c) &=p^a q^b r^c\cdot \frac{p-1}{p}\cdot \frac{q-1}{q}\cdot \frac{r-1}{r} \\ &=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1). \end{aligned} $$

よって、

$$ f(p^a q^b r^c)=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1) $$

が成り立つ。

(2)

$f(n)$ が $n$ の約数であるとは、

$$ f(n)\mid n $$

であることを意味する。

まず、$n$ が奇数で $n>2$ のとき、$n$ と互いに素な数 $a$ に対して $n-a$ も $n$ と互いに素である。さらに $n$ が奇数なので $a=n-a$ とはならず、互いに素な数は対になって数えられる。したがって $f(n)$ は偶数である。

いま $5\leqq n\leqq 100$ なので、奇数の $n$ では $f(n)$ が偶数、$n$ が奇数となり、$f(n)\mid n$ は成り立たない。よって $n$ は偶数である。

そこで

$$ n=2^a p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t} $$

とおく。ただし $a\geqq 1$、$p_1,\ldots,p_t$ は相異なる奇素数である。

(1) と同じ考え方により、

$$ f(n)=2^{a-1}p_1^{e_1-1}\cdots p_t^{e_t-1}(p_1-1)\cdots(p_t-1) $$

である。

各 $p_i$ は奇素数なので、$p_i-1$ は偶数である。したがって、$f(n)$ に含まれる $2$ の指数は少なくとも

$$ (a-1)+t $$

である。

一方、$n$ に含まれる $2$ の指数は $a$ である。$f(n)\mid n$ であるためには、$f(n)$ に含まれる $2$ の指数が $n$ に含まれる $2$ の指数を超えてはならないから、

$$ (a-1)+t\leqq a $$

となる。よって

$$ t\leqq 1 $$

である。

つまり、$n$ の奇素因数は高々1種類である。したがって、調べるべき形は

$$ n=2^a $$

または

$$ n=2^a p^b $$

である。ただし $p$ は奇素数である。

まず $n=2^a$ のとき、

$$ f(2^a)=2^{a-1} $$

であるから、常に $f(n)\mid n$ が成り立つ。$5\leqq 2^a\leqq 100$ より、

$$ 2^a=8,16,32,64 $$

である。

次に $n=2^a p^b$ の場合を考える。このとき

$$ f(n)=2^{a-1}p^{b-1}(p-1) $$

である。

したがって

$$ \begin{aligned} \frac{n}{f(n)} &= \frac{2^a p^b}{2^{a-1}p^{b-1}(p-1)} \\ \frac{2p}{p-1} \end{aligned} $$

である。

$f(n)\mid n$ であるためには、$\dfrac{2p}{p-1}$ が整数でなければならない。ここで $\gcd(p,p-1)=1$ だから、$p-1$ は $2$ を割り切る必要がある。

よって

$$ p-1\mid 2 $$

であり、$p$ は奇素数だから

$$ p=3 $$

である。

したがって、この場合は

$$ n=2^a3^b $$

に限られる。ただし $a\geqq 1,\ b\geqq 1$ である。

$5\leqq 2^a3^b\leqq 100$ を満たすものを列挙する。

$b=1$ のとき、

$$ 2^a\cdot 3\leqq 100 $$

より

$$ 6,12,24,48,96 $$

である。

$b=2$ のとき、

$$ 2^a\cdot 9\leqq 100 $$

より

$$ 18,36,72 $$

である。

$b=3$ のとき、

$$ 2^a\cdot 27\leqq 100 $$

より

$$ 54 $$

である。

$b\geqq 4$ のとき、最小でも $2\cdot 3^4=162$ となり、$100$ を超える。

以上より、条件を満たす $n$ は

$$ 6,8,12,16,18,24,32,36,48,54,64,72,96 $$

である。

解説

この問題の中心は、$f(n)$ がオイラーの $\varphi$ 関数であることを見抜き、素因数で割り切れる数を除くことである。

（1）は包除原理を正しく使えばよい。$p,q,r$ のどれかで割り切れる数を除くので、重複して除いた分を戻す必要がある。

（2）では、単純に $5$ から $100$ まで調べるのではなく、$2$ の指数に注目するのが重要である。奇素因数が2種類以上あると、それぞれの $p_i-1$ から少なくとも1つずつ $2$ が出てくるため、$f(n)$ に含まれる $2$ の指数が大きくなりすぎる。これにより、奇素因数は高々1種類に絞られる。

その後、$n=2^a$ と $n=2^a p^b$ の2つだけを調べればよく、後者では $p=3$ しか許されない。