創作整数問題#33解法&創作整数問題#34

最近寒い日が続いています。東京都心でも数センチほど積雪があり、今シーズン一番の寒気がやってきているというのも頷けますね。

因みに、先週の日曜のオイミャコン(ロシア・サハ共和国の北東に位置する「世界一寒い定住地」)では最高気温-56℃、最低気温-60℃を記録しています。北海道の内陸でも-20数℃が関の山ですから、やはりシベリアの寒さは段違いですね。


さて、本日1月22日に因んだ小話を少し。

前回の問題#33ではオイラーのトーシェント関数$\phi (n)$を扱いましたが、実は自然数$n$で$$\phi (n)=122$$を満たすものは存在しないことが知られています。このような正の整数のことを「ノントーシェント数」と呼びます。$122$は小さい方から数えて$16$番目のノントーシェント数です。さらに、実は$122$を$2$倍した$244$も($38$番目の)ノントーシェント数になっています。

なお、$1$を除くすべての奇数はノントーシェント数となるのでここではカウントしていませんでした。奇数のノントーシェント数まで含めた場合、$122$は小さい方から数えて$76$番目、$244$は$159$番目のノントーシェント数となります。(HN たけちゃん 様よりご指摘を頂きました(2018/01/24付))



《問題#34》

任意の正の整数$n$に対して、各位の数字が$1$または$2$のみからなる正の整数であり$2^n$で割り切れるものが存在することを示せ。

(創作問題)


あまり見たことの無いタイプの問題かもしれませんね。入試問題というよりは数学コンテスト向きの問題です。

 

証明問題につき、解答例は次回掲載します。


創作整数問題#33(解き方)


自然数$n$に対して、$1$から$n$までの自然数で$n$と互いに素なものの個数を$\phi (n)$とする。例えば $\phi (2)=1$、$\phi (3)=2$、$\phi (8)=4$ である。このとき以下の問に答えよ。

(1)関数$\phi (n)$が乗法的であることを利用して、$\phi (1200)$の値を求めよ。ここで関数$\phi (n)$が乗法的であるとは、$\phi (1)=1$ であり、かつ、互いに素な自然数$m$、$n$について$$\phi (mn)=\phi (m) \phi (n)$$がつねに成り立つことをいう。

(2)$n \geqq 3$ のとき、$\phi (n)$は任意の自然数$n$に対して偶数値をとることを示せ。

(1)はトーシェント関数が「乗法的」であるという性質を利用すれば簡単に求めることができます。また(2)は素数$p$について $\phi(p)=p-1$、$\phi(p^m)=p^m-p^{m-1}$ などの関係式を利用して示すことができます。

 

(1)

$$1200=2^4 \cdot 3 \cdot 5^2$$と素因数分解できることを利用して、

$$\begin{align}\phi (1200) &=\phi(2^4 \cdot 3 \cdot 5^2) \\
&=\phi(2^4) \cdot \phi(3) \cdot \phi(5^2) \\
&=(2^4-2^3) \cdot (3-1) \cdot (5^2-5) \\
&=8 \cdot 2 \cdot 20 \\
&=\color{red}{320} \end{align}$$

と求めることができます。

 

(2)

関数の中身$n$がどんな整数なのかで場合分けします。

$n$が素数のとき、$n \geqq 3$ より$n$は奇素数です。素数$n$に対して$$\phi(n)=n-1$$となりますから$\phi (n)$は偶数です。

次に$n$が合成数の場合(素数でない場合)を考えます。

$n$がある奇素数$p$を素因数にもつ合成数であるとき、ある整数$N$を用いて $n=pN$ と表せます。これより、$$\begin{align}\phi (n) &=\phi(p \cdot N) \\
&=\phi(p) \cdot \phi(N)\\
&=(p-1)\phi(N) \end{align}$$となります。いま、$p$は奇素数なので $p-1$ は偶数です。よって$\phi (n)$は偶数です。

最後に、$n$が奇素数を素因数にもたない合成数であるとき、$n$は偶数の素数、つまり$2$しか素因数にもたないので、$n$は$2$の冪乗の形で表せます。そこで $n=2^k$ と表すことにします(ただし$k$は$2$以上の整数)。

このとき、$$\begin{align}\phi (n) &=\phi(2^k) \\
&=2^k-2^{k-1} \end{align}$$となります。$k \geqq 2$ より、これは偶数なので$\phi (n)$は偶数です。

以上ですべての正の整数$n$の場合について尽くされていますから、$n \geqq 3$ のとき$\phi (n)$が偶数となることが証明されました。


 

今回の問題は全然ゴツい問題ではないので、これを誘導設問としてさらに発展的な問題に仕上げることもできそうです。

なお、冒頭で触れた「ノントーシェント数」ですが、様々な性質が知られています。例えば、ノントーシェント数が無数に存在することや、任意の整数$m$に対して、積$mp$がノントーシェント数となるような素数$p$が存在することなどが知られています。

また、トーシェント関数$\phi (n)$について、$$\displaystyle \sum^{\infty}_{n=1} \dfrac{\phi (n)}{2^n}=1.3676…$$と収束することも知られています。


数論の未解決問題にトーシェント関数に関するものが多く存在していることもなかなか興味深いですね。

“創作整数問題#33解法&創作整数問題#34” への2件の返信

  1. お久しぶりです.
    2018年のはじめての書き込みですが,
    「あけましておめでとうございます」は遅きに失した感がありますね.

    「$122$ 以下の自然数 $n$ で $\phi(n)=122$ を満たすものは存在しない」
    のは当然ですね.
    $\phi(n)\leqq n$ であり,等号は $n=1$ でのみ成立するので,
    「$N$ 以下の自然数 $n$ で $\phi(n)=N$ を満たすものは存在しない」
    は,$N\geqq 2$ であるすべての自然数 $N$ に対して成立します.

    私の知識にはなかったので調べてみたのですが,
    Wikipediaによれば,$m$ がノントーシェント数であることの定義は
    「自然数 $n$ で $\phi(n)=m$ を満たすものは存在しない」のようです.
    すると,「$\phi(n)=122$」の1行上の「122以下の」は
    カットする方がよいと思います.

    また,この定義によれば,$1$ を除くすべての奇数はノントーシェント数となり,
    $122$ は16番目ではなく76番目,$244$ は38番目ではなく159番目の
    ノントーシェント数であることになると思います.
    (プログラムで調べました.)

    ただし,Wikipedia の定義に「$m$ は偶数,かつ,」を追加した定義ならば,
    16番目,38番目で正しいようなので,
    定義によってはこのままで正しいかもしれません.

    1. お久し振りです。
      コメントありがとうございます。
      何かと至らぬところの多いサイトではありますが、今年もどうぞ宜しくお願い致します。

      1以外のすべての奇数はノントーシェントなので、ここでは奇数を勘定に入れていませんでした。仰る通り「ノントーシェント」の定義に照らせば、122と244はそれぞれ76番目、159番目のノントーシェント数となりますね。

      また、「122以下の」云々に関しては完全にご指摘の通りですので、早速訂正させて頂きました・・・。
      いつもありがとうございます。

pencil へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 が付いている欄は必須項目です