解説

方針・初手

条件(ii)は、$h$ と互いに素な $h$ 未満の自然数が、6個の数 $m_1,\dots,m_6$ の中にすべて含まれることを意味する。したがって、まず

$$ \phi(h)\leq 6

$$

を得るのが初手である。

ただし、$m_1,\dots,m_6$ のすべてが $h$ と互いに素であるとは限らない点に注意する。

解法1

**(1)**

$p^n$ と互いに素でない $p^n$ 以下の自然数は、$p$ の倍数である。

実際、$p$ は素数であるから、自然数 $k$ が $p^n$ と互いに素でないことは、$k$ が $p$ を約数にもつことと同値である。

$1$ から $p^n$ までの自然数のうち、$p$ の倍数は

$$ p,2p,3p,\dots,p^{n-1}p

$$

であり、その個数は $p^{n-1}$ 個である。

したがって、$p^n$ と互いに素な $p^n$ 以下の自然数の個数は

$$ p^n-p^{n-1}

$$

である。よって

$$ \phi(p^n)=p^n-p^{n-1}

$$

が示された。

**(2)**

条件(i)より

$$ m_1<m_2<\cdots<m_6<h

$$

であるから、$h>1$ である。したがって、$h$ 自身は $h$ と互いに素でないので、$\phi(h)$ は $h$ 未満で $h$ と互いに素な自然数の個数に等しい。

条件(ii)より、そのような自然数は集合 ${m_1,m_2,\dots,m_6}$ に含まれる。よって

$$ \phi(h)\leq 6

$$

である。

ここで、$h$ が $11$ 以上の素数 $q$ で割り切れると仮定する。$h=q^a r$ とおく。ただし $a\geq 1$、$\gcd(q,r)=1$ である。

与えられた乗法性と （1） より、

$$ \phi(q^a)=q^a-q^{a-1}=q^{a-1}(q-1)

$$

である。したがって

$$ \phi(h)=\phi(q^a)\phi(r)=q^{a-1}(q-1)\phi(r)

$$

となる。

ここで $q\geq 11$ であり、$\phi(r)\geq 1$ だから

$$ \phi(h)\geq q-1\geq 10

$$

となる。これは $\phi(h)\leq 6$ に反する。

よって、$h$ は $11$ 以上の素数で割り切れない。

**(3)**

$m_2=4$ とする。

まず、$1$ は任意の自然数 $h$ と互いに素であり、かつ $1<h$ である。したがって条件(ii)より、$1$ は集合 ${m_1,m_2,\dots,m_6}$ に属する。

$m_2=4$ かつ $m_1<m_2$ であるから、

$$ m_1=1

$$

である。

このとき、$2,3$ は集合 ${m_1,m_2,\dots,m_6}$ に属さない。条件(ii)より、$h$ と互いに素な $h$ 未満の自然数はすべてこの集合に属するので、$2,3$ は $h$ と互いに素ではない。

したがって

$$ 2\mid h,\qquad 3\mid h

$$

である。

また、$2\mid h$ であるから、$4$ は $h$ と互いに素ではない。すなわち、集合 ${m_1,m_2,\dots,m_6}$ のうち少なくとも $m_2=4$ は、$h$ と互いに素な数ではない。

よって、$h$ と互いに素な $h$ 未満の自然数は多くても $5$ 個であり、

$$ \phi(h)\leq 5

$$

である。

さらに （2） より、$h$ の素因数は $2,3,5,7$ のみである。すでに $2\mid h,\ 3\mid h$ が分かっているので、

$$ h=2^a3^b5^c7^d

$$

とおける。ただし

$$ a\geq 1,\quad b\geq 1,\quad c\geq 0,\quad d\geq 0

$$

である。

乗法性と （1） より、$5$ が $h$ を割るなら $\phi(h)$ には因数 $\phi(5)=4$ が現れる。すると

$$ \phi(h)\geq \phi(2)\phi(3)\phi(5)=1\cdot 2\cdot 4=8

$$

となり、$\phi(h)\leq 5$ に反する。よって $5\nmid h$ である。

同様に、$7$ が $h$ を割るなら

$$ \phi(h)\geq \phi(2)\phi(3)\phi(7)=1\cdot 2\cdot 6=12

$$

となり、$\phi(h)\leq 5$ に反する。よって $7\nmid h$ である。

したがって

$$ h=2^a3^b

$$

である。

このとき

$$ \phi(h)=\phi(2^a)\phi(3^b)

$$

である。（1） より

$$ \phi(2^a)=2^a-2^{a-1}=2^{a-1}

$$

かつ

$$ \phi(3^b)=3^b-3^{b-1}=2\cdot 3^{b-1}

$$

だから

$$ \phi(h)=2^{a-1}\cdot 2\cdot 3^{b-1}=2^a3^{b-1}

$$

である。

もし $b\geq 2$ なら、

$$ \phi(h)=2^a3^{b-1}\geq 2\cdot 3=6

$$

となり、$\phi(h)\leq 5$ に反する。よって

$$ b=1

$$

である。

したがって

$$ h=2^a\cdot 3

$$

であり、

$$ \phi(h)=2^a

$$

である。$\phi(h)\leq 5$ より

$$ 2^a\leq 5

$$

なので、

$$ a=1,2

$$

である。

一方、$m_2=4$ で

$$ m_1<m_2<m_3<m_4<m_5<m_6<h

$$

だから、少なくとも

$$ m_6\geq 8

$$

であり、

$$ h\geq 9

$$

である。

$a=1$ のとき $h=6$ となり、$h\geq 9$ に反する。したがって

$$ a=2

$$

である。

よって

$$ h=2^2\cdot 3=12

$$

である。

実際、$h=12$ のとき、$12$ と互いに素な $12$ 未満の自然数は

$$ 1,5,7,11

$$

であり、例えば

$$ (m_1,m_2,m_3,m_4,m_5,m_6)=(1,4,5,6,7,11)

$$

とすれば条件(i), (ii)を満たす。

解説

この問題では、条件(ii)を「$m_1,\dots,m_6$ がすべて $h$ と互いに素である」と読んではいけない。条件(ii)が述べているのは、$h$ と互いに素な数がその6個の集合に含まれるということだけである。

したがって得られる基本情報は

$$ \phi(h)\leq 6

$$

であり、$m_2=4$ の条件を加えると、$4$ は偶数 $h$ と互いに素でないため、さらに

$$ \phi(h)\leq 5

$$

まで絞れる。この差が重要である。

あとは、$\phi(p^n)=p^n-p^{n-1}$ と乗法性を用いて、$h$ の素因数を制限する。$11$ 以上の素数が入ると $\phi(h)$ が大きくなりすぎるため、素因数は $2,3,5,7$ に限られる。さらに $m_2=4$ から $2,3$ がともに $h$ を割ることが分かり、最後は指数を調べれば $h=12$ に決まる。

答え

**(1)**

$$ \phi(p^n)=p^n-p^{n-1}

$$

**(2)**

$h$ は $11$ 以上の素数で割り切れない。

**(3)**

$$ h=12

$$