13

2と5以外の総ての素数がレピュニットの素因数として現れることの証明

351
0
$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

レピュニットの日

本日は11月11日,見事に$1$が並びました.$11$$11111$のように,総ての桁にずらと$1$が並ぶ数をレピュニットと言い,これにちなんで11月11日はレピュニットの日なのだそうです.だそうです,というあたりにぼくの姿勢がうかがわれます.

それでもレピュニット自体にはおもしろい性質があるようで,今回はその中から次の定理をご紹介します.

レピュニットの素因数

$2$,$5$ を除く総ての素数はあるレピュニットの素因数となる.

$1$を並べる」というシンプルな数の列の中にほぼ総ての素数が埋まっているのは,好きな人にはたまらないロマンなのかもしれません.

鳩ノ巣原理

今回はこの定理を鳩ノ巣原理によって証明しましょう.個人的には定理1よりも鳩ノ巣原理の方が好きです.

鳩ノ巣原理

有限集合 $X$, $Y$$\#X > \#Y$ を充たすとき,任意の写像 $f \colon X \to Y$ に対して $\# f^{-1}(y) > 1$ なる $y \in Y$ が存在する.

鳩ノ巣原理という呼称の由来は,この定理を鳩の巣と卵で喩えるからです.いくつかの鳩の巣に卵が入っています.$X$ を卵の集合,$Y$ を巣の集合とし,写像 $f$ を卵 $x$ をそれが入っている巣 $y$ に対応づけるものだと見做しましょう.このとき,$f^{-1}(y)$ は巣 $y$ に入っている卵の全体と言えて,この定理は

卵の数が巣の数よりも多ければ,ある巣には2個以上の卵が入っている

とまとめられます.これは直観的には明らかと言ってよい事柄だと思うのですが(もちろん証明はできます)様々な結果を導く強い補題でもあるのです.

証明

$n$ 番目のレピュニット,すなわち $1$$n$ 個並んだ数
$$ \overbrace{111 \cdots 1}^n$$
$R_n$ と表します.$p+1$ 個のレピュニット $R_1, R_2, \ldots, R_{p+1}$$p$ で割った剰余で類別します.$p$ で割った剰余は $0, 1, \ldots, p-1$$p$ 通りなので,鳩ノ巣原理によって2つのレピュニット $R_s, R_t$$s < t$ としてよい)が同じ剰余をもち,特に $R_t - R_s$$p$ で割り切れます.ところで
$$ R_t - R_s = \overbrace{11\cdots 1}^{t-s}\overbrace{00\cdots 0}^{s} = R_{t-s} \times 10^s$$
と整理され,$p$$10$ と互いに素ですから $R^{t-s}$ を割り切ります.$\square$

この切れ味の良さは何度使っても気持ちがいいものです.添付の動画には,もうひとつ鳩ノ巣原理を使って得られる結果をご紹介しています.皆様も是非,鳩ノ巣原理の楽しさをご堪能ください.

投稿日:20201111

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

龍孫江
龍孫江
111
11045
代数学(群論・環論・体論)の問題を解説するYouTubeチャンネル「龍孫江の数学日誌」を運営しております(リンクからどうぞ).YouTubeでは扱いきれないまとまった記事を書いていきたいと思います.どうぞご贔屓に.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中