2022-10-19

極大超プーレ数とフェルマー商の素因数分解

数学素数整数論プーレ数

超プーレ数 $m$ があったとき、その約数 $d$ は定義より超プーレ数・素数・1 のいずれかです。

超プーレ数に対してその約数が多ければ多いほど、多くの超プーレ数を内部に持つことになります。今回は「約数をできるだけ多く持つような超プーレ数」を考えたいと思います。

プーレ数や超プーレ数の定義、基本的な性質についてはこちらの記事で紹介しています：
tsujimotter.hatenablog.com

すなわち、次のような定義が自然に思いつきます。

定義（極大超プーレ数）

超プーレ数 $m$ に対して、 $m$ より大きな超プーレ数 $M$ であって $m \mid M$ なるものが存在しないとき、 $m$ を極大超プーレ数（maximal super-Poulet number）といいます。

つまり、これ以上親がいないような、極大の親玉であるような超プーレ数のことを指すわけですね。

ちなみに「極大」は "maximal" の訳語です。"maximal super-Poulet" に対応する日本語訳が定着していないので私がオリジナルでつけた訳語となります。

"maximal" の訳として「最大」も候補に挙がるのですが、すべての超プーレ数の中で一番大きいわけではないので適切ではないように考えています。

2022-10-17

プーレ数の平方因子とヴィーフェリッヒ素数

数学素数整数論プーレ数

前回に引き続き「超プーレ数」の話題です。今朝投稿されたばかりの次のYouTube動画に関する話題について、ブログでもより深く解説してみたいと思います。

www.youtube.com

前回紹介したときに現れた超プーレ数の例は

$341 = 11 \times 31$

$1387 = 19 \times 73$

$2047 = 23 \times 89$

$2701 = 37 \times 73$

$3277 = 29 \times 113$

のように、平方因子を持たないものばかりでした。果たして、平方因子を持つような超プーレ数は存在するのでしょうか？

2022-10-10

プーレ数と超プーレ数

数学素数整数論プーレ数

明日話したくなる「数」のお話シリーズの最新動画で超プーレ数という概念を紹介しました。

www.youtube.com

動画内でいくつか定理を紹介しましたが、証明までは説明しませんでした。このブログ記事では動画の補足情報として、動画で紹介できなかった証明部分を紹介したいと思います。

2022-09-16

エラトステネスの篩を数式で表すと・・・？

数学素数整数論

素数の一覧表を作るときに、一個一個の数を素数かどうか判定していくのもよいですが、もう少し効率的に行う方法があります。

その方法の一つがエラトステネスの篩（ふるい）です。

エラトステネスの篩は、情報系の大学生であればプログラミングの演習等で一度は実装したことがあるかと思いますが、実に「アルゴリズム的」なものです。説明の際は「手順」を説明されることが多く、私はこれを数式で表そうと考えたことがありませんでした。

ところが、Wikipediaを見ると、エラトステネスの篩はこんな数式で表せると書いてあります。

$\displaystyle \newcommand{\HRNO}{\unicode[sans-serif]{x306E}} \pi(n) - \pi(\sqrt{n}) + 1 = \sum_{d \mid P(\sqrt{n})} \mu(d) \left\lfloor\frac{n}{d}\right\rfloor \tag{1}$

細かい定義は次のとおりですが、本文の中で順に説明していきます。

$\pi(x)$ ： $x$ 以下の素数の個数
$P(z)$ ： $z$ 以下のすべての素数を掛け合わせて得られる数
$\mu(n)$ ：メビウス関数
$\lfloor x \rfloor$ ：ガウス記号（ $x$ を超えない最大の整数）
$a \mid b$ ： $a$ は $b$ を割り切る

こんな風に表せるのか！と驚いた一方で、これはいったいどういうことなんだろうとも思いました。

実際、式 $(1)$ の意味するところは何なのか、初見ではあまりよくわかりません。そこでこの記事では、式 $(1)$ の意味を理解し、どのようにして導かれるのかを理解するために順を追って解説したいと思います。

2022-09-12

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

数学整数論素数

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

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

定理

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

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

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

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

2022-03-14

(987654321-1)/(123456789+1) がちょうど 8

数学整数論

最近、タイムラインで

$\displaystyle \frac{987654321}{123456789} \fallingdotseq 8$

という話をよくみかけます。とても面白い現象ですね。

この問題については、id:egory_cat さんのブログにて、一般の $n$ 進法に対して証明が与えられています。
egory-cat.hatenablog.com

ブログを拝見させていただきましたが、とても面白かったです！

要するに、分子の数 $987654321$ は

$\displaystyle f(n) = \sum_{k=1}^{n-1} k n^{k-1}$

に対して $n = 10$ を代入した数であり、分母の数 $123456789$

$\displaystyle g(n) = \sum_{k=1}^{n-1} (n-k) n^{k-1}$

に対して $n = 10$ を代入した数であり、これらの比

$\displaystyle \frac{f(n)}{g(n)}$

の小数部分が十分小さな値となることを示せるわけですね。

一方で、Twitter上でこんなツイートも見かけました：

(987654321-1)/(123456789+1) = 8 pic.twitter.com/KWrcpmyF11
— Poo-Sung Park (@puzzlist) 2021年3月30日

なるほど、上の記号を用いて

$\displaystyle \frac{f(10)-1}{g(10)+1} = 8$

が成り立つと言うわけですね。これは面白い。

この関係から、一般の $n$ 進法において

$\displaystyle \frac{f(n)-1}{g(n)+1} = n-2$

が成り立つことを示唆されますが、これは成り立つのでしょうか。

その答えはイエスです！

一般の $n$ で成り立ちますので、実際に証明してみましょう！

id:egory_cat さんの記事より

$\displaystyle f(n) = \frac{(n-2)n^n + 1}{(1-n)^2}$

$\displaystyle g(n) = \frac{n^n - (n^2 - n + 1)}{(1-n)^2}$

が成り立ちますので、これを使って変形しましょう。

$\displaystyle \begin{align} f(n) - 1 &= \frac{(n-2)n^n + 1}{(1-n)^2} - 1\\ &= \frac{(n-2)n^n + 1 - 1 + 2n - n^2}{(1-n)^2} \\ &= \frac{(n-2)n^n + 2n - n^2}{(1-n)^2} \\ &= \frac{n(n^n - n) + 2(n^n - n)}{(1-n)^2} \\ &= \frac{(n^n - n)(n-2)}{(1-n)^2} \end{align}$

$\displaystyle \begin{align} g(n) + 1 &= \frac{n^n - (n^2 - n + 1)}{(1-n)^2} + 1\\ &= \frac{n^n - (n^2 - n + 1) + 1 - 2n + n^2}{(1-n)^2} \\ &= \frac{n^n - n}{(1-n)^2} \end{align}$

したがって

$\displaystyle \frac{f(n) - 1}{g(n) + 1} = \frac{(n^n - n)(n-2)}{(1-n)^2} \cdot \frac{(1-n)^2}{n^n - n} = n-2$

となり、綺麗に $n-2$ だけが残りましたね！

元の問題に立ち返ってみると、この式の分母を「ちょっと小さく」して、分子の方を「ちょっと」大きくすると、 $n-2$ より少しだけ大きな値になるというわけなんですね。

いやー、数学ってうまいことできていますね！！

これで証明は完了しましたが、少し疑問が残りました。この結果って、定義に戻って考えると

$\displaystyle \sum_{k=1}^{n-1} k n^{k-1} - 1 = (n-2) \left(\sum_{k=1}^{n-1} (n-k) n^{k-1} + 1\right)$

ということを表しているわけですよね。これって級数のままで証明できたりしないでしょうか。

もし思いついた方がおられましたら、コメントで教えていただけるとうれしいです。

それでは今日はこのへんで！
（とても楽しい記事を公開してくださった id:egory_cat さんに感謝です！）

追記

最後の

$\displaystyle \sum_{k=1}^{n-1} k n^{k-1} - 1 = (n-2) \left(\sum_{k=1}^{n-1} (n-k) n^{k-1} + 1\right)$

という式ですが、直接証明する方法をOTTYさんから教えていただきました。許可をいただきましたので、転載させていただきます。

$f(n), g(n)$ に加えて、 $h(n)$ を次のように定義します。

$\displaystyle h(n) = \sum_{k=1}^{n-2} (n-k-1)n^{k-1}$

これは $n = 10$ と代入すれば、 $h(10) = 12345678$ となります。つまり、 $g(n)$ の最後の桁だけ抜いた数というわけですね。

ここで、次のような関係が成り立ちます：

$\displaystyle f(n) + h(n) = (n-1) \sum_{k=1}^{n-1} n^{k-1} \tag{1}$

$\displaystyle g(n) - h(n) = \sum_{k=1}^{n-1} n^{k-1} \tag{2}$

$\displaystyle g(n) - n h(n) = n-1 \tag{3}$

$(1), (2), (3)$ はそれぞれ

$\displaystyle 987654321 + 12345678 = 999999999 \tag{1'}$

$\displaystyle 123456789 - 12345678 = 111111111 \tag{2'}$

$\displaystyle 123456789 - 123456780 = 9 \tag{3'}$

と対応しています。

これらを使うと、次のように目的の式が得られます：

$\displaystyle \begin{align} f(n) - 1 &= (n-1)\sum_{k=1}^{n-1} n^{k-1} - h(n) - 1 \\ &= (n-1) (g(n) - h(n)) - h(n) - 1 \\ &= (n-1) g(n) - n h(n) - 1 \\ &= (n-2) g(n) + g(n) - n h(n) - 1 \\ &= (n-2) g(n) + (n-1) - 1 \\ &= (n-2) (g(n) + 1) \end{align}$