全てのSNNN数を割り切らない素数

更新日：2022/9/28

問題

全てのSNNN数を割り切ることができない素数は無限に存在するか？

— Hydrogen (@suiso_728660) July 16, 2017

平方剰余

この節では，前提知識として平方剰余の概念と諸法則を紹介する．

平方剰余とは，奇素数 $p$ を法とする合同式における平方数に相当する概念である． $$ \begin{align*} \text{$n$ が平方数} &\iff \text{ある整数 $x$ に対して }n=x^2 \\ \text{$n$ が法 $p$ の平方剰余} &\iff \text{ある整数 $x$ に対して }n\equiv x^2\mod{p} \end{align*} $$ 平方剰余でない数を平方非剰余という．ただし，$p$ の倍数は平方剰余でも平方非剰余でもないと約束する．

これらの概念を数式として表現するために，次のルジャンドル記号が用いられる．

定義 奇素数 $p$ と整数 $n$ に対し，ルジャンドル記号 $\leg{n}{p}$ を $$ \leg{n}{p}=\begin{cases} 1 & (\text{$n$ が法 $p$ の平方剰余}) \\ -1 & (\text{$n$ が法 $p$ の平方非剰余}) \\ 0 & (\text{$n$ が $p$ の倍数}) \\ \end{cases} $$ で定める．

ルジャンドル記号について，次のような性質が知られている．

1. $m\equiv n\mod{p}$ ならば $\leg{m}{p}=\leg{n}{p}$
2. $\leg{mn}{p}=\leg{m}{p}\leg{n}{p}$
3. 相異なる奇素数 $p,q$ に対して $\leg{p}{q}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\leg{q}{p}$ （平方剰余の相互法則）
4. $\leg{2}{p}=(-1)^{\frac{p^2-1}{8}}$ （第二補充法則）
5. 奇素数 $p,q$ が $p\equiv q\mod{4n}$ を満たすならば $\leg{n}{p}=\leg{n}{q}$

(1)〜(4) は有名であるので，証明は初等整数論の文献を参照されたい．(5) の証明を以下に与える．

証明

性質(2)より，$n$ が素数である場合について示せば十分である．

$n$ が奇素数である場合

性質(1),(3)より，示すべき式は $$ \begin{align*} && \leg{n}{p} &= \leg{n}{q} \\ &\iff& (-1)^{\frac{p-1}{2}\frac{n-1}{2}}\leg{p}{n} &= (-1)^{\frac{q-1}{2}\frac{n-1}{2}}\leg{q}{n} \\ &\iff& (-1)^{\frac{p-1}{2}\frac{n-1}{2}} &= (-1)^{\frac{q-1}{2}\frac{n-1}{2}} \\ &\iff& \frac{p-1}{2}\frac{n-1}{2} &\equiv \frac{q-1}{2}\frac{n-1}{2} \qquad\mod{2} \\ &\impliedby& \frac{p-1}{2} &\equiv \frac{q-1}{2} \qquad\mod{2} \\ &\iff& p-1 &\equiv q-1 \qquad\mod{4} \\ \end{align*} $$ であり，仮定 $p\equiv q\mod{4n}$ より所望の合同式を得る．

$n=2$ の場合

性質(4)より，示すべき式は $$ \begin{align*} && \leg{2}{p} &= \leg{2}{q} \\ &\iff& (-1)^\frac{p^2-1}{8} &= (-1)^\frac{q^2-1}{8} \\ &\iff& \frac{p^2-1}{8} &\equiv \frac{q^2-1}{8} \qquad\mod{2} \\ &\iff& p^2-1 &\equiv q^2-1 \qquad\mod{16} \\ \end{align*} $$ である．いま，$p\equiv q\mod{4\cdot 2}$ より $p-q$ は $8$ の倍数である．また，$p,q$ は奇数であるから $p+q$ は $2$ の倍数である．したがって $p^2-q^2=(p+q)(p-q)$ は $16$ の倍数，すなわち $p^2\equiv q^2\mod{16}$ であり，所望の合同式を得る．$\blacksquare$

解答

補題 $S_{a,b,s}$ を一般化SNNN数列，$p$ を $a-1$ と互いに素な奇素数とする．$p$ が条件 $$ \begin{align*} \leg{a}{p} &= 1, & \leg{bD}{p} &= -1 \end{align*} $$ を満たすならば，$p$ は $S_{a,b,s}$ の全ての項を割り切らない．

証明

背理法で示す．$p$ が $S_{a,b,s}(n)$ を割り切ると仮定すると $$ \frac{Da^n-b}{a-1} \equiv 0 \mod{p} $$ であり，$p$ は $a-1$ と互いに素であるから $$ Da^n \equiv b \mod{p} $$ が成り立つ．ここでルジャンドル記号の性質(1)を用いると $$ \leg{Da^n}{p} = \leg{b}{p} $$ を得る．このとき，仮定 $\leg{bD}{p}=-1$ から $\leg{D}{p}\neq 0$ であり，$\leg{D}{p}=\leg{D}{p}^{-1}$ が成り立つことなどに注意して $$ \begin{align*} \leg{D}{p}\leg{a}{p}^n &= \leg{b}{p} \\ \leg{a}{p}^n &= \leg{b}{p}\leg{D}{p} \\ \leg{a}{p}^n &= \leg{bD}{p} \\ 1^n &= -1 \\ \end{align*} $$ となり，矛盾が導かれる．よって補題が成立する．$\blacksquare$

定理 全てのSNNN数を割り切らない素数は無数に存在する．

証明

SNNN数列 $S_{10,7,3}$ と素数 $31$ について $$ \begin{align*} \leg{a}{31} &= \leg{10}{31} = 1, & \leg{bD}{31} &= \leg{7\cdot 34}{31} = -1 \end{align*} $$ が成立する．ここで $p\equiv 31\mod{4abD}$ すなわち $p\equiv 31\mod{9520}$ を満たす素数 $p$ を考えると，ルジャンドル記号の性質(5)より $$ \begin{align*} \leg{a}{p} &= \leg{a}{31} = 1, & \leg{bD}{p} &= \leg{bD}{31} = -1 \end{align*} $$ であるから，$p$ は補題の条件を満たす．よって，$p=9520k+31$（$k$ は自然数）と表される素数 $p$ は全てのSNNN数を割り切らない．ここで $9520$ と $31$ は互いに素であるから，算術級数定理より，この条件を満たす $p$ は無数に存在する．したがって定理が成立する．$\blacksquare$