「いずれも素数」系問題のハイレベル完全攻略

パソコン・タブレットなど、画面の大きい端末での閲覧を推奨します。

「いずれも素数」型整数問題の完全攻略

―法を当てるのではなく、式の構造から作る

はじめに

ごきげんよう、みなさま。まずはご覧くださりありがとうございます。
今回扱うのは、

いくつかの式が、いずれも素数となるような整数を求めよ。
という形の整数問題です。
この種の問題では、合同式を利用して、どれかの式を小さな素数の倍数にすることがよくあります。しかし、実際に解こうとすると、次の疑問が生じます。
なぜ法3を考えるのか。
なぜ法5を考えるのか。
小さい素数を順番に試し、たまたま当たったものを使っているだけではないのか。
本記事の目標は、法3や法5を使う典型問題を暗記することではありません。
$$ \boxed{\text{なぜその法を選ぶのかを、式の構造から説明できるようになること}} $$
を目指します。
先に結論を述べると、この種の問題では、複数の式から「変数によって動く共通部分」を取り出し、次の三点を調べます。

1. その共通部分が、ある法でどの余りを取り得るか。
2. 各式は、共通部分がどの余りのときに小さな素数の倍数になるか。
3. 各式によって、取り得る余りをすべて覆えるか。
   一次式、平方数、立方数、指数、分数など、見た目が異なる問題でも、核となる操作は同じです。違うのは主に、共通部分が取り得る余りをどのように求め、どのように少なくするかという点です。
   本記事の読破にはそれ相応の胆力や力がいるかと思います。
   が、特段珍しい知識が必要なわけでは有りません。
   例えば合同式を初めて学ぶ方も読めるように、まず合同式、その後に集合の記号を説明します。集合の説明には余りの例が必要になるため、合同式を先に置いています。
   仮に初学者なら読破にはやはり胆力が鍵でしょう。
   厳しいと思った方には姉妹記事スタンダードの方をお勧めします。

目次

• 第0部　合同式の完全基礎
• 第1部　集合の基礎
• 第2部　最初の具体例
• 第3部　すべての核となる包囲原理
• 第4部　前処理と一文字化
• 第5部　自由な整数・一次式型
• 第6部　素数などの特殊条件
• 第7部　平方剰余・立方剰余・一般の累乗剰余
• 第8部　因数分解と指数型
• 第9部　分数の形をした式
• 第10部　一つの法では終わらない場合
• 第11部　余分な式とカモフラージュ
• 第12部　ここまでの解法は、すべて同じである
• 第13部　構造が見えない場合の実験
• 第14部　完全攻略フローチャート
• 第15部　総合問題
• 第16部　総合問題の解答・解説
• 第17部　最後の問題とおわりに

第0部　合同式の完全基礎

この部では、本記事で必要になる合同式の知識を一から説明します。後で使う約分や周期の根拠も、単なるルールとして置かずに確認します。

0.1　素数・合成数・倍数

たとえば、2、3、5、7は素数であり、4、6、8、9は合成数です。

たとえば、$5\mid30$ ですが、$5\nmid32$ です。本記事では文章の読みやすさを優先し、「$A$ は $d$ の倍数である」と書く場合も多くあります。

0.2　整数を余りの部屋に分ける

整数は無数にありますが、3で割った余りだけを見るなら、すべての整数は $0,1,2$ の三種類に分かれます。どの整数 $n$ も、ある整数 $k$ を用いて、
$$ n=3k,\qquad n=3k+1,\qquad n=3k+2 $$
のいずれかに表せるからです。本記事では、この三種類を「法3における余りの部屋」と呼ぶことがあります。

0.3　合同式の定義

たとえば、17と2を5で割った余りはどちらも2なので、
$$ 17\equiv2\pmod5 $$
です。また、$17-2=15$ は5の倍数です。一般に、次の二つは同じ意味です。

ここで $\Longleftrightarrow$ は、「左が成り立つことと右が成り立つことが同じである」という意味です。

0.4　負の余り

法3では、
$$ 2\equiv-1\pmod3 $$
です。実際、$2-(-1)=3$ は3の倍数です。したがって、法3の余りを $0,1,2$ ではなく、$0,1,-1$ と表しても構いません。
同様に、法5では $0,1,2,-2,-1$ と表せます。負の余りを用いると、$X-1,X,X+1$ のような対称的な形が見えやすくなります。

0.5　合同式で行ってよい計算

たとえば、$F(x)=x^2+2x+3$ とします。$n\equiv2\pmod5$ なら、
$$ F(n)\equiv2^2+2\cdot2+3=11\equiv1\pmod5 $$
です。

0.6　互いに素とベズーの等式

合同式の約分を根拠から説明するため、次の事実を確認します。

0.7　合同式では自由に割れない

たとえば、$2x\equiv2\pmod4$ から $x\equiv1\pmod4$ とはいえません。実際、$x=3$ も元の合同式を満たします。分かるのは、$x$ が奇数、すなわち $x\equiv1\pmod2$ であることまでです。

たとえば、$2x\equiv2\pmod5$ なら、2と5は互いに素なので $x\equiv1\pmod5$ と約分できます。

0.8　素数を法とする積

法が合成数の場合には、この性質は一般に成り立ちません。たとえば、$2\cdot3\equiv0\pmod6$ ですが、2も3も6の倍数ではありません。

0.9　法も同時に小さくなる割り算

実際、$A-B$ が $dm$ の倍数なので、$(A-B)/d$ は $m$ の倍数です。たとえば、$2x\equiv6\pmod{10}$ なら、両辺と法を2で割って $x\equiv3\pmod5$ とできます。

0.10　大きな法から小さな法へ

たとえば、$a\equiv b\pmod6$ なら $a\equiv b\pmod2$ かつ $a\equiv b\pmod3$ です。なお、この例では逆も成り立ちます。差が2の倍数かつ3の倍数なら、2と3が互いに素なので差は6の倍数になるからです。ただし、$a\equiv b\pmod2$ だけから $a\equiv b\pmod6$ を導くことはできません。

0.11　素数の倍数になった場合

したがって、本記事では次の流れを繰り返します。

1. どれかの式が小さな素数 $q$ の倍数になることを示す。
2. その式も素数なら、値は $q$ そのものでなければならない。
3. 「式 $=q$」を解いて候補を求める。
4. 元のすべての条件へ戻って確認する。

0.12　余りの表

平方数を法5で調べると、次の表になります。

したがって、平方数が法5で取り得る余りは $0,1,4$ です。元の数には5種類の余りがありますが、平方すると3種類に集まります。この「余りの種類が減る」という現象が、後の平方剰余の中心です。

0.13　多項式と累乗の周期

整数係数多項式 $F(n)$ について、$n+m\equiv n\pmod m$ なので、
$$ F(n+m)\equiv F(n)\pmod m $$
です。したがって、$F(n)$ を法5で調べるなら、$n=0,1,2,3,4$ の5場合を調べれば十分です。
累乗では、たとえば法5で、
$$ 2^1\equiv2,\quad2^2\equiv4,\quad2^3\equiv3,\quad2^4\equiv1 $$
となり、その後は $2,4,3,1$ が繰り返されます。

$a^T\equiv1\pmod m$ なら、
$$ a^{n+T}=a^na^T\equiv a^n\pmod m $$
なので、$T$ は $a^n$ の余りの周期です。ただし、最小周期は $T$ より小さいことがあります。

0.14　フェルマーの小定理

0.15　最小周期はなぜ $q-1$ の約数か

フェルマーの小定理から、$a^n$ の法 $q$ における周期として $q-1$ を使えます。さらに、最小周期について次が成り立ちます。

特に $T=q-1$ とすれば、最小周期 $t$ は $q-1$ の約数です。たとえば法7では、$2^1\equiv2$、$2^2\equiv4$、$2^3\equiv1$ なので、最小周期は3です。

0.16　狙う素数と作業する法

たとえば、整数 $A/2$ を3の倍数にしたいとします。そのためには、$A$ が6の倍数でなければなりません。このとき、式を合成数にするために狙う素数は3ですが、分子を分類するために実際に使う法は6です。

この部のまとめ

合同式とは、無数の整数を有限個の余りの部屋へ整理する道具です。本記事では、合同式を用いて、どの許される余りでも少なくとも一つの式を小素数の倍数にする包囲網を作ります。

第1部　集合の基礎

この部では、「取り得る余り」をまとめて扱うために必要な集合の記号を説明します。集合論を本格的に学ぶことが目的ではありません。

1.1　集合と要素

たとえば、$A=\{1,4\}$ は1と4を集めた集合です。1が $A$ の要素であることを $1\in A$、2が $A$ の要素でないことを $2\notin A$ と書きます。

1.2　集合では順番と重複を区別しない

集合では要素を並べる順番に意味はなく、同じ要素を何度書いても一つと数えます。したがって、
$$ \{1,4\}=\{4,1\},\qquad \{1,1,4\}=\{1,4\} $$
です。

1.3　集合の要素数

有限集合 $A$ に含まれる要素の個数を $|A|$ と表します。たとえば、$A=\{1,4\}$ なら $|A|=2$ です。数 $x$ に対する $|x|$ は絶対値ですが、集合 $A$ に対する $|A|$ は要素数です。

1.4　包含関係

たとえば、$\{1,4\}\subseteq\{0,1,2,3,4\}$ です。一方、$A\not\subseteq B$ は、$A$ の要素の中に $B$ に含まれないものが少なくとも一つあることを表します。
$A\subseteq B$ かつ $B\subseteq A$ なら、二つの集合は同じ要素を持つので $A=B$ です。

1.5　集合の差

たとえば、$A=\{0,1,2,3,4\}$、$B=\{1,4\}$ なら、$A\setminus B=\{0,2,3\}$ です。後に、一つの法で処理できなかった余りだけを残すときに使います。

1.6　共通部分

たとえば、$A=\{0,1,4\}$、$B=\{1,2,4\}$ なら、$A\cap B=\{1,4\}$ です。後に、ある法で実際に処理できた余りを表すときに使います。

1.7　本記事で集合を使う理由

ある数 $X$ が法5で1または4にしかならないとき、その余りをまとめて、
$$ R_5=\{1,4\} $$
と表せます。また、複数の式が5の倍数になるために必要な $X$ の余りが1または4なら、
$$ D_5=\{1,4\} $$
と表せます。このとき $R_5=D_5$ なので、$X$ がどちらの余りでも、必ずどれかの式が5の倍数になります。集合は、余りの部屋を漏れなく比較するための記法です。

第2部　最初の具体例

法3では、整数 $p$ の余りは $0,1,-1$ の三つです。また、
$$ p+8\equiv p-1\pmod3,\qquad4p+1\equiv p+1\pmod3 $$
なので、三つの式の役割は次の表のようになります。

どの余りの場合にも、少なくとも一つの式が3の倍数です。三式はいずれも素数なので、3の倍数になる式は3そのものでなければなりません。
正の素数 $p$ に対して $p+8=3$ と $4p+1=3$ は不可能なので、$p=3$ だけが候補です。実際、$3,11,13$ はいずれも素数です。よって、
$$ \boxed{p=3} $$
です。

単に「式が3本だから法3」なのではありません。入れる三つの部屋を、三つの式が一つずつ担当していることが本質です。

第3部　すべての核となる包囲原理

3.1　可動部分

素数であるべき複数の式に共通して現れ、変数によって値が変わる部分を $X$ とします。本記事では、この $X$ を可動部分と呼びます。
たとえば、$p^2+4,p^2+6$ なら $X=p^2$、$2^n+1,2^n+19$ なら $X=2^n$ とするのが自然です。

3.2　狙う素数と作業する法

どれかの式を小さな素数 $q$ の倍数にしたいとき、この $q$ を狙う素数と呼びます。余りを実際に分類する法を $M$ と書き、作業する法と呼びます。通常は $M=q$ ですが、分母がある場合には $M=dq$ などとなることがあります。

3.3　到達集合

たとえば、$X$ が自由な整数なら $R_5=\{0,1,2,3,4\}$ です。一方、$X=x^2$ で $x$ が5の倍数でないなら $R_5=\{1,4\}$ です。同じ法5でも、可動部分の形や条件によって、実際に入れる部屋は変わります。

3.4　担当集合

たとえば、$X+1,X+19$ を法5で考えます。$X+1$ が5の倍数になるのは $X\equiv-1\pmod5$、$X+19\equiv X-1$ が5の倍数になるのは $X\equiv1\pmod5$ のときです。したがって、
$$ D_5=\{-1,1\} $$
です。

3.5　完全包囲の条件

3.6　要素数による事前判定

$R_M\subseteq D_M$ なら、当然 $|R_M|\leqq|D_M|$ です。したがって、
$$ |R_M|>|D_M| $$
なら、その法だけでは完全包囲できません。

3.7　式数と担当部屋数は違う

式が3本あっても、二つの式が同じ余りを担当することがあります。三式が法5で $X\equiv1,1,4$ のときに5の倍数になるなら、$D_5=\{1,4\}$ であり、$|D_5|=2$ です。

3.8　部分包囲

完全包囲に失敗しても、その法が無意味とは限りません。処理できた余りは $R_M\cap D_M$、処理できなかった余りは $R_M\setminus D_M$ です。残った余りを偶奇や合同条件へ翻訳し、その条件の下で可動部分を作り直します。

3.9　小素数そのものになる例外

ある式が素数 $q$ の倍数でも、その式が $q$ そのものなら素数です。したがって、包囲が完成した後には、「どの式が $q$ の倍数になるか」「その式が $q$ そのものになり得るか」「得られた候補が元の全条件を満たすか」を確認します。

3.10　係数が異なる一次式

$q\mid a$ の場合には $aX+b\equiv b\pmod q$ なので、$q\mid b$ ならすべての部屋を担当し、$q\nmid b$ ならどの部屋も担当しません。

第4部　前処理と一文字化

包囲原理を適用する前に、問題をできるだけ単純な形へ整えます。

4.1　素数条件をすべて書き出す

「素数 $p$ について」と書かれているなら、$p$ 自身も素数条件です。たとえば、素数 $p$ について $(p+1)/2$ と $(p+11)/2$ がともに素数であるという問題には、
$$ p,\qquad\frac{p+1}{2},\qquad\frac{p+11}{2} $$
という三つの素数条件があります。

4.2　整数性・正負・大小

分数の形をした式が素数なら、その値は2以上の整数です。したがって、分子が分母で割り切れるか、式が0・1・負の数にならないか、分母が0にならないか、小素数 $q$ より明らかに大きいかを先に確認します。

4.3　偶奇

2は唯一の偶数の素数です。したがって、素数であるべき式が偶数なら、その式は2でなければなりません。たとえば、素数 $p,q$ について $p+q$ も素数なら、$p,q$ の少なくとも一方は2です。両方が奇素数なら、$p+q$ は2より大きい偶数になるからです。

4.4　一文字化

$p+q$ が素数なので、$p,q$ の一方は2です。もし $p=2$ なら、$p+2q=2(q+1)$ は2より大きい偶数になるため不適です。したがって $q=2$ であり、問題は $p,p+2,p+4$ がいずれも素数となる $p$ を求める一文字の問題へ変わります。

4.5　可動部分は変数そのものとは限らない

現在の条件が変わったなら、可動部分も作り直して構いません。

第5部　自由な整数・一次式型

5.1　自由な整数の到達集合

可動部分 $X$ が自由な整数なら、素数 $q$ を法として、
$$ R_q=\{0,1,\ldots,q-1\},\qquad |R_q|=q $$
です。一方、$q\nmid a$ である一次式 $aX+b$ は一つの余りだけを担当します。そのような式が $k$ 本なら $|D_q|\leqq k$ です。

したがって、式が3本なら法2と法3、式が5本なら法2・法3・法5が候補です。ただし、式数は候補を絞るだけであり、担当の重複や集合の中身を必ず確認します。

5.2　「3式なら法3」の正体

三つの一次式で法3の三部屋を一つずつ担当できれば、$R_3=D_3$ となります。これが「三つの式がすべて素数なら法3を考える」という定石の正体です。
式が3本あることは法3を試す理由にはなりますが、成功を保証しません。三式の担当が重複していれば、三部屋を覆えないからです。

5.3　係数のカモフラージュ

法3では $4\equiv1$、$5\equiv-1$、$8\equiv-1$ です。したがって、$4p+1$ は法3では $p+1$ と同じ役割を持ちます。問題文で係数が大きく見えても、法の世界では $X-1,X,X+1$ のような単純な並びになることがあります。

5.4　5式と法5

可動部分は $X=p$ です。法5で定数項を整理すると $0,2,1,3,4$ となるため、各余りに対して次の式が5の倍数になります。

よって $R_5=D_5=\{0,1,2,3,4\}$ です。$p=5$ なら $5,7,11,13,19$ はすべて素数です。$p+2=5$ から得られる $p=3$ では $p+6=9$ となり、他の式が5になる場合には正の素数 $p$ を得ません。したがって、
$$ \boxed{p=5} $$
です。

第6部　素数などの特殊条件

6.1　素数の0の部屋

可動部分 $p$ と法 $q$ がともに素数なら、$p\equiv0\pmod q$ となるのは $p=q$ の場合だけです。したがって、まず $p=q$ を別に確認し、$p\ne q$ では0でない余りだけを考えます。

6.2　奇数という条件

可動部分 $X$ が奇数なら、法4で取り得る余りは1と3です。したがって、$R_4=\{1,3\}$ です。自由な整数なら4種類あった余りが、奇数という条件によって2種類へ減ります。

6.3　既に合同条件がある場合

前の段階で $n$ が偶数と分かったなら、法4では $n\equiv0,2\pmod4$ だけを考えます。また、$p\equiv1,4\pmod5$ まで絞れたなら、次の段階でもその条件を保存します。

第7部　平方剰余・立方剰余・一般の累乗剰余

7.1　平方剰余

小さい法で平方数が取り得る余りは次の通りです。

7.2　奇素数における平方剰余の個数

7.3　式数から平方型の候補法を絞る

平方部分 $X=x^2$ を含む一次式 $a_iX+b_i$ が $k$ 本あり、各係数 $a_i$ は素数 $q$ の倍数でないとします。一つの式は一つの $X$ の余りを担当するので、完全包囲には次が必要です。

これは必要条件です。実際に定数項が平方剰余を覆うかは、集合の中身を調べなければ分かりません。

7.4　平方型の例

まず $p=5$ なら、$5,29,31$ はすべて素数です。次に $p\ne5$ とし、可動部分を $X=p^2$ とします。$p$ は5の倍数でないので、
$$ R_5=\{1,4\}. $$
$X+4$ は $X\equiv1\pmod5$ を担当し、$X+6\equiv X+1$ は $X\equiv4\pmod5$ を担当します。したがって、$D_5=\{1,4\}=R_5$ です。
$p\ne5$ では、二式のどちらかが5より大きい5の倍数となるため不適です。よって、
$$ \boxed{p=5} $$
です。法5が候補になったのは、非零平方剰余が $(5-1)/2=2$ 種類であり、平方を含む有効な式も2本だったからです。

7.5　立方剰余

平方数と異なり、立方すると必ず余りの種類が減るわけではありません。法5では、
$$ 0^3\equiv0,\quad1^3\equiv1,\quad2^3\equiv3,\quad3^3\equiv2,\quad4^3\equiv4\pmod5 $$
なので、すべての余りが現れます。
一方、7の倍数でない $x$ に対して、フェルマーの小定理より $x^6\equiv1\pmod7$ です。したがって、
$$ (x^3)^2\equiv1\pmod7, $$
$$ (x^3-1)(x^3+1)\equiv0\pmod7. $$
零積の性質より、$x^3\equiv1$ または $x^3\equiv-1\pmod7$ です。よって、法7における立方数の余りは $\{0,1,-1\}$、非零立方剰余は $\{1,-1\}$ です。
参考として、直接計算すると法9では $\{0,1,-1\}$、法13では $\{0,1,5,8,12\}$ が立方数の余りです。

7.6　立方型の例

まず $p=7$ なら、$7^3+6=349$、$7^3+36=379$ です。$\sqrt{379}<20$ であり、349と379は20以下の素数 $2,3,5,7,11,13,17,19$ のいずれでも割り切れないため、どちらも素数です。
次に $p\ne7$ とします。$p=2$ なら $p^3+6=14$ なので不適です。したがって $p$ は7の倍数でない奇素数です。可動部分を $X=p^3$ とすると、$R_7=\{1,-1\}$ です。
$X+6$ は $X\equiv1\pmod7$ を担当し、$X+36\equiv X+1$ は $X\equiv-1\pmod7$ を担当します。したがって $D_7=\{1,-1\}=R_7$ です。$p\ne7$ ではどちらかが7より大きい7の倍数になるので、
$$ \boxed{p=7} $$
です。

7.7　多項式の解の個数

一般の累乗剰余を扱うため、先に多項式について一つ準備します。

7.8　フェルマーの小定理による圧縮

可動部分を $X=x^r$ とし、素数 $q$ は $x$ を割らないとします。ある正の整数 $d$ について $q-1\mid rd$ なら、
$$ X^d=x^{rd}\equiv1\pmod q. $$
したがって、$X$ は $Y^d\equiv1\pmod q$ の解に限られます。前節の定理より、その解は高々 $d$ 個です。

平方数について法5では $5-1\mid2\cdot2$ なので、非零平方剰余は高々2種類です。立方数について法7では $7-1\mid3\cdot2$ なので、非零立方剰余は高々2種類です。

7.9　累乗しても種類が減らない場合

たとえば、3と $5-1=4$ は互いに素なので、法5ではすべての非零の余りが立方数として現れます。

7.10　一般の累乗剰余の候補法

$X=x^r$ を含む有効な一次式が $k$ 本あるとします。非零の到達可能な余りを $k$ 種類以下へ圧縮したいなら、
$$ q-1\mid rd,\qquad1\leqq d\leqq k $$
となる候補を探せます。$d=1,2,\ldots,k$ と動かし、$rd$ の正の約数に1を加えて素数となるものを候補にし、最後に具体的な累乗剰余と担当集合を確認します。

この部のまとめ

平方・立方・一般の累乗型では、累乗によって到達集合が何種類へ減るかを調べます。候補法を種類数から絞った後も、最後には具体的な余りの中身と担当集合を比較します。

第8部　因数分解と指数型

この部では、可動部分が $X=B^m$ の形になる問題を扱います。底 $B$ は固定され、指数 $m$ が動きます。指数型では、余りの周期が短くなる法を式の本数から逆算して作ります。

8.1　合同式より先に因数分解を見る

正の整数 $m$ に対して、
$$ x^m-1=(x-1)(x^{m-1}+x^{m-2}+\cdots+x+1) $$
です。また、$m$ が奇数なら、
$$ x^m+1=(x+1)(x^{m-1}-x^{m-2}+\cdots-x+1) $$
です。したがって、指数型では合同式へ入る前に、指数の偶奇によって因数分解できないかを確認します。

8.2　指数を2で割れるだけ割る

任意の正の整数 $n$ は、
$$ n=2^s m $$
と書けます。ただし、$s$ は0以上の整数、$m$ は奇数です。これは、$n$ が偶数である間は2で割る操作を繰り返し、最後に残った奇数を $m$ とすれば得られます。たとえば、$12=2^2\cdot3$、$40=2^3\cdot5$、$64=2^6\cdot1$ です。

これは必要条件であって十分条件ではありません。$n$ が2の累乗でも、$a^n+1$ が必ず素数になるわけではありません。

8.3　指数型と累乗剰余型の違い

第7部では $X=x^r$ とし、指数 $r$ を固定して底 $x$ を動かしました。この部では $X=B^m$ とし、底 $B$ を固定して指数 $m$ を動かします。平方剰余では $x$ を動かしたときの $x^2$ の余りを調べ、指数型では $m$ を動かしたときの $B^m$ の周期を調べます。

8.4　周期と到達集合

素数 $q$ が底 $B$ を割らないとします。フェルマーの小定理により $B^{q-1}\equiv1\pmod q$ なので、$B^t\equiv1\pmod q$ となる正の整数 $t$ は存在します。その中で最小のものを $t$ とします。

8.5　式数から候補法を生成する

可動部分 $X=B^m$ を含む一次式 $a_iX+b_i$ が $k$ 本あり、各係数 $a_i$ は素数 $q$ の倍数でないとします。また、$q\nmid B$ とします。一つの式は高々一つの余りを担当するので、完全包囲には $|R_q|\leqq k$ が必要です。
最小周期を $t$ とすれば $t\leqq k$ であり、$B^t\equiv1\pmod q$ なので $q\mid B^t-1$ です。

したがって、
$$ B^1-1,\quad B^2-1,\quad\ldots,\quad B^k-1 $$
を因数分解すれば、候補となる素数法を有限個に絞れます。

小さい周期を作る候補は、次の因数分解から見つけられます。

これは、
$$ \begin{aligned} B^2-1&=(B-1)(B+1),\\ B^3-1&=(B-1)(B^2+B+1),\\ B^4-1&=(B-1)(B+1)(B^2+1) \end{aligned} $$
によります。ただし、$q\mid B^t-1$ でも最小周期が本当に $t$ とは限りません。候補を作った後に、実際の余りを確認します。

8.6　中心例

第1段階

可動部分を $X=2^n$ とします。式は2本なので、周期が2以下となる法を、
$$ 2^1-1=1,\qquad2^2-1=3 $$
から探します。底を割る素数2では、二式はどちらも奇数となり、2の倍数になりません。したがって、非自明な候補は法3です。
法3では $2\equiv-1$ なので、$2^n\equiv(-1)^n\pmod3$ です。よって、
$$ R_3=\{1,-1\}. $$
$X+1$ と $X+19\equiv X+1$ は、どちらも $X\equiv-1\pmod3$ の部屋を担当します。したがって、
$$ D_3=\{-1\}. $$
完全包囲には失敗しますが、奇数 $n$ は処理できます。$n=1$ では $2^n+19=21$ となり不適です。奇数 $n>1$ では、二式はともに3より大きい3の倍数です。したがって、残るのは $n$ が偶数の場合です。

第2段階

$n=2m$ とおくと $2^n=4^m$ です。可動部分を $X=4^m$ へ作り直します。式は依然として2本なので、
$$ 4^1-1=3,\qquad4^2-1=15 $$
から法3と法5が候補になります。
法3では $4^m\equiv1$ となり、どちらの式も3の倍数になりません。法5では $4\equiv-1$ なので、$R_5=\{1,-1\}$ です。また、$X+1$ は $X\equiv-1$、$X+19\equiv X-1$ は $X\equiv1$ を担当します。よって、
$$ D_5=\{1,-1\}=R_5. $$
$m$ が奇数なら $4^m+1$ が5の倍数です。これが素数なら $4^m+1=5$ なので $m=1$、$n=2$ です。$m$ が偶数なら $4^m+19$ が5の倍数であり、$m\geqq2$ なので5より大きくなります。
$n=2$ のとき、$2^2+1=5$、$2^2+19=23$ であり、条件を満たします。したがって、
$$ \boxed{n=2} $$
です。

8.7　なぜ指数を法4で分けるのか

第2段階では $4^m\equiv(-1)^m\pmod5$ なので、必要なのは $m$ の偶奇だけです。$n=2m$ だから、
$$ \begin{aligned} m\text{ が奇数}&\Longleftrightarrow n\equiv2\pmod4,\\ m\text{ が偶数}&\Longleftrightarrow n\equiv0\pmod4. \end{aligned} $$
つまり、法5を選んだ結果、必要な指数分類として法4が現れました。最初から理由なく $n$ を法4で分けたのではありません。法8まで細かく分けても、法5における $2^n$ の余りは増えません。

8.8　指数の一つの部屋を処理する方法

指数 $m$ が $m\equiv r\pmod T$ を満たすとします。$0\leqq r< T$ とすれば、$m=Tk+r$ と書けるので、
$$ B^m+c=(B^T)^kB^r+c. $$

実際、$B^T\equiv1\pmod q$ なので、$B^m+c\equiv B^r+c\equiv0\pmod q$ です。指数の分類が既に見えている場合には、$B^T-1$ と $B^r+c$ の共通の素因数を調べることで、その部屋を処理する法を作れます。

8.9　因数分解と周期は同じ構造を見る

$m$ が奇数なら $B^m+1$ は $B+1$ で割り切れます。一方、素数 $q$ が $B+1$ を割るなら $B\equiv-1\pmod q$ なので、$B^m\equiv-1\pmod q$ です。
因数分解は約数を直接取り出す見方、周期は余りの繰り返しとして見る見方です。二つは別の偶然ではなく、同じ構造を異なる方向から見ています。

第9部　分数の形をした式

9.1　まず整数性を確認する

$A/d$ が素数なら、この値は整数です。したがって、$A$ は $d$ の倍数でなければなりません。さらに、この商を素数 $q$ の倍数にしたいなら、$A/d=qk$ と書けるので $A=dqk$ です。

9.2　狙う素数と作業する法

$A/2$ を3の倍数にしたいなら、分子 $A$ を6の倍数にします。したがって、狙う素数は3、作業する法は6です。分数型で法6や法10が現れるのは、合成数を法として狙うからではなく、分母を掛け戻した結果です。

9.3　基本例

$p$ 自身も素数条件です。狙う素数を3とし、分母2を掛け戻して法6で考えます。
まず $p=3$ なら、$(p+1)/2=2$、$(p+11)/2=7$ であり、条件を満たします。次に $p\ne3$ とします。$p$ は奇素数で3の倍数でもないので、
$$ R_6=\{1,5\}. $$
$p+11$ が6の倍数になるのは $p\equiv1\pmod6$、$p+1$ が6の倍数になるのは $p\equiv5\pmod6$ のときです。したがって、$D_6=\{1,5\}=R_6$ です。
$p=5$ では $(p+1)/2=3$ ですが、もう一方は8となるため不適です。$p>5$ では、どちらかの商が3より大きい3の倍数になります。よって、
$$ \boxed{p=3} $$
です。

9.4　分母が複数ある場合

複数の式
$$ \frac{A_1(X)}{d_1},\qquad\frac{A_2(X)}{d_2},\qquad\ldots $$
を同じ素数 $q$ の倍数にしたいとします。第 $i$ 式については、$A_i(X)$ が $d_iq$ の倍数となる条件を調べます。一つの表で扱うなら、$d_1q,d_2q,\ldots$ の最小公倍数を作業する法にできます。ただし、作業する法が大きくなるほど余りの部屋も増えるため、現在の条件で実際に到達できる部屋だけを調べます。

9.5　合成数を作業する法にするときの注意

法6や法10は合成数です。したがって、「積が法の倍数なら、どちらかの因数も法の倍数である」という性質を使ってはいけません。分数型では、分子が $dq$ の倍数であることを確認し、そこから商が素数 $q$ の倍数であると結論します。

第10部　一つの法では終わらない場合

10.1　部分包囲

法 $M$ において $R_M\not\subseteq D_M$ でも、$R_M\cap D_M$ に含まれる余りは処理できます。残るのは $R_M\setminus D_M$ です。
たとえば、$R_3=\{1,-1\}$、$D_3=\{-1\}$ なら、残るのは $\{1\}$ です。可動部分が $2^n$ なら、$2^n\equiv1\pmod3$ から $n$ が偶数だと分かります。

10.2　残った集合を条件へ翻訳する

部分包囲の後は、残った余りを指数の偶奇、特定の合同条件、変数がある数の倍数であることなどへ翻訳します。その条件の下で、$n=2m$、$p=5m+1$ などと置き直し、可動部分を再定義します。
たとえば、$n=2m$ なら $2^n=4^m$ なので、可動部分を $2^n$ から $4^m$ へ作り直せます。

10.3　同じ核を繰り返す

10.4　「法3の次に法5」では説明にならない

「まず法3、次に法5」とだけ書くと、なぜその二つを使うのかが見えません。第8部の例では、2本の式で $2^n$ の余りを覆うため周期が2以下となる法を生成すると法3が現れ、法3で奇数指数を処理した結果、偶数指数が残りました。そこで $n=2m$ として $4^m$ へ作り直し、再び周期が2以下となる法を生成すると法5が現れました。
後の法は、前の段階で残った構造から生まれています。

第11部　余分な式とカモフラージュ

11.1　式数が到達部屋数より多い場合

到達集合が2部屋しかないのに、素数条件が3本以上あることがあります。余った式は、他の式と同じ部屋を担当する、小素数そのものになる候補を排除する、最後に残った候補を排除する、解の確認にだけ使われる、本当の構造を見えにくくする、といった役割を持ちます。

11.2　論理的に不要な式

実は、$2^n+1$ と $2^n+19$ の二式だけで $n=2$ と決まります。$n=2$ のとき $2^n+3=7$ も素数なので、$2^n+3$ は解を決定するためには不要で、最終確認にだけ使われています。

11.3　解答後の吟味

問題を解き終えたら、各式が完全包囲に必要だったか、他の式と担当が重複したか、小素数そのものになる例外を除いたか、最終確認だけに使われたか、全く不要だったかを確認します。これは、解答者の視点から作問者の視点へ進むためにも重要です。

第12部　ここまでの解法は、すべて同じである

12.1　唯一の核

12.2　各論の正体

各論は別々の裏技ではありません。$R_M$ を速く求め、小さくするための定石です。記事に載っていない形でも、可動部分を見つけ、到達集合と担当集合を比較できれば、同じ考え方を適用できます。

第13部　構造が見えない場合の実験

13.1　実験の位置づけ

一文字化、可動部分、式数、平方・立方剰余、指数の周期、分母の掛け戻し、因数分解を調べても候補法が見えない場合には、実験して推測するしかありません。ただし、値を無秩序に代入して答えを当てるのではありません。実験でも探すものは $R_M$ と $D_M$ です。

13.2　実験表

13.3　実験する法を先に絞る

自由な一次式が $k$ 本なら通常は素数 $q\leqq k$、平方型なら平方剰余の種類数が $k$ 以下となる法、指数型なら $B^t-1\ (1\leqq t\leqq k)$ の素因数、分数型なら狙う素数に分母を掛け戻した法へ候補を絞れます。
指数型で巨大な値を直接計算する必要はありません。候補法 $q$ に対して $B,B^2,B^3,\ldots\pmod q$ を順に計算し、1へ戻った時点で周期を確定します。

13.4　部分成功を保存する

法3で奇数指数だけを処理できたなら、「$n$ は偶数」という条件を保存します。次の実験では偶数だけを調べ、最初からすべてをやり直しません。

13.5　実験を証明へ戻す

実験から「$n\equiv2\pmod4$ のとき、$2^n+1$ は5の倍数らしい」と分かったとします。$n=4k+2$ とおけば、
$$ 2^n+1=4\cdot16^k+1. $$
法5で $16\equiv1$ なので、$2^n+1\equiv4+1\equiv0\pmod5$ です。さらに、$2^n+1=4^{2k+1}+1$ と見れば、奇数乗の和の因数分解から5が現れたことも分かります。

13.6　実験の停止条件

$|R_M|>|D_M|$ である、自由な一次式型で候補の素数が式数より大きい、指数型で最小周期が有効な式数より大きい、といった場合には、その法で完全包囲を目指す実験を打ち切れます。ただし、完全包囲できなくても、有用な部分包囲になる可能性は残ります。

第14部　完全攻略フローチャート

14.1　前処理

STEP 1　素数条件をすべて書き出す

変数自身が素数である条件も含めます。

STEP 2　整数性・正負・偶奇・大小を見る

分数が整数になる条件、偶数の素数2、小素数そのものになる可能性を確認します。

STEP 3　できるだけ一文字化する

複数の文字を、偶奇や条件式によって減らします。

14.2　核となる分析

STEP 4　可動部分 $X$ を抜き出す

式を $a_iX+b_i$ または $(a_iX+b_i)/d_i$ の形へ整理します。

STEP 5　現在の条件を明示する

$X$ は自由な整数か、0になり得るか、素数・奇数・平方数・累乗数か、指数に条件があるか、前段階で余りが絞られているかを確認します。

STEP 6　型から候補法を作る

ここで $k$ は、各式が高々一つの余りを担当する有効な一次式の本数です。

14.3　候補法の検査

STEP 7　到達集合 $R_M$ を求める

可動部分が実際に取り得る余りを、漏れなく求めます。

STEP 8　担当集合 $D_M$ を求める

各式が狙う素数の倍数になる余りを求め、重複を除きます。

STEP 9　完全包囲か部分包囲かを判定する

$R_M\subseteq D_M$ なら完全包囲です。完全包囲できなくても、$R_M\setminus D_M$ を新しい条件へ翻訳し、STEP 4へ戻ります。

14.4　例外と最終確認

STEP 10　小素数そのものになる場合を調べる

式が狙う素数 $q$ の倍数でも、「式 $=q$」なら素数です。その方程式を解きます。

STEP 11　元のすべての条件へ戻る

途中で使わなかった式も含め、候補を検算します。

第15部　総合問題

ここからは、どの型を使うかを問題名では明かしません。講義中の例題の単なる再掲ではなく、同じ原理を別の形で使う問題を並べました。

第16部　総合問題の解答・解説

問題1の解答

可動部分を $X=p$ とします。法3では、
$$ p+4\equiv p+1,\qquad2p+1\equiv-p+1\pmod3. $$

したがって、$R_3=D_3=\{0,1,-1\}$ です。$p+4=3$ から正の素数 $p$ は得られず、$2p+1=3$ からは $p=1$ となります。よって $p=3$ だけが候補です。
$p=3$ のとき三式の値は $3,7,7$ で、いずれも素数です。式の値が重複しても、各値が素数なら条件を満たします。したがって、
$$ \boxed{p=3} $$
です。

問題2の解答

可動部分を $X=p$ とします。法5で五式の定数項を見ると $0,2,1,3,4$ となり、五つの余りがすべて一度ずつ現れます。したがって、$R_5=D_5=\{0,1,2,3,4\}$ です。
$p=5$ のとき、$5,7,11,13,29$ はすべて素数です。$p+2=5$ から得られる $p=3$ では $p+6=9$ となります。他の式が5になる場合には正の素数 $p$ を得ません。よって、
$$ \boxed{p=5} $$
です。

問題3の解答

$p+q$ が素数なので、$p,q$ の少なくとも一方は2です。もし $q=2$ なら、$2p+q=2(p+1)$ は2より大きい偶数なので不適です。したがって $p=2$ です。
問題は $q,q+2,q+4$ がいずれも素数となる $q$ を求める問題へ変わります。法3では三式が三部屋を一つずつ担当するため、どれかが3の倍数です。$q+2=3$ と $q+4=3$ から正の素数 $q$ は得られないので、$q=3$ です。
実際、$(p,q)=(2,3)$ のとき $2,3,5,7$ はすべて素数です。よって、
$$ \boxed{(p,q)=(2,3)} $$
です。

問題4の解答

まず $p=7$ のとき、$p^2+10=59$、$p^2+12=61$、$p^2+34=83$ であり、すべて素数です。
次に $p\ne7$ とし、可動部分を $X=p^2$ とします。法7における非零平方剰余より、$R_7=\{1,2,4\}$ です。また、
$$ X+34\equiv X-1,\qquad X+12\equiv X-2,\qquad X+10\equiv X+3\pmod7. $$
三式はそれぞれ $X\equiv1,2,4\pmod7$ を担当するので、$D_7=\{1,2,4\}=R_7$ です。$p\ne7$ では三式のどれかが7より大きい7の倍数になります。したがって、
$$ \boxed{p=7} $$
です。

問題5の解答

まず $p=7$ のとき、$p^3+76=419$、$p^3+78=421$ です。$\sqrt{421}<21$ であり、419と421は21以下の素数 $2,3,5,7,11,13,17,19$ のいずれでも割り切れないため、どちらも素数です。
次に $p\ne7$ とします。$p=2$ なら $p^3+76=84$ となるため不適です。したがって $p$ は7の倍数でない奇素数です。可動部分を $X=p^3$ とすると、$R_7=\{1,-1\}$ です。
$76\equiv-1$、$78\equiv1\pmod7$ なので、$X+76$ は $X\equiv1$、$X+78$ は $X\equiv-1$ を担当します。よって $D_7=\{1,-1\}=R_7$ です。$p\ne7$ ではどちらかが7より大きい7の倍数になります。したがって、
$$ \boxed{p=7} $$
です。

問題6の解答

可動部分を $X=4^n$ とします。法5では $4\equiv-1$ なので $R_5=\{1,-1\}$ です。$X+1$ は $X\equiv-1$、$X+9\equiv X-1$ は $X\equiv1$ を担当するので、$D_5=\{1,-1\}=R_5$ です。
$n$ が奇数なら $4^n+1$ が5の倍数です。これが素数なら $4^n+1=5$ なので $n=1$ です。$n$ が偶数なら $4^n+9$ が5の倍数であり、$n\geqq2$ なので5より大きくなります。
$n=1$ のとき $4^1+1=5$、$4^1+9=13$ です。よって、
$$ \boxed{n=1} $$
です。

問題7の解答

可動部分を $X=2^n$ とします。法3では $2^n\equiv(-1)^n$、$49\equiv1$ です。$n$ が奇数なら二式はともに3の倍数です。$n=1$ では $2^n+49=51$ となり、奇数 $n>1$ では3より大きい3の倍数が生じます。したがって $n$ は偶数です。
$n=2m$ とおき、可動部分を $X=4^m$ へ作り直します。法5では $4^m\equiv(-1)^m$、$49\equiv-1$ なので、$R_5=D_5=\{1,-1\}$ です。
$m$ が奇数なら $4^m+1$ が5の倍数です。これが素数なら $m=1$、$n=2$ です。$m$ が偶数なら $4^m+49$ が5より大きい5の倍数です。$n=2$ のとき $2^2+1=5$、$2^2+49=53$ なので、
$$ \boxed{n=2} $$
です。

問題8の解答

狙う素数を3とし、分母2を掛け戻して法6を使います。まず $p=3$ なら、$(p+7)/2=5$、$(p+23)/2=13$ であり、条件を満たします。
$p\ne3$ とします。$p$ は奇素数で3の倍数でないため、$R_6=\{1,5\}$ です。$p\equiv1\pmod6$ なら $p+23$ が6の倍数、$p\equiv5\pmod6$ なら $p+7$ が6の倍数です。よって $D_6=\{1,5\}=R_6$ です。
これらの商が3そのものになる方程式からは正の素数 $p$ を得ません。したがって、
$$ \boxed{p=3} $$
です。

問題9の解答

まず $p=3$ なら、$(p^2+13)/2=11$、$(p^2+17)/2=13$ であり、条件を満たします。
$p\ne3$ とします。$p$ は奇素数で3の倍数でないので、$p\equiv1,5\pmod6$ です。したがって $p^2\equiv1\pmod6$ であり、$p^2+17\equiv0\pmod6$ です。よって $(p^2+17)/2$ は3の倍数です。$p\geqq5$ なので、この値は3より大きく、合成数です。したがって、
$$ \boxed{p=3} $$
です。この問題では、$(p^2+13)/2$ は $p=3$ が実際に条件を満たすことを確認する役割を持ち、$p\ne3$ の排除には使われていません。

問題10の解答

$2^n+1$ と $2^n+49$ の二式だけで、問題7より $n=2$ と決まります。$n=2$ のとき $2^n+7=11$ も素数です。したがって、
$$ \boxed{n=2} $$
です。$2^n+7$ は解の決定には不要であり、最終確認にだけ使われています。

第17部　最後の問題とおわりに

ここまでの内容を組み合わせて解く、最後の問題を一題用意しました。特別な定理や、ここまでに扱っていない裏技は必要ありません。
整数性、因数分解、一文字化、可動部分、到達集合、担当集合、部分包囲、そして可動部分の作り直しを意識しながら、ぜひ自分の手で挑戦してみてください。

「いずれも素数」問題で本当に難しいのは、合同式の計算そのものではありません。何を可動部分と見るか、どの法なら可動部分の余りが少なくなるか、各式がどの余りを担当するかを見抜くことです。
初めは「三式なら法3」「五式なら法5」という定石から入っても構いません。しかし、その背後にある本当の原理は、
$$ \boxed{R_M\subseteq D_M} $$
です。
自由な一次式では小さい法を使い、素数条件では0の部屋を特別扱いし、平方・立方・一般の累乗では累乗剰余を使います。指数型では短い周期を作る法を $B^t-1$ から生成し、分数型では分母を掛け戻して作業する法を作ります。一つの法で終わらなければ、残った集合から可動部分を作り直します。
これらは別々の裏技ではありません。すべて、可動部分が入れる部屋を求め、各式の担当する部屋ですべて覆うという一つの考え方から生まれています。
初めから候補法を完全に見抜けない場合には実験して構いません。ただし、実験でも $R_M$ と $D_M$ を探し、発見した規則を合同式で証明し、最後にはなぜその法が現れたのかを式の構造へ戻って考えます。

この視点を身につければ、既知の典型問題を解くだけでなく、これまでに見たことのない形の問題にも対応できるようになります。本記事が、「なぜその法を考えるのか」を自分で考えるための一助となれば幸いです。
みなさまの日常に良き数学の彩りのあらんことを。
それでは、ごきげんよう。