Arithmetica

フィボナッチ数と平方数, 記数法.

Arithmetica 算術ノート

あるリュカ数列を用いた 3𝒏 + 1 型の素数の無数性の証明

 3 で割って 1 余る素数は無数に存在する.

 

この記事では, 以下を目標として上記の定理を証明します.

  • \ 2\ 通りの方法で\ 3n+1\ 型の素数の無数性を証明する. 



前提知識

三項間漸化式の解法, ユークリッド (Euclid, エウクレイテス) の互除法, フェルマ (Fermat) の小定理, (合同式における)位数, 平方剰余の相互法則など







円分多項式を用いた証明

恐らくこちらの方法が一般的です. 任意の正整数\ a\ に対する\ an+1\ 型の素数の無数性も,  少しの工夫を加えればこの方法によって証明することができ,  高木先生の『初等整数論講義』などに載せられています.


通常の素数の無数性の証明方法(Euclidの方法)と同様に, 有限個の\ 3n+1\ 素数から新しい\ 3n+1\ 素数が得られることを示し, 帰納的に証明します. したがって目標は

  • 初めに用意した\ 3n+1\ 型の素数のいずれでも割り切れないような数をつくる.
  • その数の素因数として, \ 3n+1\ 型であるようなものを, 初めに用意したものの他に見つける.

二番目の条件については, \ n^3-1\ の因数(円分多項式\ n^2+n+1\ を考えれば, 位数の議論から\ 3\ 以外のすべての素因数が\ 3n+1\ 型であることがわかります. \ n^3-1\ の素因数を使っても同様の方法で証明することはできますが, 実質的にいってこの証明において着目するのは\ n^2+n+1\ の素因数のみなので, ここでは\ n^2+n+1\ を用います.

補題 1 正整数\ n\ に対し, \ n^2+n+1\ \ 3\ でない素因数は必ず\ 3n+1\ 型である.

証明. \ p\neq3\ \ n^2+n+1\ の素因数の\ 1\ つとする. このとき\ p\mid(n-1)(n^2+n+1)\ より\ n^3\equiv1\ \ ({\rm mod}\ p)\ であって, \ n\equiv1\ \ ({\rm mod}\ p)\ を仮定すると \begin{align} n^2+n+1\equiv3\not\equiv0\ \ ({\rm mod}\ p) \end{align} となって不合理であるから, \ n\ \ {\rm mod}\ p\ における位数は\ 3\ である. Fermatの小定理より\ n^{p-1}\equiv1\ \ ({\rm mod}\ p)\ が成り立つことと合わせれば, \ 3\mid p-1\ が得られる.

\Box

 

定理 2 \ 3n+1\ 型の素数は無数に存在する.

証明. 与えられた\ 3\ で割って\ 1\ 余る素数\ p_1,\ p_2,\ \ldots,\ p_i\ に対し, それらのすべての積を\ M\ とし, \begin{align} N=(3M)^2+3M+1 \end{align} とおく. 補題より\ N\ の素因数\ r\ はすべて\ 3n+1\ 型であり, かつ, \ Q\ \ p_1,\ p_2,\ \ldots,\ p_i\ のいずれでも割り切れないから, 新たな\ 3n+1\ 型の素数\ r\ が得られた. よって再帰的に\ 3n+1\ 型の素数を構成することができ, その無数性がしたがう.

\Box






あるLucas数列を用いた証明

証明の大枠は先ほどの証明とほぼ同じですが, この証明では, 相互法則と第一補充則により \begin{align} p\equiv1\ \ ({\rm mod}\ 3)\Longleftrightarrow\left(\frac{-3}{p}\right)=1 \end{align} であることを利用します.


(一部の例外を除き) 非零整数の組\ (P,Q)\ について, 漸化式 \begin{align} u_0=0,\ u_1=1,\ u_{n+2}=Pu_{n+1}-Qu_n \end{align} によって定義される数列\ (u_n)_{n\geq0}\ を第二種Lucas数列といい, 以下のような性質が知られています.

\ (P,Q)=(1,-1)\ のとき\ u_n\ はFibonacci数になります.
定理 3 \ \gcd(u_m,u_n)=u_{\gcd(m,n)}.\
系 4 \ \gcd(u_{n+1},u_n)=1.\
定理 5 \ u_{2n+1}=u_{n+1}^2-Qu_n^2.\
補題 6 \ u_n\ \ (P,Q)=(1,-3)\ に対応するLucas数とする. このとき, 奇数番目項\ u_{2n+1}\ の奇数の素因数は必ず\ 3n+1\ 型である.

証明. 明らかに\ 3\nmid u_n\quad(n\neq0)\ であるから, \ p\ \ u_{2n+1}\ の奇数の素因数とすれば\ p\neq3\ である. このとき, 等式 \begin{align} u_{2n+1}=u_{n+1}^2+3u_n^2 \end{align} において\ p\mid u_n\ を仮定すると, \ p\mid u_{n+1}\ となり系 4 に反する. よって\ p\nmid u_n\ であって, \ {\rm mod}\ p\ における\ u_n\ の逆元\ u'\ が存在し, \ (u')^2\ を両辺にかけて\ {\rm mod}\ p\ をとると \begin{align} (u'u_{n+1})^2\equiv-3\ \ ({\rm mod}\ p). \end{align} よって\ -3\ \ {\rm mod}\ p\ の平方剰余であり, \ p\neq2,3\ であったから\ p\equiv1\ \ ({\rm mod}\ 3).\

\Box
定理 2 \ 3n+1\ 型の素数は無数に存在する.

証明. 相異なる奇素数\ p,\ q,\ \ldots\ に対して, 補題より\ u_p,\ u_q,\ \ldots\ \ 3n+1\ 型の素因数を持つが, 定理 3 から\ u_p,\ u_q,\ \ldots\ はどの\ 2\ つも互いに素なので, これらに重複はない. 奇素数は無数に存在するから, \ 3n+1\ 型の素数が無数に存在することが証明された.

\Box


\ (P,Q)=(1,-1)\ に対応するFibonacci数列\ (F_n)\ を用いれば, 上と同じ手法により\ 4n+1\ 素数の無数性を証明できます.





[tex: ]


ALIA VERITAS AD ALIAM SEMPER VIAM STERNIT
ひとつの真理の考究は, かならずまたひとつの真理への道を拓く


フィボナッチ数とは, 黄金比の冪を √5 を用いて表示したときに, 無理数部に現れる分数の二倍である.

\begin{align} (F_n)_{n\geqslant0}=\;&0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233,\ 377,\ 610,\ 987,\ \\&1597,\ 2584,\ 4181,\ 6765,\ 10946,\ 17711,\ 28657,\ 46368,\ 75025,\ \ldots. \end{align}



平方数とは, 或る整数の平方に等しい数である.

\begin{align} (n^2)_{n\geqslant0}=\;&0,\ 1,\ 4,\ 9,\ 16,\ 25,\ 49,\ 64,\ 81,\ 100,\ 121,\ 144,\ 169,\ 196,\ 225,\ 256,\ \\&289,\ 324,\ 361,\ 400,\ 441,\ 484,\ 529,\ 576,\ 625,\ \ldots. \end{align}



pic-Arithmetica

算 術 ノ ー ト

Arithmētica はラテン語の第一変化名詞で, 算術や初等的な整数論を意味します. 当ブログでは, 算術と整数論, 特にフィボナッチ数や平方数に関する事柄, 面白いと感じた問題, そして数論における定理について, 気ままに記事を投稿します. 記事の内容に関する誤植や新しい発見などが有りましたら, 私の Twitter アカウント (@Numerus_A) までご報告頂けますと幸いに思います.

読者になる