オイラーの
ϕ
関数に関するレーマーの予想と
Xiao
の証明について
鈴木治郎† †信州大学 †[email protected] 要旨 素数ではない正整数nとオイラーのϕ(n)関数に関して，レーマーはϕ(n)が n− 1を割り切らないという予想をした．2017年，Xiaoはこの予想を証明したとする論 文をarXivに投稿した．この論文には誤りがあり，証明はできていない．ここでは証明 の誤りを指摘するとともに，初等整数論で起こりやすい誤りおよび素因数分解問題におけ るオイラーのϕ関数の重要性について解説する． キーワード レーマーの予想,オイラーのϕ関数1
はじめに
正の整数 n に対して定義されるオイラー（Euler）の ϕ 関数とは，n 以下の正の整数であって n と互いに素な数 の個数を表す関数のことである．とくに n = p が素数で あるとき ϕ(n) = ϕ(p) = p− 1 である． E.H. レーマー（Lehmer）は 1932 年に 性質 1 (レーマーの予想). n が合成数，つまり素数でな ければ ϕ(n) は n− 1 を割らない． と予想した． 2 つの整数 a, b があるとき，その一方について a̸= 0 であるとする．a が b を割り切るとき，記号 a| b で表す． a が b を割らないとき，記号 a∤ b で表す．この記号のも とでレーマーの予想は「n が合成数のとき ϕ(n)∤ n − 1」 と表せる．n = p が素数であれば，上にあげた性質によ り ϕ(p) = p− 1 は n − 1 = p − 1 を割る．記号で表せば ϕ(n)| n − 1 である． 今日のネットワーク社会において公開鍵暗号は，誰で も盗聴可能なネットワークを安全に利用するための基本 技術である．SSL で使われる公開鍵暗号方式 RSA は素因 数分解の計算困難性に数学的基礎を置く方法である．素 因数分解はオイラーの ϕ 関数と結びつく． 性質 2 (素因数分解と ϕ 関数). n の素因数の個数が 2 個 以下であれば，n の素因数分解を得ることと ϕ(n) を求め ることとは同等の計算困難性をもつ 2018 年 4 月 11 日受付 2018 年 8 月 10 日採録 性質の証明の概略 素数 p, q により n は素因数分解 paqb を持つとする．このとき例えば素因数 p について ϕ(pa) = p− 1 a = 1 のとき pa−1(p− 1) a > 1 のとき である．またオイラーの ϕ 関数は，互いに素な正整数 M, N に対して ϕ(M N ) = ϕ(M ) ϕ(N ) という性質をもつ．よって n の素因数分解にこれを適用 すれば，オイラーの ϕ 関数の値もわかる [3]． 逆にオイラーの ϕ 関数の値はわかっていても p, q は未知 なものとする．もしも a > 1 とすれば ϕ(n) = ϕ(qb) pa−1 (p− 1) であり， p| gcd(n, ϕ(n)) となる．つまり n とは異なる自明でない約数 p がわかる． つまり計算量 O(log n) であるユークリッドの互除法で素 因数を求めることができる．もう一つの素因数 q につい ても同様なので，a > 1 または b > 1 のときに素因数を 求めることに困難はない．n = pq の場合に，オイラーの ϕ 関数の値から素因数を求めることが残される． n = pq の素因数 p, q は未知であっても，オイラーの ϕ 関数の値は ϕ(n) = (p− 1)(q − 1) = pq − (p + q) + 1 とわかっていると仮定する．このとき 2 次方程式 x2− (n + 1 − ϕ(n))x + n を考えると，n の素因数 p, q のいずれも満たすことが確 かめられる．だから，この方程式の解を，2 次方程式の 国際ICT利用研究学会研究会研究論文誌 第１巻 第１・2合併号 2-解の公式などにもとづいて求めればよい．よって n = pq の場合もオイラーの ϕ 関数の値から n の素因数分解を容 易に求めることができる． 素因数の個数が 3 以上の場合でも，例えば Miller-Rabin の擬素数判定法によれば，リーマン予想の仮定のもとで O(log2n) の計算量で素因数を見つけることができる [4]． しかしながら素因数が 2 個の場合のような同等性は得ら れていない． もしもレーマーの予想が誤りであれば，n− 1 の素因数 分解を通じて ϕ(n) の値の手がかりも得られるのであり， とくに n− 1 の素因数分解を n の素因数分解へと反映で きることは，ポラード（Pollard）の n− 1 法 [3, 2 章 §5] などの素因数分解法で有効性が高くなる．したがって n の素因数分解が容易になる合成数が少なからず存在する という意味で，数学の社会への応用としても興味ある問 題である． このレーマーの予想に対して，Huan Xiao はこの予想 を証明したとする論文 [2] を arXiv に投稿した． 山下倫範氏にこの論文のことを教えてもらった（2018 年 3 月 9 日である）．筆者は，その論文の確認をしてみ た．証明には誤りが見つかった．誤りの部分を以下に引 用する．恒等式から得られる 2 つの関係式 (2.2) (p′1− 1)(p′2− 1)· · · (p′k− 1)| (p′1p′2· · · p′k− 1)p′k+1+ p′k+1− 1 (2.3) (p′k+1− 1)| (p′ k+1− 1)p′1p′2· · · p′k + p′1p′2· · · p′k− 1 をもとに Xiao は以下を主張した [2]．
From formula 2.3 we know (p′k+1− 1)| p′
1p′2· · · p′k− 1,
combining with formula 2.2 gives
(p′1− 1)(p′2− 1)· · · (p′k− 1)| p′1p′2· · · p′k− 1. しかし，この議論が成り立つためには (p′1− 1)(p′2− 1)· · · (p′k− 1)| p′k+1− 1 を示す必要がある．しかし Xiao はこのことを証明して いない． かつてフェルマーの最終定理を和田秀男氏 [5] ととも に研究していた筆者は，アマチュアの方々から「難問を （初等的に）解決した」と称する手紙をもらう機会がたび たびあったので，このような論文を読み解くのに慣れて いる．そこで，こうした証明の誤りを読み解く上で，投 稿者の勘違いをはっきりさせる方法に関する注意を交え て，Xiao の論文について簡単に解説する．
2
Xiao の証明
レーマーはその予想を発表した論文 [1] において次の 2 つの性質を証明している． 性質 3 (レーマーの定理 1). ϕ(n) が n− 1 を割るならば n は相異なる奇素数の積である． 証明 p2|n ⇒ p(p−1)|ϕ(n) である．仮定により ϕ(n)|n−1 なので p|n − 1 である．しかし素数 p は n の約数（≥ 3） なので n− 1 を割ることはない． 性質 4 (レーマーの定理 4). 合成数 n の素因数の個数が 6 以下であれば，ϕ(n) は n− 1 を割らない． 2.1 帰納法で証明する？ Xiao は次の性質を証明の出発点とした [2]． 性質 5 (レーマーの定理の言い換え). 合成数 n に対して ϕ(n) が n− 1 を割るならば，n の素因数の個数は 7 以上 であり，また n の素因数はすべて相異なる（以下の証明 の書き直しにおいて，素因数の個数は 2 以上で十分であ る．したがってレーマーの定理 4 はこの議論において不 要である）． ここで Xiao は次の形で証明すると論じている． 性質 6 (Xiao の証明方法). Xiao の帰納法に関する主張 部分を以下に引用する [2]．We use induction on the number of distinct prime divisors ω(n) of n. . . . suppose there is no composite number n with ω(n) = k, k ≥ 8 such that ϕ(n)|n − 1. We need to show there is no composite number n with ω(n) = k + 1 such that ϕ(n)|n − 1. ここで帰納法の出発点となる「第 1 段の主張」，すなわ ち n がある初期値に関して成り立つという主張，を明示 的に述べていないことが気になる．帰納法による証明の 誤りの多くは「第 1 段」に誤りのあることが多いためで ある．しかし以下に述べたように帰納法でない形に言い 換えられるので，帰納法自体を問題にはしない． レーマーの予想を満たす n の素因数の個数に関する帰 納法を Xiao は次のように進めている． オイラーのφ関数に関するレーマーの予想とXiaoの証明について 3
-相異なる k 個の任意の奇素数の積 n = p1· · · pkについ て ϕ(n) = (p1− 1) · · · (pk− 1) ∤ n − 1 を仮定する．こ のとき，ある k + 1 個の素数の積 n = p′ 1· · · p′k+1にお いて ϕ(n) = (p′1− 1) · · · (p′k+1− 1) | n − 1 を仮定すれ ば（つまり設定すべき命題の対偶を仮定すれば）ϕ(n) = (p′1− 1) · · · (p′k+1− 1) ∤ p′1· · · p′k− 1 が証明できて，帰納 法の仮定に矛盾する． 2.2 帰納法の代案 帰納法や背理法で示すとしてある場合，トートロジー あるいは定義されない状況がよくあるので注意したい． 適当な言い換えができるならば，その言い換えをした上 で考察したほうがよい．次のようにすれば帰納法表現も 背理法表現も避けることができる． L をレーマーの予想を満たさない合成数 n の集合，す なわち L ={n ∈ N | n は ϕ(n)|n − 1 である合成数 } とする．レーマーの定理 1 により，L は L = ∪ k≥2 Lk, Lk ={ 相異なる k 個の素数の積 } ∩ L と表せる．このとき 性質 7 (添字の最小値の存在). L̸= ∅ であれば，任意の k < K について Lk =∅ かつ LK ̸= ∅ となる最小の自然 数 K が存在する∗． n∈ LK に対してはレーマーの定理 1 により，相異な る奇素数 p1, . . . , pKが存在して n = p1p2· · · pK−1pK と 表せる．さらに L の定義により次を満たす． (p1− 1) · · · (pK−1− 1)(pK− 1) | p1· · · pK−1pK− 1 (1) この関係は適当な整数 α̸= 0 により α(p1− 1) · · · (pK−1− 1)(pK− 1) = p1· · · pK−1pK− 1 (2) と言い換えられる．整除性に関する性質は，0 に相当す る数で割る誤りが多いので，式の操作として割らない形 に言い換えて読み直すべきである． 2.3 Xiao の計算 Xiao は n− 1 に対して次の 2 つ式変形（前述の 2.2 お よび 2.3）を提供した． p1· · · pK−1pK− 1 = (p1· · · pK−1− 1)pK+ pK− 1 (3) ∗レーマーの定理 4 から K≥ 7 であり，その後，何人かの仕事でこ の下限は更新されている． p1· · · pK−1pK−1 = (p1· · · pK−1)(pK−1)+p1· · · pK−1−1 (4) (2) と (4) を合わせれば (p1· · · pK−1)pK− 1 (2) = α(p1− 1) · · · (pK−1− 1)(pK− 1) (4) = (p1· · · pK−1)(pK− 1) + p1· · · pK−1− 1 が得られる．p1· · · pK−1− 1 について解けば p1· · · pK−1− 1 = α(p1− 1) · · · (pK−1− 1)(pK− 1) − (p1· · · pK−1)(pK− 1) = (pK− 1){α(p1− 1) · · · (pK−1− 1) − p1· · · pK−1} である．β = α(p1− 1) · · · (pK−1− 1) − p1· · · pK−1とお けば β(pK− 1) = p1· · · pK−1− 1 (5) と表せる．また (2) と (3) から α(p1− 1) · · · (pK−1− 1)(pK− 1) = pK− 1 + pK(p1· · · pK−1− 1) (6) を得る．(6) の両辺に β を乗じてから (5) を代入する． (p1− 1) · · · (pK−1− 1)αβ(pK− 1) = β(pK− 1) + βpK(p1· · · pK−1− 1) = (p1· · · pK−1− 1)(1 + βpK) (7) この関係にもとづき Xiao は (p1− 1) · · · (pK−1− 1) | p1· · · pK−1− 1 を主張した．しかし証明できているのは (p1− 1) · · · (pK−1− 1) | (p1· · · pK−1− 1)(1 + βpK) までである． ここで冒頭に引用した，Xiao が証明を与えていない のに仮定していると思える設定 (p1− 1) · · · (pK−1− 1) | pK− 1 を導入すれば，式 (7) の途中変形を利用して (p1− 1) · · · (pK−1− 1) | p1· · · pK−1− 1 が証明できる．この性質が成り立つことは添字 K の最小 性に反する．したがって L =∅ である．つまりレーマー の予想が証明できたことになる． 国際ICT利用研究学会研究会研究論文誌 第１巻 第１・2合併号 4
-整除性の関係を等式に言い換えたことにより，冒頭で 引用した Xiao の議論よりも問題点が明確になっている ことがわかるだろう． 最後に係数部分 1 + βpKを計算しておく． 1+βpK= α(p1−1) · · · (pK−1−1)−(p1· · · pK−1−1) であり，K の最小性の仮定により 0 にはならない． (p1−1) · · · (pK−1−1) と 1+βpKが互いに素ならば証明 はうまくいく．しかし見ればわかるように，この 2 数の公 約数は p1· · · pK−1−1 と α(p1−1) · · · (pK−1−1) の公約数 でもある．K の最小性から，それは (p1−1) · · · (pK−1−1) の倍数にはならないが，それ以上のことはわからない．
参考文献
[1] D.H.Lehmer, on Euler’s totient function, Bulletin of the American Mathematical Society, 38: 745– 751.1932.
[2] Huan XIAO, On the Lehmer’s problem involving Euler’s totient function, arXiv:1711.08313v1, 2017 年 11 月 16 日と記載． [3] 和田秀男，コンピュータと素因子分解，遊星社，1987 （第 2 版，1999）. [4] コブリッツ，数論アルゴリズムと楕円暗号理論入門 （櫻井幸一訳），シュプリンガー-フェアラーク東京， 1997. [5] 鈴木治郎，和田秀男先生の数学，国際 ICT 利用研究 学会論文誌第 1 巻第 1 号，pp.102–110, 2017.
