tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

「2pがトーシェントであること」と「pがソフィー・ジェルマン素数であること」は同値

数学整数論素数

今朝投稿されたYouTube動画
youtu.be

にて、 $2p$ （ $p$ は素数）の形の数がトーシェントである条件が、ソフィー・ジェルマン素数に関係するという非常に興味深い定理を紹介しました。

定理

$p$ を素数とすると，次が成り立つ：

$2p$ がトーシェント $\;\; \Longleftrightarrow \;\;$ $p$ はソフィー・ジェルマン素数

ここで、 $m$ がトーシェントであるとは、ある $n$ が存在して $\varphi(n) = m$ が成り立つことを言います。（詳しくは動画をご覧ください。）

今日は、動画の補足としてこの興味深い定理の証明を紹介したいと思います。
（今回はあくまで動画の補足という位置付けなので、いつもの記事と違って淡々と進めていくタイプの記事となっています。）

証明には、オイラー関数の下記の性質を用います。

性質１： $\varphi(mn) = \varphi(m) \varphi(n)$ （ $m, n$ は互いに素）
性質２： $\varphi(p^e) = p^e - p^{e-1}$ （ $p$ は素数、 $e$ は正整数）
性質３： $n = p_1^{e_1} \cdots p_r^{e_r}$ と素因数分解されるとき $\varphi(n) = n \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_r}\right)$
性質４： $\{\varphi(n) \mid n = 1, 2, 3, \ldots \} = \{1\} \cup \{ 2n \mid n = 1, 2, 3, \ldots\}$

　

補題

次の補題を示します。

補題

$n$ を自然数， $q$ を素数とし $m = qn$ とする．このとき，次の (i), (ii) が成り立つ：
(i) $q \not\mid n$ ならば $\varphi(m) = (q-1) \varphi(n)$
(ii) $q \mid n$ ならば $\varphi(m) = q \varphi(n)$

（証明）
(i) $q, n$ は互いに素より、性質１より $\varphi(m) = \varphi(q) \varphi(n)$ 。

性質２より $\varphi(q) = q - 1$ なので $\varphi(m) = (q-1) \varphi(n)$ となり (i) が従う。

(ii) $q \mid n$ より $\operatorname{ord}_q(n) = e$ とすると（ $q^e$ が $n$ をちょうど割り切る）、

$m = qn = q^{e+1} n'$ 　（ $q, n'$ は互いに素）

とかける。また $n = q^{e} n'$ とも表せる。

よって、性質１・２より

$\varphi(m) = \varphi(q^{e+1}) \varphi(n') = q^{e}(q-1) \varphi(n')$

であり、同様に

$\varphi(n) = \varphi(q^{e}) \varphi(n') = q^{e-1}(q-1) \varphi(n')$

でもあるので (ii) $\varphi(m) = q\varphi(n)$ が得られる。

（証明終わり）

$\Longleftarrow$ の証明

$p$ はソフィー・ジェルマン素数より、 $2p+1$ も素数。よって、 $\varphi(2p+1) = 2p$ であり、これは $2p$ がトーシェントであることを意味する。

$\Longrightarrow$ の証明

$2p$ はトーシェントより、ある $m$ が存在して $\varphi(m) = 2p$ である。

$p = 2$ はあきらかにソフィー・ジェルマン素数であり成立するので、以降 $p\neq 2$ として構わない。

$m = 2^e$ （2のべき）のときと、それ以外で場合分けをする。

$m = 2^e$ のとき

このときは性質２より $\varphi(2^e) = 2^{e-1} = 2p$ であり、 $p \neq 2$ に矛盾する。

$m = qs$ （ $q$ は奇素数）のとき

(i) $q \not \mid s$ のとき、補題の (i) より $\varphi(m) = (q-1) \varphi(s) = 2p$ 。

よって、 $q-1 \mid 2p$ 。すなわち $q - 1$ は $2p$ の約数であるから

$q - 1 = 1, \; 2, \; p, \; 2p$

のいずれかである。

・ $q$ は奇素数より $q - 1 = 1$ ではない。

・ $q - 1 = 2$ とすると $q = 3$ であるが、このとき $(3-1) \varphi(s) = 2p$ より $\varphi(s) = p$ である。 $p$ は奇素数であり、1より大きいので、これは性質４に反する。

・ $p, q$ の偶奇性より $q - 1 = p$ はあり得ない。

ゆえに、あり得るのは

$q - 1 = 2p$

の場合だけであり、 $q = 2p + 1$ は素数より、 $p$ はソフィー・ジェルマン素数。

(ii) $q \mid s$ のとき、補題の (ii) より $\varphi(m) = q \varphi(s) = 2p$ である。

よって、 $q \mid 2p$ である。 $q$ は奇素数なので $q = p$ である。

よって $p\varphi(s) = 2p$ より $\varphi(s) = 2$ である。

また、 $q \mid s$ より $s = q^{\alpha} s'$ （ $q, s'$ は互いに素）と置くことができ、性質１・２より

$\varphi(s) = q^{\alpha - 1} (q-1) \varphi(s')$

より、 $q - 1 \mid \varphi(s) = 2$ である。

ゆえに、 $q-1 = 1$ または $q - 1 = 2$ であり、 $q \neq 2$ より $q = 3$ である。

このとき、 $p = q = 3$ より $2p+1 = 7$ で、 $p$ はソフィー・ジェルマン素数。

（証明終わり）

面白いですね！　それでは今日はこの辺で！
（動画も是非見てね！）

参考文献

Rodney Coleman, "On the image of Euler's totient function", arXiv:0910.2223 [math.NT].
arxiv.org