インテジャーズ

INTEGERS

数、特に整数に関する記事。

オイラーのトーシェント関数とφ(R(n))=n

2016\varphi (\mathrm{R}(n))=nを満たす6番目の数です。西暦で言えば、このような性質を満たすのは(我々が生きているうちでは)今年が最後です。

Eulerのトーシェント関数

正整数nに対し、1からnまでのnと互いに素な整数の個数を\varphi (n)と表して、Eulerのトーシェント関数と言います。例えば、6と互いに素な整数は1から6の間に1, 4の2つだけなので、\varphi (6)=2となります。\varphi (1)1です。一般公式は次のように与えられます:

命題 n\geq 2n=p_1^{e_1}\cdots p_k^{e_k}と素因数分解されるとき、
\displaystyle \varphi (n) = n\left(1-\frac{1}{p_1}\right) \cdots \left( 1-\frac{1}{p_k}\right)
が成り立つ。

これは、素数pと正整数lに対して \varphi (p^l)=p^l-p^{l-1}が成り立つことと、\varphiの乗法性(nmが互いに素であれば\varphi (nm)=\varphi (n) \varphi(m))から従います。乗法性は中国式剰余定理から分かります(\#(\mathbb{Z}/n\mathbb{Z})^{\times}=\varphi (n)に注意)。

トーシェント(totient)とは?

Eulerのトーシェント関数は1758年までにEulerが基本的な性質を調べており、GaussのDA(1801年)で記号\varphiが用いられました。その後、Sylvesterの論文

“On Certain Ternary Cubic-Form Equations,” Amer. Jour. of Math., (1879), no. 3, 280-285, no. 4, 357-393.

で"totient"という言葉を用いることが提唱されました。なお、Sylvesterは同時に「\varphiではなく\tauを使うべし」としていますが、こちらは後の歴史において採用されていません。"totient"は完全に造語ですが、ラテン語の"totiens"("so many times"を意味する)が由来であるという説があるようです。詳しくはSylvesterに問い合わせてください。

反転作用素\mathrm{R}

10進法表記された正整数を逆から読んだ正整数に変換する作用素を\mathrm{R}と表すことにします。
例) \mathrm{R}(12345)=54321

これを用いると、nが回文数\Longleftrightarrow \mathrm{R}(n)=nとなります。
integers.hatenablog.com

\varphi (\mathrm{R}(n))=n

n \geq 2 \Longrightarrow \varphi (n) < nなので、\varphi (n) = nとなることは決してありません。しかしながら、\varphi (\mathrm{R}(n))=nは屡々生じるようです。

例)

\begin{equation}\begin{split} \varphi (\mathrm{R}(2016))&=\varphi (6012)=\varphi ( 2\times 3^3\times 113)\\ &=6012\times \left(1-\frac{1}{2}\right) \left( 1-\frac{1}{3}\right)\left(1-\frac{1}{113}\right) = 2016\end{split}\end{equation}


10^{11}以下のこのような数の全リストは次のようになります:

\begin{align}&1, 12, 36, 192, 1992, 2016, 31067664, 39206496, 1564356432,\\ &3937403136, 15600000432, 22871605008\end{align}

次のような一般的な命題が成立します:

命題 k, a, b, cを非負整数とし、q_k:=\underbrace{9\cdots 9}_{k}7=10^{k+1}-3 および
p_{a,b,c}:=\underbrace{(\underbrace{9\cdots 9}_{a}78\underbrace{0\cdots 0}_{b}21\underbrace{9\cdots 9}_{a})\cdots (\underbrace{9\cdots 9}_{a}78\underbrace{0\cdots 0}_{b}21\underbrace{9\cdots 9}_{a})}_{c\times (2a+b+4)}7
が素数であると仮定する。このとき、n_k:=\mathrm{R}(3q_k)=1\underbrace{9\cdots 9}_{k}2 および
m_{a,b,c}:=\mathrm{R}(3p_{a,b,c})=1\underbrace{(\underbrace{9\cdots 9}_{a}56\underbrace{0\cdots 0}_{b}43\underbrace{9\cdots 9}_{a})\cdots (\underbrace{9\cdots 9}_{a}56\underbrace{0\cdots 0}_{b}43\underbrace{9\cdots 9}_{a})}_{c\times (2a+b+4)}2
とすると、\varphi (\mathrm{R}(n_k))=n_k および \varphi (\mathrm{R} (m_{a,b,c}))=m_{a,b,c}が成り立つ。

証明. n=n_k \ (\text{resp.} \ m_{a,b,c})p=q_k \ (\text{resp.} \ p_{a,b,c})とすると、

\varphi (\mathrm{R}(n))=\varphi (3p)=2(p-1) =n

となっている。 Q.E.D.

q_0=7, q_1=97, q_2=997, p_{0,0,2}=782178217, p_{0,5,1}=7800000217
は素数なので、n_0=12, n_1=192, n_2=1992, m_{0,0,2}=1564356432, m_{0,5,1}=15600000432が得られます。

一方、次は(たぶん)未解決の問題です:

Chandler予想 \varphi (\mathrm{R}(n))=nを満たす整数nは無数に存在するであろう。