第5問 整数の解答・解説

$N=p^a{q}^b{r}^c$ とおく。$1$ 以上 $N$ 以下の整数が $N$ と互いに素でないのは、$p,q,r$ のどれかで割り切れるときである。$1$ から $N$ までで $p$ の倍数は $\frac{N}{p}$ 個、$pq$ の倍数は $\frac{N}{pq}$ 個、というふうに数えられるので、包除原理より

である。右辺は因数分解できて

となる。$N=p^a{q}^b{r}^c$ を入れると

である。（証明終わり）

素因数が1種類なら $f\left(p^a\right)=p^{a-1}\left(p-1\right)$、2種類なら $f\left(p^a{q}^b\right)=p^{a-1}{q}^{b-1}\left(p-1\right)\left(q-1\right)$ と、同じ形になる。(2) ではこれらも使う。

$n$ は偶数。$n\geqq 5$ が奇数とすると、$n$ は奇素数 $p$ をもち、$f\left(n\right)$ は $p-1$（偶数）で割り切れるので偶数である。偶数は奇数の約数になれないので、$f\left(n\right)$ は $n$ の約数にならない。

そこで $n=2^{a}m$（$a\geqq 1$、$m$ は奇数）と書く。(1) と同じ形の式から

である。

$m=1$ のとき：$f\left(n\right)=2^{a-1}$ は $2^a$ の約数なので条件をみたす。$5\leqq 2^a\leqq 100$ から $n=8,16,32,64$ である。

$m>1$ のとき：$m$ の奇素数 $p$ について $f\left(m\right)$ は $p-1$（偶数）で割り切れるので、$f\left(m\right)=2^{s}t$（$t$ は奇数、$s\geqq 1$）と書ける。このとき

で、これが $n=2^{a}m$（$2$ の指数は $a$）の約数になるには $a-1+s\leqq a$、つまり $s=1$ が必要である。

もし $m$ が相異なる奇素数 $p,q$ をもつと、$f\left(m\right)$ は $\left(p-1\right)\left(q-1\right)$ で割り切れて $4$ の倍数になり $s\geqq 2$ となる。よって $m=p^b$（$p$ は奇素数、$b\geqq 1$）である。

なので、$s=1$ は $p-1\equiv 2(\mathrm{mod}4)$ を意味する。さらに $f\left(n\right)=2^{a-1}{p}^{b-1}\left(p-1\right)=2^a{p}^{b-1}\cdot \frac{p-1}{2}$ が $2^a{p}^b$ の約数になるには、$\frac{p-1}{2}$ が $p$ の約数でなければならない。$p-1$ と $p$ は互いに素なので

である（このとき $p-1=2$ で $s=1$ も成り立つ）。したがって $n=2^a{3}^b$（$a,b\geqq 1$）である。逆にこの形なら $f\left(n\right)=2^{a-1}\cdot 3^{b-1}\cdot 2=2^a{3}^{b-1}$ で、確かに $n$ の約数である。

$5\leqq 2^a{3}^b\leqq 100$ を数え上げると

1. $b=1$：$6,12,24,48,96$
2. $b=2$：$18,36,72$
3. $b=3$：$54$

である。$m=1$ の場合と合わせて

の $13$ 個である。

答えは「$2$ の冪」と「$2$ の冪 × $3$ の冪」。$f\left(n\right)$ は $n$ に $\frac{p-1}{p}$ を掛けていく関数なので、分母の $p$ を $n$ 側でちょうど吸収できるのが $p=2,3$ だけ、と見ると納得しやすい。