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

レピュニットの日

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

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

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

鳩ノ巣原理

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

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

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

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

証明

$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$ 通りなので，鳩ノ巣原理によって２つのレピュニット $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$

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