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

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

方針・初手

条件(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$ に決まる。