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

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

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

---

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

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

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

---

---

《問題#34》

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

（創作問題）

---

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

 

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

---

創作整数問題#33（解き方）

---

---

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

 

（１）

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

$$\begin{array}{rl}\varphi (1200)& =\varphi (2^4\cdot 3\cdot 5^2)\\ & =\varphi (2^4)\cdot \varphi (3)\cdot \varphi (5^2)\\ & =(2^4-2^3)\cdot (3-1)\cdot (5^2-5)\\ & =8\cdot 2\cdot 20\\ & =320\end{array}$$

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

 

（２）

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

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

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

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

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

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

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

---