2021-01-22

mod mのべき乗余が何通りの値を取るかという話

数学整数論中国剰余定理

１つ前の記事に関連して「 $a^{k} \pmod{m}$ がどんな値をとるのか」という問題が気になりました。
tsujimotter.hatenablog.com

上の記事では

$k = \varphi(m)+1$ のとき $a^{\varphi(m)+1} \equiv a \pmod{m}$
$k = \lambda(m)+1$ のとき $a^{\lambda(m)+1} \equiv a \pmod{m}$

となる、つまり $a = 0, \ldots, m-1$ の全ての値を取ることを示しました。鯵坂もっちょさんの可視化の方法を用いるならば、右肩上がりの階段状になります。

f:id:tsujimotter:20210122201425p:plain:w400

（横軸が $a$ で、縦軸が $a^7 \pmod{42}$ となっています）

「 $a$ が $m$ と互いに素であるかどうかに関わらず」このようになるというのが面白かったわけですね。

一方で、 $k = \varphi(m)$ 乗した場合については、特に法則はなさそうに見えました。何か法則はあるのでしょうか。

そんなことを考えているうちに、青山学院大学の中川貴仁さんの卒論研究を見つけました。

整数のべき乗とオイラーの定理について
中川貴仁（西山研究室）
http://www.gem.aoyama.ac.jp/~kyo/sotsuken/2014/nakagawa_sotsuron_2014.pdf

中川さんの論文によると、 $m$ が相異なる $r$ 個の素数の積で表されるとき、すなわち

$m = p_1 p_2 \cdots p_r$

のとき、 $a^{\varphi(m)} \pmod{m}$ の値は $2^r$ 個通りの数をとるそうなのです。

$a$ が $m$ と互いに素のときは、オイラーの定理により $a^{\varphi(m)} \equiv 1 \pmod{m}$ ですから、常に $1$ の値をとります。上の話は、 $a$ が $m$ と互いに素とは限らないときも含めて、何パターンの値を取りうるかを教えてくれます。

そんなことが証明できるのですね。大変面白かったので、証明を紹介したいと思います。

2021-01-22

「互いに素でない場合」のオイラーの定理

数学整数論

$m$ を正の整数としたとき、 $a$ を $m$ と互いに素な任意の整数として

$a^{\varphi(m)} \equiv 1 \pmod{m}$

が成り立つことが知られています。 $\varphi(m)$ はオイラーのトーシェント関数といって、この合同式はオイラーの定理として知られています。

これは素数を使った有名な暗号の一つ「RSA暗号」の理論的背景に使われます。具体的には、 $m = pq$ として考えますが、 $\varphi(m) = (p-1)(q-1)$ となります。上の定理から

$a^{k(p-1)(q-1)+1} \equiv a \pmod{m}$

という合同式が成り立ちます。これを使うと、任意の $s$ に対して $t$ が存在して

$a^{st} \equiv a^{k(p-1)(q-1)+1} \equiv a \pmod{m}$

が成り立つ事が言えます（ユークリッドの互除法を使います）。したがって、 $s$ を暗号鍵、 $t$ を複合鍵とすれば、 $a$ を暗号化してまた戻してくる事ができるというわけですね。

以下の記事でより詳しく説明しました：
tsujimotter.hatenablog.com

ところで、意外にあまり明示的に書かれていない事実として、 $a$ が $m = pq$ と互いに素でなくても

$a^{\varphi(m)+1} \equiv a \pmod{m}$

は成り立ちます。つまり、暗号文を選ぶ時に、わざわざ $m$ と互いに素であるかどうか気にしなくて良いというわけですね。

ちなみに、上が成り立つからといって両辺を $a$ で割った

$a^{\varphi(m)} \equiv 1 \pmod{m}$

は一般に成り立ちません。両辺を割ることができない場合があるというのが、合同式の面白いところです。

2021-01-21

素数生成多項式と虚2次体の類数 (2)

数学素数整数論オイラーの素数生成多項式

昨日は、オイラーの素数生成多項式に関して「私の発見」を紹介させていただきました。
tsujimotter.hatenablog.com

執筆時は、この研究の先行研究にあたるものを発見できず、「先行研究はあるかわからないが独自にこんな発見をした」というスタンスを取っていました。しかしながら、やはり探せばあるものです。

このブログでも何度かお世話になっている木村巌先生より、2件ほど教えていただきました。私自身の力で見つけることができなかったので、大変ありがたいお話です！

[1]
On a lower bound for the class number of an imaginary quadratic field
[2]
An inequality between class numbers and Ono's numbers associated to imaginary quadratic fields

この様子だと他にも類似の研究はありそうです。勉強になります。

もちろん、私の記事と完全に同じ結果というわけではありません。私の記事と先行研究 [1][2] の違いをまとめると、次のようになります。

tsujimotter： $0\leq X \leq q-2$ の範囲において $f(X) = X^2 + X + q$ が素数を生成する確率に着目
先行研究[1][2]： $0\leq X \leq q-2$ の範囲において $f(X) = X^2 + X + q$ の素因数の個数（特に $0\leq X \leq q-2$ の範囲で個数が最大のもの）に着目

実は素因数の個数に着目すると、後半で示すように非常に明快な関係が得られるのです。この辺は問題の定式化のセンスを感じますね。私には思いつかないアイデアでした。

というわけで、この分野の考え方に親しむためにも、特に先行研究の考え方と結果についてまとめてみたいと思います。

オイラーの素数生成多項式について、より基本的な事項を知りたい方は、まずはこちらの記事を読むのをお勧めします：
tsujimotter.hatenablog.com

2021-01-20

（独自研究）素数生成多項式と虚2次体の類数

数学自由研究・独自研究整数論素数オイラーの素数生成多項式

今回の記事は、素数がたくさん登場する多項式

$f(X) = X^2 + X+ 41$

に関連する話題です。今回は私がこの式について考えているうちに、思いついて実施してみた独自研究について紹介したいと思います。どこかの本に書いてある話ではないので、誤りを含んでいる可能性も大いにあるかと思います。また、十分な調査ができているわけではないので、独自性もはっきりとしていません。その点をご了承の上で読んでください。

今回の記事は発展的な内容になっています。オイラーの素数生成多項式について、より基本的な事項を知りたい方は、まずはこちらの記事を読むのをお勧めします：
tsujimotter.hatenablog.com

今回は論文を意識したフォーマットで書いているため、普段のブログ記事より内容が難しく、堅めの書き振りになっている点をご了承ください。また、虚2次体に関する基本的な知識を前提とします。

追記：2020.01.21
やはりといいますか、当然と言いますか、先行研究として類似のアイデアの研究はありました。勉強も兼ねてブログにまとめていますので、次の記事もぜひご参照ください：
tsujimotter.hatenablog.com

追記：2020.01.22
Proposition 1.の証明におきまして、 $p = 2$ の場合を適切に考慮し忘れていたため、その点を修正しました。Proposition 2. の証明に影響はありません。

1. Introduction

1772年、EulerはBernoulliに宛てた手紙の中で、素数を生成する2次多項式について述べている。すなわち、素数 $q$ に対し、

$f_{q}(X) = X^2 + X + q \tag{1}$

と定義すると、素数 $q = 2, 3, 5, 11, 17, 41$ に対し $f_q(X)$ に整数 $X = 0, \ldots, q-2$ を代入した値がすべて素数になることを発見した。これをオイラーの素数生成多項式という。

Rabinovitch (1913)は $f_q(X)$ が素数生成多項式である条件と、対応する虚2次体の類数が1である条件の間の同値性を示した。すなわち、 $q$ を任意の素数であるとき、 $f_{q}(X)$ が $X = 0, \ldots, q-2$ においてすべて素数になるための必要十分条件は、虚2次体 $\mathbb{Q}(\sqrt{1-4q})$ の類数が1であることである。

さらに、Baker (1966)やStark (1967)により、類数が1である虚2次体が独立に決定されており、その系として上記の条件を満たす $q$ は $q = 2, 3, 5, 11, 17, 41$ のときに限られる。

ここで、任意の素数 $q$ に対し、2次多項式 $f_{q}$ を考えて

$\displaystyle P_1(q) = \frac{\# \{ X \in \mathbb{Z} \mid 0 \leq X\leq q-2 \;\; \text{s.t.}\;\; f_{q}(X)\colon \text{prime} \} }{q-1} \tag{2}$

とする。 $P_1(q)$ を素数生成確率と呼ぶことにする。名前の通り、 $0\leq X\leq q-2$ に対して $f_{q}(X)$ が素数になる割合を表す。

また、虚2次体 $K$ に対しその判別式を $d_K$ としたとき、対応する類数を $h_{d_K}$ と表すことにする。このとき、Rabinovitchの定理は次のように言い換えられる。

Theorem 1 (Rabinovitch, 1913)

$q$ を任意の素数とすると、次が成り立つ：

$P_1(q) = 1 \; \Longleftrightarrow \; h_{1-4q} = 1 \tag{3}$

上記の定理は類数1と $P_1(q) = 1$ が同値という主張であるが、類数が2以上については $P_1(q) < 1$ が成り立つ以上のことは言及されていない。先行研究においても、このような観点に基づく研究はないように思える。

そこで本研究では、計算機により虚2次体 $\mathbb{Q}(1-4q)$ の類数 $h_{1-4q}$ を計算し、特に類数 $2$ 以上のケースにおける $P_1(q)$ の振る舞いを観察する。 $P_1(q)$ が類数 $h_{1-4q}$ に反比例するというヒューリスティックな仮定に基づいて分析したところ、少なくとも $q < 100000$ においては $f_q$ は予想より素数になりやすいという「バイアス」が存在することを発見した。

2021-01-02

「数体の素元星座定理」に関するプレプリントについて

数学整数論素数おすすめの記事プレプリント紹介

2021年に入ってすぐに、とんでもないニュースが飛び込んできました。もちろん、数学のニュースです。

東北大学の研究チームによる論文のプレプリントがarXivで公開されました。タイトルは "Constellations in prime elements of number fields" で、こちらのリンクからアクセスできます：

Constellations in prime elements of number fields
Wataru Kai, Masato Mimura, Akihiro Munemasa, Shin-ichiro Seki, Kiyoto Yoshino
https://arxiv.org/abs/2012.15669

Wataru Kai, Masato Mimura, Akihiro Munemasa, Shin-ichiro Seki, Kiyoto Yoshinoの5名により発表されたプレプリントです。著者の一人であるShin-ichiro Seki（関真一朗）さんの名前は、今回の記事で何度か登場します。

上記の原稿はプレプリントですので、査読がなされたわけではありません。したがって、証明されたかどうかを確認するためには、自分で証明を読み込んで確認するほかありません。

普段、このようなプレプリントはなるべく紹介しないようにしているのですが、今回ばかりはどうしてもブログでご紹介したくなりました。というのも、証明されたとされる結果があまりにすごいからです！

英語で書かれた論文ですが、主定理の名称を日本語でいうなら

「数体の素元星座定理」

ということになります。いかにも興味をそそられる内容ですよね！

この「数体の素元星座定理」なる日本語訳については、関真一朗さんご自身のツイートから拝借させていただきました。