素数の性質と証明
素数は整数論の基礎です。素数に関する重要な定理と証明方法を学びます。
素数の定義と基本性質
素数：1より大きく、1と自身以外の約数を持たない自然数
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
素数の無限性（ユークリッドの証明）：素数は無限に存在する。
📘 例題①（素数の無限性の証明）
背理法：素数が有限個（p₁, p₂, …, pₙ）と仮定する。
N = p₁×p₂×…×pₙ + 1 とおく。
N はどの pᵢ でも割り切れない（余りが1）。
→ N の素因数はリスト外の素数 → 矛盾 → 素数は無限個 ■
背理法：素数が有限個（p₁, p₂, …, pₙ）と仮定する。
N = p₁×p₂×…×pₙ + 1 とおく。
N はどの pᵢ でも割り切れない（余りが1）。
→ N の素因数はリスト外の素数 → 矛盾 → 素数は無限個 ■
素数の判定
n が素数かどうかの判定：√n 以下の素数で割り切れないか調べる
📘 例題②（素数判定）
127 が素数かどうか判定せよ。
√127 ≈ 11.3。2,3,5,7,11 で割り切れるか確認：
127÷2=63.5（×）、127÷3（1+2+7=10:×）、127÷5（末尾2,7:×）
127÷7=18.1…（×）、127÷11=11.5…（×）
解答：127 は素数
127 が素数かどうか判定せよ。
√127 ≈ 11.3。2,3,5,7,11 で割り切れるか確認：
127÷2=63.5（×）、127÷3（1+2+7=10:×）、127÷5（末尾2,7:×）
127÷7=18.1…（×）、127÷11=11.5…（×）
解答：127 は素数
💡 ポイント
- 素数判定：√n以下の素数で試し割り
- 偶数の素数は2のみ
- 3以上の素数はすべて奇数
- 「p が素数、p|ab → p|a または p|b」（重要定理）
練習問題
- 101 が素数かどうか判定せよ。
- p が素数で p|n² ならば p|n であることを示せ。
- 2以上の連続した2整数 n と n+1 がともに素数になるのは n=2 のみであることを示せ。
解答・解説
- √101≈10.05。2,3,5,7で確認：101÷7=14.4…（×）→ 101は素数
- p|n² = p|n×n。p が素数なので p|n または p|n → p|n ■
- n≥3 のとき n か n+1 の少なくとも一方は偶数（連続整数）。偶数が素数なのは2のみ→ n=2 または n+1=2。n=2 → n+1=3（どちらも素数 ✓）。n+1=2 → n=1（素数でない×）。n=2のみ ■