(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\) であるため、矛盾してしまい、背理法により題意が示されます。
解答はコチラ
※閲覧にはログインまたは会員登録(有料)が必要です。
上の赤いボタンをクリックすると新規登録画面が開きます。
すでに有料会員登録している方ここでログイン
