問題はこちら（画像をクリックするとPDFファイルで開きます。）
仮想難関大シリーズということで、東大、京大をはじめとする旧帝大、東工大、国公立大学医学部医学科などの難関国公立大を想定したオリジナルの自作問題です。
「手垢の付いていない問題で力試しがしたい」
という方はぜひご活用ください。
今回は整数の問題です。
等差数列の中で連続する素数の個数を考える問題です。
これについては
グリーン・タオの定理
任意の正の整数 \(n\) に対して、\(n\) 個の項からなる素数等差数列が存在する。
というテレンス・タオ氏の定理が有名です。
本問の (3) は
- 公差 \(4\) の等差数列では、素数が４連続することはない。
本問の (4) は
- 公差 \(d\) が \(0 \lt d \lt 2023\) である等差数列では、素数が \(12\) 連続となることはない。
ということを示す問題です。
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む
(1) について
\(r_{i}=r_{j}\) となる \(i\) , \(j\) の存在を仮定し、矛盾を導く背理法を狙っていきます。
\(im \equiv jm \pmod p\) を満たす \(i\) , \(j\) ( ただし、\(1 \leq i \lt j \leq p-1\) ) が存在すると仮定すると、
\((j-i)m \equiv 0 \pmod p\)
ということになり、
\((j-i)m\) が \(p\) の倍数
ということになります。
\(m\) は素数 \(p\) の倍数でないことから、\(j-i\) が \(p\) の倍数ということになり、
\(i \equiv j \pmod p\)
が成り立ちます。
ただ、今この \(i\) , \(j\) は \(1\) 以上 \(p-1\) 以下の整数であるため、
\(i=j\)
ということになり、\(i \lt j\) ということに矛盾します。
(2) について
(1) から分かったことは
- \(r_{1} \ , \ r_{2} \ , \ \cdots \ , \ r_{p-1}\) には重複はない
ということです。
つまり、２つの集合
- \(A=\{r_{1} \ , \ r_{2} \ , \ \cdots \ , \ r_{p-1}\}\)
- \(B=\{1 \ , \ 2 \ , \ \cdots \ , \ p-1\}\)
という集合が一致することを目指します。
鳩の巣原理
\(n\) 羽の鳩が \(n-1\) 個以下の巣箱に入るとき、\(2\) 羽以上鳩が入っている巣箱が少なくとも１つ存在する。
という原始的な原理を用いるため、(1) ができればほぼ自明に近いと感じる人もいるでしょう。
(3) について
\(q\) , \(q+4\) , \(q+8\) , \(q+12\) が全て素数となることはないということを示すわけです。
基本的に
どれかに合成数が紛れ込む
ということを示す方向性となります。
\(4\) , \(8\) , \(12\) が
- \(4 \equiv 1 \pmod 3\)
- \(8 \equiv 2 \pmod 3\)
- \(12 \equiv 0 \pmod 3\)
ということに注目し、\(q\) を \(3\) で割った余りで分類すればよいでしょう。
(4) について
今度は \(q \ , \ q+d \ , \ \cdots \ , \ q+11d\) が全て素数となることはないことを示します。
(3) と違って公差 \(d\) が具体的には与えられていません。
ただ、
\(q \ , \ q+d \ , \ \cdots \ , \ q+11d\) のどれかに合成数が紛れ込む
という方向性は引き続き睨んでいきます。
(1) , (2) の主張は、\(d\) が素数 \(p\) で割り切れないとき
- \(d \ , \ 2d \ , \ \cdots \ , \ (p-1)d\) を素数 \(p\) で割った余りは \(1 \ , \ 2 \ , \ \cdots \ , \ p-1\) と１対１対応する。
というものです。
例えば \(d\) が \(5\) で割り切れないときを考えてみます。
以下、合同式の法を \(5\) とします。
\(d \equiv 1\) のとき
\(2d \equiv 2 \ , \ 3d \equiv 3 \ , \ 4d \equiv 4\)
\(d \equiv 2\) のとき
\(2d \equiv 4 \ , \ 3d \equiv 1 \ , \ 4d \equiv 3\)
\(d \equiv 3\) のとき
\(2d \equiv 1 \ , \ 3d \equiv 4 \ , \ 4d \equiv 2\)
\(d \equiv 4\) のとき
\(2d \equiv 3 \ , \ 3d \equiv 2 \ , \ 4d \equiv 1\)
と、いずれのケースにおいても、
- \(d \ , \ 2d \ , \ 3d \ , \ 4d\) を \(5\) で割った余りは \(1 \ , \ 2 \ , \ 3 \ , \ 4\) と１対１対応
しています。
\(q \equiv 1 \ , \ 2 \ , \ 3 \ , \ 4\) でしたから、
\(q+kd \equiv 0\)
となる \(k\) (\(k=1 \ , \ 2 \ , \ \cdots \ , \ 4\)) が存在することになり、合成数が紛れ込んでしまいます。
これにより、\(d\) が \(5\) の倍数でないといけないことになるわけです。
同様にして、\(d\) が \(2\) の倍数、\(3\) の倍数、\(7\) の倍数、\(11\) の倍数である必要性も出てくるため、
\(d\) は \(2310\) の倍数
ということになりますが、\(0 \lt d \lt 2023\) であるため、矛盾してしまい、背理法により題意が示されます。
解答はコチラ
