mod p

完全攻略 ― 位数を中心に

更新日：2023-08-09

この記事の目的は，位数に関する議論を原始根を中心に整理し，様々なタイプの数学オリンピックの整数問題に対して応用することである．

理論

まずフェルマーの小定理を示し，オイラーの定理，カーマイケルの定理へと拡張する．次に，原始根を導入して基本的な取り扱いを述べ，いくつかの応用を見る． LTEの補題やジグモンディーの定理についても触れる．

本章を通して特に断りのない限り $p$ は素数を表す．

1. 多項式

定理 1（剰余の定理）. 整数係数多項式

f, g

は，最高次係数が

p

で割り切れないとする．このとき，以下をみたす整数係数多項式

q, r

が，係数を

mod p

で考えて一意に存在する：

f \equiv g q + r (\mod p), \deg r < \deg g

証明は通常の剰余の定理と同様に進行する．

証明. まず，存在するとして一意であることを示す．二つあったとする．すなわち，

f \equiv g q_{1} + r_{1} \equiv g q_{2} + r_{2} (\mod p)

とすると，

r_{1} - r_{2} \equiv g (q_{2} - q_{1}) (\mod p)

となる．いま，

q_{1} ≢ q_{2} (\mod p)

とすると

\deg (r_{1} - r_{2}) \geq \deg g

となり矛盾するから，

q_{1} \equiv q_{2} (\mod p)

．このとき

r_{1} \equiv r_{2} (\mod p)

も従う．

　存在することを示す． $g$ が定数の時は明らかなので， $\deg g \geq 1$ とする． $\deg f$ に関する帰納法で示す. $\deg f < \deg g$ のときは $q = 0, r = f$ とすればよい． $k \geq \deg (g (x)) - 1$ について， $\deg f \leq k$ において示されたとする. $\deg f = k + 1$ として， $f, g$ の最高次係数を $a, b$ とすると， $b c \equiv 1 (\mod p)$ なる整数 $c$ が存在する． $f_{1} (x) \equiv f (x) - a c g (x) x^{k + 1 - \deg g} (\mod p)$ とすると， $\deg f_{1} \leq k$ とできるので，帰納法の仮定により $f_{1} \equiv g q_{1} + r (\mod p)$ かつ $\deg r < \deg g$ なる整数係数多項式 $q_{1}, r$ が存在する． $f (x) \equiv f_{1} (x) + a c g (x) x^{k + 1 - \deg g} \equiv g (x) (a c x^{k + 1 - \deg g (x)} + q_{1} (x)) + r (x) (\mod p)$ により $\deg f = k + 1$ でも主張は正しく，定理は示された．

整数 $a$ に対して， $g (x)$ として $x - a$ をとると，以下の系が得られる：

定理 2.

f (a) \equiv 0 (\mod p)

であるとき，

f (x) \equiv (x - a) q (x) (\mod p)

なる整数係数多項式

q

が存在する．

さらに，この系を繰り返し用いれば次の系が得られる：

定理 3（因数定理）.

f

を整数係数多項式とし，整数

a_{1}, \dots, a_{n}

は

mod p

で相異なるとする．

f (a_{1}) \equiv \dots \equiv f (a_{n}) \equiv 0 (\mod p)

であるとき，ある整数係数多項式

g (x)

が存在して，

f (x) \equiv g (x) (x - a_{1}) \dots (x - a_{n}) (\mod p)

が成り立つ．

上の系から次の定理が導かれる：

定理 4.

n

を非負整数とし，

f (x)

を

mod p

で恒等的に

0

でない整数係数

n

次多項式とすると，

f (x) \equiv 0 (\mod p)

の

mod p

における解は高々

n

個である．

この記事では，特に $f (x) = x^{n} - 1$ としてこの定理を使うことがしばしばある．

2. フェルマーの小定理

ここではフェルマーの小定理とその証明，および簡単な応用について触れる．フェルマーの小定理は重要であるから，複数の証明を載せて多くの視点から理解していく．

定理 5（フェルマーの小定理）.

p

を素数とする．整数

a

が

p

で割り切れないとき，

a^{p - 1} \equiv 1 (\mod p)

．

証明 1. まず，二項展開することで

(a + b)^{p} \equiv a^{p} + b^{p} (\mod p)

の成立がわかる．特に

(a + 1)^{p} \equiv a^{p} + 1 (\mod p)

なので，

0^{p} \equiv 0 (\mod p)

とあわせて

a^{p} \equiv a (\mod p)

が得られる．

a

は

p

と互いに素であるから示された．

この証明からわかるように，次の系が得られる：

系 6.

p

を素数とする．任意の整数

a

に対して，

a^{p} \equiv a (\mod p)

．

この系では $a$ に条件がつかないため，状況しだいではもとのフェルマーの小定理より適することもある．

証明2の前に，一つの補題を述べる：

補題 7.

n

を正整数とし，

X

を「

1

以上

n

以下で

n

と互いに素な整数」全体からなる集合とする．整数

a

が

n

と互いに素であるとき，写像

f : X \to X

を

f (x) \equiv a x (\mod n)

によって定めると，

f

は全単射である．

補題の証明.

f

が単射であることを示せば十分である.

f (x) = f (y)

とすると

a x \equiv a y (\mod n)

となり，

a

と

n

が互いに素であることから

x \equiv y (\mod n)

，すなわち

x = y

が従う．

証明 2.

n = p

として補題を適用することで，

(p - 1)! \equiv \prod_{i = 1}^{p - 1} i \equiv \prod_{j = 1}^{p - 1} (a j) \equiv a^{p - 1} (p - 1)! (\mod p) .

(p - 1)!

と

p

は互いに素であるから，

a^{p - 1} \equiv 1 (\mod p)

．

証明3は少し入り組む．単にフェルマーの小定理を示すだけであれば上の二つのような方法をとれば十分だが，以降の議論のために紹介する．そのためには，しばらくの準備が必要である．

補題 8. 整数

a

が

p

と互いに素であるとき，ある正整数

n

が存在して

a^{n} \equiv 1 (\mod p)

となる．

補題の証明. 典型的な鳩の巣原理の適用例である．鳩の巣原理により，

a^{0}, \dots, a^{p}

の中には

p

で割った余りが等しい

2

数

a^{i}, a^{j} (i < j)

がある．このとき，

a^{j - i} \equiv 1 (\mod p)

となる．

この補題によって，次の定義が導入できる：

定義 1（位数）.

p

を素数とし，

a

を

p

と互いに素な整数とする．このとき，

a^{m} \equiv 1 (\mod p)

なる最小の正整数

m

を

a

の

mod p

での位数とよぶ．この記事では位数を

{ord}_{n} (a)

で表すこととする．

位数の基本性質の一つとして， $a^{n}$ の位数は $a$ の位数の約数である（証明を試みよ）．

証明 3. 明らかに，位数はつねに

p - 1

以下である．位数としてありうる最大値を

m

とし，

a

の位数が

m

であるとする．いま，

m = p - 1

であることを示したい．そのために，

m < p - 1

であると仮定して矛盾を導く．

　このとき，位数が $m$ の約数でない整数 $b$ が存在する．なぜならば，位数が $m$ の約数である整数 $c$ は $c^{m} - 1 \equiv 0 (\mod p)$ をみたし，定理4によりこれをみたす $c$ は $mod p$ で高々 $m (< p - 1)$ 個であるからである．このような $b$ のうち位数が最小であるものを $d$ とし，その位数を $n$ とすると，（ $n$ の最小性により）任意の $n$ の真の約数は $m$ の約数でもある．これにより， $n$ の素因数 $p$ を一つとると， $n$ は $m p$ の約数となる．ここで $n$ が $p$ 以外の素因数 $q$ をもつとすると， $n$ は $m q$ の約数でもあり，これは $n ∣ m$ を導くから矛盾．すなわち， $n = p^{e}$ と表せる．

　このとき， $a d$ の位数が $m p$ であることを示せば十分である（ $m$ の最大性に矛盾する）． $(a d)^{m p} \equiv 1 (\mod p)$ により $k ∣ m p$ であるが， $(a d)^{m} \equiv d^{m} ≢ 1 (\mod p)$ により $k ∤ m$ である．したがって， $p^{e} = n ∣ k$ が必要である． $d^{p^{e}} \equiv 1 (\mod p)$ により $1 \equiv (a d)^{k} \equiv a^{k} d^{k} \equiv a^{k} (\mod p)$ となるから， $m ∣ k$ ．よって， $k$ は $m$ と $n$ の公倍数であるから， $k = m p$ となる．

　さて，以上で $a$ の位数が $p - 1$ であることが示された．このとき， $p - 1$ 個の整数 $a^{0}, a^{1}, a^{2}, \dots, a^{p - 2}$ は $mod p$ で相異なるから，任意の $p$ と互いに素な整数 $b$ に対して $b \equiv a^{i} (\mod p)$ なる整数 $i$ が存在することになる．すると， $b^{p - 1} \equiv (a^{i})^{p - 1} \equiv (a^{p - 1})^{i} \equiv 1 (\mod p)$ となり，証明が完了する．

ここまでの議論によって，一つの重要な帰結が得られる．原始根は，この記事の一つの重要なテーマである．

定理 9（原始根の存在）. 素数

p

に対して，

mod p

には原始根が存在する．すなわち，ある整数

a

が存在して，任意の

p

で割り切れない整数

b

に対して，ある非負整数

n

が存在して

a^{n} \equiv b (\mod p)

となる．

最後の証明はちょっとしたオマケである．

証明 4.

a > 0

のとき示せばよい．円周上に等間隔に並んだ

p

個の点に，

1

以上

a

以下の整数を割り当てる方法の個数を考える．ここで，回転して一致するものを区別しないことにすると，すべての点に同じ数を割り当てるか否かで場合分けすればよく，求める場合の数は

\frac{a^{p} - a}{p} + a

である．よって，特に

a^{p} \equiv a (\mod p)

である．

なお，証明1・証明2の理解の助けとして，以下の系を述べておく．これは系3と系6から導かれる．

系 10.

x

についての多項式として，次が成り立つ：

x (x - 1) (x - 2) \dots (x - (p - 1)) \equiv x^{p} - x (\mod p)

さて，フェルマーの小定理の自明な応用例をいくつか見ておく．まず，以下は具体的な数をあてはめたのみにすぎないが，たとえば「 $4$ 乗数を見たら $mod 5$ を考えるとよいかもしれない」といった逆向きの目線は侮れない．

系 11. 整数

a

に対して，以下が成り立つ：

$a$ が $3$ で割り切れないとき， $a^{2} \equiv 1 (\mod 3)$ ．
$a$ が $5$ で割り切れないとき， $a^{4} \equiv 1 (\mod 5)$ ．
$a$ が $7$ で割り切れないとき， $a^{6} \equiv 1 (\mod 7)$ ．

また，一般に $a^{3} \equiv a (\mod 3)$ ， $a^{5} \equiv a (\mod 5)$ ， $a^{7} \equiv a (\mod 7)$ が成り立つ．

次も自明な言いかえにすぎないが，いわゆるモジュラ逆数を計算する具体的な方法を与えている点で重要である：

系 12. 整数

a

が

p

と互いに素であるとき，

a^{p - 2} \cdot a \equiv 1 (\mod p)

．すなわち，

a^{- 1} \equiv a^{p - 2} (\mod p)

．

最後に，非常に簡単な例題を一つ．

★☆☆☆☆

有名問題

$p$ を $7$ 以上の素数とする，十進法で $1$ が $p - 1$ 個連続した数 $1111 \dots 1$ は， $p$ の倍数であることを示せ．

解答

$p$ は $10$ および $9$ と互いに素であるから， $1111 \dots 1 = \sum_{k = 0}^{p - 2} 10^{k} = \frac{10^{p - 1} - 1}{10 - 1} \equiv 0 (\mod p) .$

3. カーマイケルの定理

素数に限らず，一般の正整数 $n$ を法としたフェルマーの小定理の拡張を考えたい．すなわち目標は，任意の $n$ と互いに素な整数 $a$ に対して $a^{m} \equiv 1 (\mod n)$ が成立するような，正の整数 $m$ を見つけることである．中国剰余定理をふまえて，まずは $n = p^{k}$ と表せる場合に絞って考える．

補題 13.

k

を正整数として，

p

を素数，

a

を

p

と互いに素な整数とすると，

a^{(p - 1) p^{k - 1}} \equiv 1 (\mod p^{k}), a^{2^{k}} \equiv 1 (\mod 2^{k + 2}) .

証明. 一つ目の式を示す．

S

を「

p^{k}

以下の

p

と互いに素な正整数」全体からなる集合とすると，補題7により

\prod_{i \in S} i \equiv \prod_{i \in S} (a i) \equiv a^{φ (p^{k})} \prod_{i \in S} i (\mod p^{k})

が成り立つ．

φ (p^{k}) = p^{k - 1} (p - 1)

により示された．二つ目の式を示すためには，以下に留意する：

a^{2^{k}} - 1 = (a^{2} - 1) (a^{2} + 1) \dots (a^{2^{k - 1}} + 1) = (a^{2} - 1) \prod_{i = 1}^{k - 1} (a^{2^{i}} + 1) .

a^{2^{i}} + 1

は偶数であり，

a^{2} - 1

は

8

の倍数である．よって，左辺は

2

で

3 + (k - 1) = k + 2

回以上割り切れる．

補題により，次のように関数 $λ (n)$ を定めれば， $a^{λ (n)} \equiv 1 (\mod n)$ が従う：

定義 2（カーマイケル関数）. 以下で定義される

λ : Z_{> 0} \to Z_{> 0}

を，カーマイケル関数とよぶ：

λ (1) = λ (2) = 1, λ (4) = 2, λ (2^{k + 2}) = 2^{k}, λ (p^{k}) = (p - 1) p^{k - 1}, λ (n) = lcm (λ (p_{1}^{e_{1}}), λ (p_{2}^{e_{2}}), . . ., λ (p_{N}^{e_{N}}))

ただし，上では

p

は奇素数とし，

n = \prod {p_{i}}^{e_{i}}

と素因数分解されているとする．

定理 14（カーマイケルの定理）.

n

を正整数とする．整数

a

が

n

と互いに素であるとき，

a^{λ (n)} \equiv 1 (\mod n)

．

$λ (n) ∣ φ (n)$ であるから，次の定理も成立する：

定理 15（オイラーの定理）.

n

を正整数とする．整数

a

が

n

と互いに素であるとき，

a^{φ (n)} \equiv 1 (\mod n)

．

なお，オイラーの定理を示すだけであれば，補題13と同様に補題7を用いるだけである．各自で試みよ．

カーマイケル関数 $λ (n)$ は，実は $a$ が $n$ と互いに素なときつねに $a^{m} \equiv 1 (\mod n)$ となる最小の $m$ を与えているので，その意味でカーマイケルの定理は最良の結果である．すなわち，オイラーの定理は必ずしも最良の結果を与えないが，オイラーの定理の方が使い勝手はよいので，ケースバイケースであることに留意しよう．

具体的計算への応用として， $13^{1341}$ の下二桁を求めてみよう．これは $100$ で割った余りを求めるということである． $φ (100) = 40$ なのでオイラーの定理により $13^{1341} \equiv (13^{40})^{33} 13^{21} \equiv 13^{21} (\mod 100)$ となるが，まだ計算が大変である．いま $λ (100) = 20$ であるから，カーマイケルの定理を使えれば $13^{1341} \equiv 13^{1} \equiv 13 (\mod 100)$ となり，下二桁が求められた．

4. 原始根

以下の定理はすでに示したが，別証を与える（少し難しいので，飛ばしてよい）．

定理 9（原始根の存在）. 素数

p

に対して，

mod p

には原始根が存在する．すなわち，ある整数

a

が存在して，任意の

p

で割り切れない整数

b

に対して，ある非負整数

n

が存在して

a^{n} \equiv b (\mod p)

となる．

証明. まず，一般に

a^{n} \equiv 1 (\mod p) ⟺ {ord}_{p} (a) ∣ n

が成立することに注意する．特に，フェルマーの小定理により

{ord}_{p} (a) ∣ p - 1

が成立する.

　いま， $d ∣ p - 1$ であるとき， $x^{d} - 1 \equiv 0 (\mod p)$ の解の個数は定理4により $d$ 個以下である．ここで，解の個数が $d$ 個未満であったとすると， $p - 1 - d$ 次多項式 $\frac{x^{p - 1} - 1}{x^{d} - 1}$ が $p - 1 - d$ 個より多くの根をもつことになり，定理4に反する．よって， $x^{d} - 1 \equiv 0 (\mod p)$ の解の個数はちょうど $d$ 個である.

　これにより，位数が $d$ であるものが $mod p$ で $f (d)$ 個存在するとすると， $\sum_{i ∣ d} f (i) = d$ が成立するから，メビウスの反転公式により $f (d) = \sum_{i ∣ d} μ (\frac{d}{i}) i = \prod_{p ∣ d} (p^{v_{p} (d)} - p^{v_{p} (d) - 1}) = φ (d) .$ したがって， $f (p - 1) = φ (p - 1) > 0$ により定理は示された．

さて，ここからは原始根を次々に応用していく．

$r$ を $mod p$ の原始根として固定する． $p$ と互いに素な整数 $a$ に対して， $a \equiv r^{k} (\mod p)$ なる $k$ がとれる．このとき， $a mod p$ に対して $k mod p - 1$ を対応させる写像 $ψ$ を定義できる．これは全単射であり， $ψ (1) = 0$ ， $ψ (a \cdot b mod p) = ψ (a) + ψ (b) (\mod p - 1)$ ， $ψ (a^{- 1}) = - ψ (a)$ などの性質をもつ．すなわち， $p$ と互いに素な整数全体での掛け算を $mod p$ で考えることと， $mod p - 1$ で足し算を考えることは，本質的に等価である（群として同型である）．上の証明で， $d ∣ p - 1$ のとき $x^{d} - 1 \equiv 0 (\mod p)$ の解がちょうど $d$ 個であることを用いたが，これも $ψ$ を考えることで明快になるだろう．

平方剰余との関係を少しだけ見る．ここでは $p$ は奇素数であるとし， $χ_{2} (p, a)$ を平方剰余記号とする．

定理 16（オイラーの基準）.

a^{\frac{p - 1}{2}} \equiv χ_{2} (p, a) (\mod p)

証明.

(- 1)^{2} \equiv 1, - 1 ≢ 1 (\mod p)

により

2 ψ (- 1) \equiv 0, ψ (- 1) ≢ 0 (\mod p - 1)

であるから，

ψ (- 1) \equiv \frac{p - 1}{2} (\mod p - 1)

である．いま，

a

が

mod p

で平方剰余であることは，

ψ (a) \equiv 2 ψ (t) (\mod p - 1)

なる

t

があると言いかえられる．これは

ψ (a)

が偶数であることと同値であり，このとき

ψ (χ_{2} (p, a)) \equiv 0 \equiv a \cdot \frac{p - 1}{2} (\mod p - 1)

であるからよい．

a

が平方剰余でない場合も同様．

系 17. 以下が成立する．特に，

χ_{2} (p, - 1) = 1 ⟺ p \equiv 1 (\mod 4)

．

χ_{2} (p, a b) = χ_{2} (p, a) χ_{2} (p, b), χ_{2} (p, - 1) = (- 1)^{\frac{p - 1}{2}}

平方剰余についてはあまり深堀りしない．最後に，位数の関連する議論で特に頻出の状況を確認しておく．

定理 18.

a^{m} \equiv a^{n} \equiv 1 (\mod p)

であるとき，

a^{(m, n)} \equiv 1 (\mod p)

証明.

ψ (a) \equiv x (\mod p - 1)

とすれば，示すべきことは

m x \equiv n x \equiv 0 (\mod p - 1) ⟹ (m, n) x \equiv 0 (\mod p - 1)

であるが，これは素因数分解の一意性から明らかである．

　なお， $ψ$ を使わずに次のように書くこともできる：ベズーの補題により， $s m + t n = (m, n)$ なる $s, t$ がとれるから， $a^{(m, n)} \equiv a^{s m + t n} \equiv 1 (\mod p)$ ．

フェルマーの小定理とあわせることで次の系が得られる（今回はこれを最もよく用いる）．特に後半の表現は， $b$ が素数であるなど約数が少ないときに威力を発揮する．

系 19.

a^{b} \equiv 1 (\mod p) ⟺ a^{(b, p - 1)} \equiv 1 (\mod p)

．特に，

b

が

p - 1

と互いに素であるとき，

a^{b} \equiv 1 (\mod p) ⟺ a \equiv 1 (\mod p)

．

$ψ$ を用いない証明を観察すると，一般の法に対して拡張可能であることがわかる．

定理 20.

x^{a} \equiv x^{b} \equiv 1 (\mod m)

であるとき，

x^{(a, b)} \equiv 1 (\mod m)

系 21.

a^{b} \equiv 1 (\mod n) ⟺ a^{(b, φ (n))} \equiv 1 (\mod p)

．

以下はちょっとした変種である． $x^{a} \equiv x^{b} \equiv - 1 (\mod m)$ のときに類似の結果が得られるか，検討してみよ．

定理 22.

x^{a} \equiv - 1, x^{b} \equiv 1 (\mod m)

であるとき，

x^{(a, b)} = - 1 (\mod m)

．

さらに $v_{2} (b) \leq v_{2} (a)$ であるならば， $m = 1, 2$ ．

証明.

m = 1, 2

のときは自明であるから，

m \geq 3

で考える．

x^{a} \equiv - 1 (\mod m)

により

x^{2 a} \equiv 1 (\mod m)

であるから，定理20により

x^{(2 a, b)} \equiv 1 (\mod m)

である．

(2 a, b) ∣ a

とすると，

- 1 \equiv x^{a} \equiv 1 (\mod m)

となり

m \geq 3

に矛盾する．よって

v_{2} (b) > v_{2} (a)

が成り立ち，後半の主張がまず得られる．

　さて，ベズーの補題によって $s a + t b = (a, b)$ なる $s, t$ をとると， $x^{(a, b)} \equiv x^{s a + t b} \equiv (- 1)^{s} (\mod m)$ となる．ここで $x^{(a, b)} \equiv 1 (\mod m)$ とすると， $m \geq 3$ と $x^{a} \equiv - 1 (\mod m)$ に矛盾する．

これらの定理をふまえると，素数以外の法でも原始根に類するものが存在すると都合がよい．次節で論じていこう．

5. LTEの補題

もし $mod m$ に原始根 $r$ があるならば， ${ord}_{m} (r) = φ (m)$ でなければならない．しかし，カーマイケルの定理により ${ord}_{m} (r) ∣ λ (m)$ が成立するので， $λ (m) = φ (m)$ となる．これが成り立つのは， $p$ を奇素数として $m = 1, 2, 4, p^{k}, 2 p^{k}$ のときのみである．したがって，一般の法でこそ原始根は存在しないものの，実はこれらの $m$ では原始根が存在するのである．中国剰余定理をふまれば，素べきの場合にそうした議論ができれば十分であろう．

さて， $mod p^{k}$ で考えるうえで付値の概念は重要である．しばらくその準備をする．

定義 3（ $p$ 進付値）.

n

を

0

でない整数とし，

p

を素数とする，

n

が

p

で割り切れる回数を

v_{p} (n)

で表す．これを

p

進付値とよぶ．

p

進付値は有理数全体に対してまで定義でき，以下の諸性質も拡張できるが，ここではそこまで扱わない．

次の補題の証明は容易であり，読者に委ねる：

補題 23.

v_{p} (n m) = v_{p} (n) + v_{p} (m)

，

v_{p} (n + m) \geq min (v_{p} (n), v_{p} (m))

．

次の補題が核心である.

定理 24（LTEの補題）.

p

を素数，

a, b

を

p

で割り切れない整数とし，

p ∣ a - b

が成立するとする（ただし

p = 2

のときは仮定を

4 ∣ a - b

に強める）．このとき，任意の非負整数

n

について

v_{p} (a^{n} - b^{n}) = v_{p} (a - b) + v_{p} (n)

．

証明.

a - b = k p^{e}

とおく（ここで

k

は

p

で割り切れない）．このとき，

\begin{aligned} v_{p} (a^{n} - b^{n}) & = v_{p} (a^{n} - (a - k p^{e})^{n}) \\ = v_{p} (n k p^{e} a^{n - 1} -_{n} C_{2} k^{2} p^{2 e} a^{n - 2} + \dots - (- k p^{e})^{n}) \\ = v_{p} (k p^{e}) + v_{p} (n a^{n - 1} -_{n} C_{2} k p^{e} a^{n - 2} + \dots + (- k p^{e})^{n - 1}) \\ = e + v_{p} (n a^{n - 1} -_{n} C_{2} k p^{e} a^{n - 2} + \dots + (- k p^{e})^{n - 1}) \end{aligned}

となる．したがって，

v_{p} (n) = v_{p} (n a^{n - 1} -_{n} C_{2} k p^{e} a^{n - 2} + \dots + (- k p^{e})^{n - 1})

を示せばよいが，そのためには

2

以上

n

以下の整数

l

に対して

v_{p} (_{n} C_{l} (k p^{e})^{l - 1} a^{n - l}) > v_{p} (n)

を示せばよく，さらに

k, a

は

p

と互いに素であるから

v_{p} (_{n} C_{l} p^{e (l - 1)}) > v_{p} (n)

を示せば十分である．

　整数の範囲で議論するために，少し特殊な変形を行う： $\begin{aligned} v_{p} (_{n} C_{l} p^{e (l - 1)}) + v_{p} (l) & = v_{p} (l \cdot_{n} C_{l} p^{e (l - 1)}) \\ = v_{p} (n (\binom{n - 1}{l - 1}) p^{e (l - 1)}) \\ \geq v_{p} (p^{e (l - 1)}) + v_{p} (n) = e (l - 1) + v_{p} (n) . \end{aligned}$ これを移項することで， $e (l - 1) > v_{p} (l)$ を示せばよい． $y = v_{p} (l), l = x p^{y}$ とおくと， $l \geq 2$ により $e (l - 1) > \frac{x p^{y} - 1}{p - 1} \geq \frac{p^{y} - 1}{p - 1} = p^{y - 1} + \dots + p + 1 \geq y$ となる．以上により $v_{p} (_{n} C_{l} (k p^{e})^{l - 1}) > v_{p} (n)$ が得られたから， $v_{p} (a^{n} - b^{n}) = e + v_{p} (n a^{n - 1} -_{n} C_{2} k p^{e} a^{n - 2} + \dots + (- k p^{e})^{n - 1}) = v_{p} (a - b) + v_{p} (n) .$

LTEの補題を用いることで，次の結果が得られる：

定理 25.

p

を奇素数，

k

を正整数とすると，

mod p^{k}

には原始根が存在する．

証明.

a

を

mod p

における原始根とする．

a^{p - 1} ≢ 1 (\mod p^{2})

であるときは

b = a

とし，

a^{p - 1} \equiv 1 (\mod p^{2})

であるときは

b = a + p

とすれば，

b

は

mod p

における原始根であり，かつ

b^{p - 1} \equiv 1 (\mod p^{2})

をみたす．なぜならば，

a^{p - 1} \equiv 1 (\mod p^{2})

のとき

b^{p - 1} \equiv (a + p)^{p - 1} \equiv a^{p - 1} + (p - 1) p a \equiv 1 - a p ≢ 1 (\mod p^{2})

であるからである．

以下， $b$ が $mod p^{k}$ で原始根であることを示す．そのためには， $b^{n} - 1 \equiv 0 (\mod p^{k})$ ，すなわち $v_{p} (b^{n} - 1) \geq k$ なる最小の正整数 $n$ が $(p - 1) p^{k - 1}$ であることを示せばよい．まず $b^{n} \equiv 1 (\mod p)$ であり， $b$ は $mod p$ における原始根であることから， $n$ は $p - 1$ の倍数である． $n = (p - 1) m$ とおくと，LTEの補題により $k \leq v_{p} (b^{n} - 1) = v_{p} ((b^{p - 1})^{m} - 1) = v_{p} (b^{p - 1} - 1) + v_{p} (m) = 1 + v_{p} (m)$ となるから， $m$ は $p^{k - 1}$ の倍数となる．よって， $n$ は $(p - 1) p^{k - 1}$ の倍数であり，定理は示された.

系 26.

p

を奇素数，

k

を正整数とすると，

mod 2 p^{k}

には原始根が存在する．

証明.

a

を

mod p^{k}

の原始根とするとき，

a

と

a + p^{k}

のうち奇数である方が

mod 2 p^{k}

での原始根となる．

以上によって， $m$ を法として原始根が存在するのは，ちょうど $m = 1, 2, 4, p^{k}, 2 p^{k}$ （ $p$ は奇素数）のときであることが示された．

では， $k \geq 3$ で $mod 2^{k}$ のときはどうなっているだろうか？　このときの問題は，LTEの補題が $v_{2} (a - b) = 1$ の場合に成立しないことである．逆に $v_{2} (a - b) \geq 2$ のときは成立するので，類似の結果が成立することが予想できる．

定理 27.

k \geq 3

に対し，

mod 2^{k}

では以下の条件をみたす「準原始根」

a

が存在する：

${ord}_{2^{k}} (a) = 2^{k - 2}$ であり，任意の奇数 $x$ に対して $x \equiv a^{t} (\mod 2^{k})$ または $x \equiv - a^{t} (\mod 2^{k})$ が成立する $2^{k - 2}$ 未満の非負整数 $t$ が一意に存在する．

証明. 実は，

a \equiv 3, 5 (\mod 8)

のときつねに条件をみたすことを示す（さらに逆も成り立つ．これは演習とする）．

　まず，位数が $2^{k - 2}$ であることを示す． $a^{n} \equiv 1 (\mod 2^{k})$ とすると， $a^{n} \equiv 1 (\mod 4)$ により $n$ は偶数である． $n = 2 m$ とおき，さらに $a = 8 x + y$ と表すと（ここで $y$ は $3$ または $5$ ）， $a^{2} = 64 x^{2} + 16 x y + y^{2} \equiv 9 (\mod 16)$ となるから， $v_{2} (a^{2} - 1) = 3$ ．したがって，LTEの補題により $k \leq v_{2} (a^{n} - 1) = v_{2} ((a^{2})^{m} - 1) = v_{2} (a^{2} - 1) + v_{2} (m) = 3 + v_{2} (n) - 1 = v_{2} (n) + 2$ であるから， $n$ は $2^{k - 2}$ の倍数である．これは $a$ の位数が $2^{k - 2}$ であることを意味する．

　さて， $a^{t} mod 2^{k}$ は $mod 8$ で $1$ または $a$ と合同である．一方で， $mod 8$ で $1$ または $a$ と合同なものは $mod 2^{k}$ で考えれば $2^{k - 2}$ 個であるから，結局 $a^{t} mod 2^{k}$ はそのようなもの全体を動く．任意の奇数 $x$ に対して， $x$ か $- x$ の一方は $1$ または $a$ と合同であるから，後半の条件も成り立つ．

これによって，定理20・定理22が原始根を用いて示せるようになる．また，上で「カーマイケルの定理がある意味で最良の結果である」と述べたことが裏付けられる．これらを納得せよ．

6. ジグモンディーの定理

少し脇道に逸れるが，参考のために主張と証明を紹介しておく．

定義 4（原始的素因数）.

{a_{n}}

を整数列とし，

m

を正整数とする．

a_{m}

の素因数

p

について，任意の

m

未満の正整数

k

に対して

a_{k}

が

p

で割り切れないとき，

p

を

a_{m}

の原始的素因数とよぶ．

定理 28（ジグモンディーの定理）.

x, y

を

0

でない互いに素な整数とし，

| x | \neq | y |

をみたすとする．

a_{n} = x^{n} - y^{n}

とすれば，以下の場合を除いて

a_{n}

は原始的素因数をもつ：

$n = 1$ かつ $| x - y | = 1$ のとき
$n = 2$ かつ $| x + y | = 2^{k}$ のとき
$n = 3$ かつ $(x, y) = (1, - 2), (- 2, 1), (- 1, 2), (2, - 1)$ のとき
$n = 6$ かつ $(x, y) = (1, 2), (2, 1), (- 1, - 2), (- 2, - 1)$ のとき

証明. 工事中

問題への応用

ここまで, 位数の議論に関係する理論を解説してきた. ここからはそれらの定理などをどのように応用していくかを考えていく. まずは簡単な応用, 次にそれを利用した飛び道具的な使い方を見ていく. 最後に演習問題をおいておく.

1. 求値問題への応用

★☆☆☆☆

$20^{10000}$ を $13$ で割った余りを求めよ．

解答

何通りか解法を紹介する：

$20^{10000} \equiv 7^{10000} \equiv 7^{10000 mod 12} \equiv 7^{4} \equiv 2401 \equiv 9 (\mod 13)$
$20^{10000} \equiv \frac{40^{10000}}{2^{10000}} \equiv 2^{- 10000} \equiv 2^{- 10000 mod 12} \equiv 2^{8} \equiv 256 \equiv 9 (\mod 13)$
$20^{10000} \equiv 2^{20000} 5^{10000} \equiv 2^{8} 5^{4} \equiv 256 \cdot 25^{2} \equiv 9 \cdot (- 1)^{2} \equiv 9 (\mod 13)$

このように，指数に対して余りを求めるときは，愚直な計算のほかにフェルマーの小定理やカーマイケルの定理（オイラーの定理）が使えるのはもちろんだが，他にも計算すべき値を小さくするために素因数分解するなど，様々な小技を使うことができる．以下に示すのもその一つである．

★★☆☆☆

JMO 2007 予選問2

$11^{12^{13}}$ の十の位を求めよ．

解答

十の位のかわりに下二桁を求める．すなわち， $11^{12^{13}}$ を $100$ で割った余りを求める．

$λ (100) = lcm (2, 20) = 20$ ， $λ (20) = lcm (2, 4) = 4$ により， $11^{12^{13}} \equiv 11^{12^{13} mod 20} \equiv 11^{12^{13 mod 4}} \equiv 11^{12} (\mod 100)$ までは計算できるが，ここから工夫が必要である．以下には二つの選択肢を示す：

$11^{1} \equiv 11, 11^{2} \equiv 21, 11^{3} \equiv 31, \dots, (\mod 100)$ であるから， $11^{a} \equiv 10 a + 1 (\mod 100)$ であると予想でき，これは帰納法によって証明できる．よって， $11^{12} \equiv 121 \equiv 21 (\mod 100)$ ．
二項定理により， $11^{12} \equiv (10 + 1)^{12} \equiv \dots +_{12} C_{2} \cdot 10^{2} + 12 \cdot 10 + 1 \equiv 21 (\mod 100)$ ．

ここからは，一歩進んで総和や総積を絡めていく．

★☆☆☆☆

$1^{2} + 2^{2} + \dots + 100^{2}$ を $17$ で割った余りを求めよ．

解答

二乗の総和の公式を用いればよいが，少しだけ工夫する． $1^{2} + 2^{2} + \dots + 100^{2} \equiv (1^{2} + 2^{2} + \dots + 101^{2}) - 101^{2} \equiv 6 (1^{2} + 2^{2} + \dots + 16^{2}) - (- 1)^{2} (\mod 17)$ とすれば， $1^{2} + 2^{2} + \dots + 16^{2} \equiv \frac{16 \cdot 17 \cdot 33}{6} \equiv 0 (\mod 17)$ であるから，求める余りは $16$ ．

なお，これは $mod 17$ の原始根 $g$ をとることで次のようにも理解できる： $1^{2} + 2^{2} + \dots + 16^{2} \equiv g^{0} + g^{2} + \dots + g^{30} \equiv \frac{g^{32} - 1}{g^{2} - 1} \equiv 0 (\mod 17)$

上の解答で述べた原始根による理解は，指数が大きくなるとその真価を発揮する．

★★☆☆☆

$p$ を素数， $a$ を整数とするとき， $1^{a} + 2^{a} + \dots + (p - 1)^{a} \equiv 0 (\mod p)$ と同値な $p, a$ に関する条件を求めよ．

解答

$g$ を $mod p$ における原始根とする， $g^{a} ≢ 1 (\mod p)$ のとき， $\sum_{k = 1}^{p - 1} k^{a} \equiv \sum_{k = 0}^{p - 2} g^{a k} \equiv \frac{g^{a (p - 1) - 1}}{g^{a} - 1} \equiv 0 (\mod p) .$ ただし，最後にフェルマーの小定理を用いた．一方で $g^{a} \equiv 1 (\mod p)$ のとき， $\sum_{k = 1}^{p - 1} k^{a} \equiv 1 \cdot (p - 1) \equiv - 1 ≢ 0 (\mod p) .$ よって求める条件は $g^{a} ≢ 1 (\mod p)$ が，これは $p - 1 ∤ a$ と言いかえられる．

なお，原始根を使わなくても解くことはできる．各自で試みよ．

ただし，原始根だけに拘泥してはならない．その前にできることがないか考えよう．

★★★☆☆

ウォルステンホルムの定理

素数 $p \geq 5$ に対して， $\sum_{n = 1}^{p - 1} \frac{1}{n} \equiv 0 (\mod p^{2})$ が成り立つことを示せ．

解答

$\sum_{n = 1}^{p - 1} \frac{1}{n} \equiv \frac{1}{2} \sum_{n = 1}^{p - 1} (\frac{1}{n} + \frac{1}{p - n}) \equiv \frac{p}{2} \sum_{n = 1}^{p - 1} (\frac{1}{n (p - n)}) \equiv - \frac{p}{2} \sum_{n = 1}^{p - 1} \frac{1}{n^{2}} \equiv 0 (\mod p^{2})$

ただし，最後の等号は例題5から得られる．なお，最初の式変形をせずに原始根を持ち出しても $mod p$ の範疇から出られないため，最初の式変形は本質的である．

★★★☆☆

$a$ を $1$ ではない奇数とする． $\sum_{n = 1}^{p - 1} n^{a} \equiv 0 (\mod p^{2})$ となる素数 $p$ の条件を求めよ．

積の場合にも似たようなことができる．

★★☆☆☆

ウィルソンの定理

素数 $p$ に対して， $(p - 1)! \equiv - 1 (\mod p)$ を示せ．

解答

$p = 2$ のときは明らかであるから， $p \geq 3$ とする．

解法1.　 $f (x mod p) \equiv x^{- 1} mod p$ によって定義される写像 $f : {1, 2, \dots, p - 1} \to {1, 2, \dots, p - 1}$ は全単射であり， $x ≢ \pm 1 (\mod p)$ であれば $f (x) ≢ x (\mod p)$ であるから， $(p - 1)! \equiv 1 \cdot (- 1) \cdot (2 \cdot f (2)) \dots (k \cdot f (k)) \equiv - 1 (\mod p) .$

解法2.　 $g$ を $mod p$ における原始根とすると， $(p - 1)! \equiv \prod_{n = 1}^{p - 2} g^{n} \equiv g^{\frac{(p - 2) (p - 1)}{2}} \equiv g^{\frac{p - 1}{2}} g^{(p - 1) \frac{p - 3}{2}} \equiv - 1 (\mod p) .$

解法3.　以下の両辺を $\prod_{n = 1}^{p - 2} (1 + n)$ で割ればよい： $\prod_{n = 1}^{p - 2} (1 + n) \equiv \prod_{m = 1}^{p - 2} (1 + \frac{1}{m}) \equiv \frac{1}{(p - 2)!} \prod_{n = 1}^{p - 2} (1 + n) (\mod p) .$

上の解法1のように，うまく二つずつ組み合わせるというのもよくある手法である．以下はやや非自明なものである．

★★★☆☆

$\prod_{n = 1}^{30} (1 + n^{2})$ を $31$ で割った余りを求めよ．

解答

$g$ を $mod 31$ における原始根とすると， $\begin{aligned} \prod_{n = 1}^{30} (1 + n^{2}) & \equiv 2^{2} \cdot \prod_{n = 2}^{29} \frac{n^{4} - 1}{n^{2} - 1} \\ \equiv 4 \cdot \prod_{1 \leq m \leq 29, m \neq 15} \frac{g^{4 m} - 1}{g^{2 m} - 1} \\ \equiv 4 \cdot \prod_{1 \leq m \leq 29, m \neq 15} \frac{g^{2 m} - 1}{g^{2 m} - 1} \equiv 4 (\mod 31) . \end{aligned}$ ここで， $1 \leq m \leq 29, m \neq 15$ を動くとき， $4 m mod 30$ と $2 m mod 30$ のとりうる値全体は多重集合として一致することを用いた．

原始根を使わずに表現すれば，この問題では ${i^{4} mod 31}$ と ${i^{2} mod 31}$ が多重集合として一致することを用いたことになる．しばしば $mod p$ では $a$ 乗写像と $(a, p - 1)$ 乗写像が本質的に等価となるので，留意しておくと見通しが良いことがある（系21にも注意）．

#10

★★★☆☆

OMO 2013 Winter 問42

$\prod_{n = 0}^{100} (1 - n^{2} + n^{4})$ を $101$ で割った余りを求めよ．

#11

★★★☆☆

OMC067(E)

$p = 10^{9} + 7$ は素数である． $a_{1}^{10^{9} - 1} + a_{2}^{10^{9} - 1} + \dots + a_{p}^{10^{9} - 1}$ が $p$ の倍数となるような， $1$ 以上 $p - 1$ 以下の整数の組 $(a_{1}, a_{2}, \dots, a_{p})$ の個数を $10000$ で割った余りを求めよ．

2. 法をどう選ぶか

まずは明らかなものから．

#12

★★☆☆☆

OMC014(D)

次の条件をみたす $2$ 以上 $100$ 以下の偶数 $n$ をすべて求めよ：

$n < p q$ かつ $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv n (\mod p q)$ をみたす素数 $p, q$ が存在する．

解答

それぞれの素数を法として考えよう． $p = q$ のときは様子が変わってしまうので，まずは $p > q$ のときに考える．まず $q = 2$ のときは $(p - 1)^{q - 1} + (q - 1)^{p - 1} = p - 1 + 1 = p$ により $n = p$ となるが， $n$ は偶数であるから不適．以下， $q > 3$ とする．いま， $p ∤ q - 1$ であるから $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv 1 + 1 = 2 (\mod p)$ である．

さて， $q ∤ p - 1$ ならば同様に $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv 2 (\mod q)$ となる．まとめれば $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv 2 (\mod p q)$ となり，これは $n = 2$ のときに対応する（たとえば $(p, q) = (7, 5)$ で実現できる）．

$q ∣ p - 1$ のときも同様に $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv 2 - p (\mod p q)$ であるから， $n = p q - p + 2$ となる．あとは適当な大小評価によって絞り込めば， $n = 16, 28, 40, 46, 64, 76, 88$ とわかる．

最後に $p = q$ のときを考える． $p = q = 2$ のときは $n = 2$ を得る． $p \geq 3$ のとき， $(p - 1)^{q - 1} + (q - 1)^{p - 1} \equiv 2 (p - 1)^{p - 1} \equiv 2 (p^{p - 1} - \dots - (p - 1) p + 1) \equiv 2 (p + 1) (\mod p^{2}) .$ $p \geq 3$ で $2 (p + 1) < p^{2}$ であるから，このとき $n = 2 (p + 1)$ となり， $n = 8, 12, 16, 24, 28, 36, 40, 48, 60, 64, 76, 84, 88, 96.$

$(p - 1)^{p - 1} (\mod p^{2})$ のようにオイラーの定理などが適用できないときには，しばしば（フェルマーの小定理やLTEの補題の証明をなぞるように）二項定理を使うことで強引に値が計算できることは念頭に置くとよい．この発想は例題3にも現れた．

次の問題も似たような法のとり方が有効である．

#13

★★☆☆☆

JBMO 2020 SLP N8

$1 + \frac{p^{q} - q^{p}}{p + q}$ が素数になるような素数の組 $(p, q)$ をすべて求めよ．

次は小さい具体的な法の選択について見ていく．系11なども念頭に置くこと．

#14

★☆☆☆☆

京大 2018

$n^{3} - 7 n + 9$ が素数となるような整数 $n$ をすべて求めよ．

解答

$n^{3} - 7 n + 9 \equiv n - 7 n + 9 \equiv 0 (\mod 3)$ により $n^{3} - 7 n + 9 = 3$ が必要であり， $n = 1, 2, - 3$ ．

#15

★☆☆☆☆

$p + q = (p - q)^{3}$ をみたす素数の組 $(p, q)$ をすべて求めよ．

$n^{2} \equiv 0, 1, 4 (\mod 8)$ も非常に便利である．次の問題がよい応用例となるだろう：

#16

★★☆☆☆

$x^{2} + y^{2} + z^{2} = 2^{m}$ をみたす整数 $x, y, z$ と非負整数 $m$ の組をすべて求めよ．

その他の法について考えていく前に，次の主張を確認しておく：

定理 29.

n

を正整数とする．整数

a

を動かしたときに，

a^{n} mod p

のとりうる値は

1 + \frac{p - 1}{(p - 1, n)}

種類である．

これは原始根を利用すればすぐにわかる．類似の命題が $mod p^{m}$ でも成立する． $p ∣ a$ のときの処理が煩雑になるのでここでは割愛するが， $n$ と $p^{m - 1} (p - 1)$ の最大公約数が大きいほどとりうる値の個数が少なくなるという性質は重要である．たとえば， $a^{3}$ や $a^{6}$ が現れる問題ではしばしば $mod 7$ や $mod 9$ が有用である．

#17

★☆☆☆☆

$x^{3} + y^{3} + z^{3} = 5$ をみたす整数の組 $(x, y, z)$ は存在しないことを示せ．

#18

★★☆☆☆

JBMO 2020 SLP N1

$8^{n} + 47$ が素数となるような正整数 $n$ は存在するか．

解答

存在しないことを示す．そのために， $8^{n} + 47$ が素数になったと仮定する．

まずは， $8 = 2^{3}$ や $8 \pm 1 = 7, 9$ であることから $mod 7, 9$ が使えそうだが， $mod 7$ では情報は増えない． $mod 9$ で検討すると（ $mod 3$ でもよい）， $n \equiv 1 (\mod 2)$ が必要である．これによって $2^{6 m - 3} + 47$ の形だけ考えればよい（ $n = 2 m - 1$ としている）．これができる限り少ない値しか取らない法を探そう．

まず，とりうる値が一つしかないのは（ $2^{6} - 1 = 63$ により）上ですでに調べた $mod 7, 9$ などである．とりうる値が二つになるのは， $2^{6} + 1 = 65$ により（←なぜか？） $mod 5, 13$ などが該当する．

$mod 5$ では $m \equiv 0 (\mod 2)$ が必要で， $mod 13$ では $m \equiv 1 (\mod 2)$ が必要なので，矛盾する．

もう少し大きい法にも挑戦してみよう．

#19

★★☆☆☆

Rioplatense 2022 Level3 問1

$x^{2} + y^{11} - z^{2022!} = n$ をみたす整数の組 $(x, y, z)$ が存在しないような正整数 $n$ は無限に存在することを示せ．

解答

式の形がすさまじいので，十中八九適切な法を選べば解けるだろう（そうでないならば，超難問になりうる）．

$mod m$ で考えるとして， $2, 11$ と $φ (m)$ が非自明な公約数を持ってほしい． $2022!$ は約数を大量にもつので， $m$ は小さく定数として固定すれば事足りるだろう．この条件をみたす最小の $m$ は $23$ であり，実際 $mod 23$ で考えれば $n \equiv 20 (\mod 23)$ のとき $x, y, z$ が存在しないことがわかる.

例題20はかなり極端な例である．巨大な素因数分解を実現する計算機とともに考えてよい：

#20

★★★★☆

$2^{m} - 5^{n} = 3$ をみたす非負整数の組 $(m, n)$ をすべて求めよ．

解答

$m \geq 8$ のとき $mod 2^{8}$ を見て $n \equiv 35 (\mod 64)$ であり，さらに $mod 641$ を見れば存在しないことが分かる．

あとは $m \leq 7$ を調べて $(m, n) = (7, 3), (3, 1), (2, 0)$ ．

$641$ とは， $5^{64} - 1$ の素因数であって， $2$ の位数も比較的小さい ( $64$ ) ものである．

#21

判定中

USAMO 1982 問4

ある正整数 $k$ が存在して，任意の正整数 $n$ に対して $k \cdot 2^{n} + 1$ が合成数となることを示せ．

参考.　式の形を少し変えて（ $2^{n}$ の底や $k$ の付く場所など），同様の問題が解けるか考察せよ．

なお，適当な法をとって考えることだけに拘泥してはならないことを，改めて注意しておこう．

#22

★☆☆☆☆

$n^{4} + 4$ が素数となるような正整数 $n$ をすべて求めよ．

解答

一見 $mod 5$ などを使いそうだが， $n^{4} + 4 = (n^{2} + 2 n + 2) (n^{2} - 2 n + 2)$ に注意することで $n = 1$ のみ．

この手の因数分解や，単なる不等式評価は意外と失念しがちである．特に上で使った恒等式（ソフィー＝ジェルマンの恒等式）は，指数の和の形に紛れ込むことがしばしばあるので注意しておこう．

3. 約数に対する考察

ここで主に使うのは，次の問題のような考え方である：

#23

★★★☆☆

$p$ を素数とする.

$(1)$ 　 $n$ を $1$ ではない整数とするとき， $\frac{n^{p} - 1}{n - 1}$ の素因数は $p$ であるか $p$ で割って $1$ 余ることを示せ.

$(2)$ 　 $p$ で割って $1$ 余る素数が無限に存在することを示せ．

(2)を解くうえでは，最も有名な素数の無限性の証明の手順を思い起こすとよいだろう．

解答

$(1)$ 　 $\frac{n^{p} - 1}{n - 1}$ の $p$ でない素因数 $q$ であって， $p$ で割った余りが $1$ でもないものが存在したと仮定する．このとき， $n^{p} \equiv 1 (\mod q)$ が成立する．また，これにより $n$ は $p$ で割り切れないから，フェルマーの小定理により $n^{q - 1} \equiv 1 (\mod q)$ も成立する．よって，仮定により $(q - 1, p) = 1$ なので， $n \equiv n^{(q - 1, p)} \equiv 1 (\mod q)$ が成立するが， $0 \equiv \frac{n^{p} - 1}{n - 1} = n^{p - 1} + \dots + n + 1 \equiv 1^{p - 1} + \dots + 1 + 1 \equiv p (\mod q)$ となるので矛盾する（ここの議論にはLTEの補題を用いてもよい）．

$(2)$ 　 $p$ で割って $1$ 余る素数が有限個であったと仮定し，それらの総積を $S$ とする． $(1)$ で $n = p S$ とすると， $\frac{n^{p} - 1}{n - 1}$ は $p$ で割り切れず，また $S$ の定め方から $p$ で割って $1$ 余る素因数ももたない．これは $(1)$ により $\frac{n^{p} - 1}{n - 1} = \pm 1$ であることを意味するが，明らかに不合理である．

この問題からもわかるように， $a^{n} - b^{n}$ の素因数には位数の議論によって大きな制約が付くことが多く，これを利用した問題は数多い．もう少し精密に書くと，次のようになる：

#24

判定中

$n$ を正整数とし， $Φ_{n} (x, y)$ を $n$ 次斉次円分多項式とする． $a, b$ が互いに素な整数であるとき， $Φ_{n} (a, b)$ の $n$ と互いに素な素因数を $n$ で割った余りは $1$ であることを示せ．

ヒント

$d ∣ n$ とすると， $Φ_{n} (a, b) ∣ \frac{a^{n} - b^{n}}{a^{d} - b^{d}}$ であるから，適当な $d$ をとればよい．

これ以降， $a^{n} - b^{n}$ に関連した問題をあくまでここだけの用語として「円分型の問題」とよぶことにする．

これをディオファントス方程式に応用してみよう．次の問題は，安易に $mod$ や不等式評価を使うだけでは難しそうだ．

#25

★★★☆☆

IMO 2006 SLP N5

$\frac{x^{7} - 1}{x - 1} = y^{5} - 1$ をみたす $1$ でない整数の組 $(x, y)$ をすべて求めよ．

解答

両辺ともに円分型の式なので，どちらの素因数に関する議論をしようか迷うが，左辺の素因数の制約の方が厳しい．具体的には， $p ∣ \frac{x^{7} - 1}{x - 1}$ とすると， $p = 7$ または $p \equiv 1 (\mod 7)$ である．この情報を右辺に反映させたい．これは盲点になりがちだが，よく考えると右辺は $(y - 1) (y^{4} + y^{3} + y^{2} + y + 1)$ と因数分解できるから，二つの因数を $7$ で割った余りはともに $0$ または $1$ である（としたいところだが，各因数が負のときは少しだけ話が違うので， $y > 1$ を事前に確認しておく必要があることに注意しておこう）．これらは両立しない．すなわち，解は存在しない！

状況に応じて，不等式評価との併用も重要である：

#26

★★★☆☆

APMO 2012 問3

$\frac{n^{p} + 1}{p^{n} + 1}$ が整数となるような素数 $p$ と正整数 $n$ の組をすべて求めよ．

解答

$p = 2$ のとき $n = 2, 4$ が条件をみたす． $p \geq 3$ のとき，分母は偶数なので分子も偶数．すなわち $n$ は奇数である．明らかに $n \geq 3$ であり，このとき $\frac{n^{p} + 1}{p^{n} + 1} \geq 1$ は $p \geq n$ を意味する．

ここで上記の手法を用いる． $n$ は奇数なので分母は $p + 1$ で割り切れる．すなわち $n^{p} \equiv - 1 (\mod p + 1)$ ．また，オイラーの定理により $n^{φ (p + 1)} \equiv 1 (\mod p + 1)$ なので $n^{(p, φ (p + 1))} \equiv - 1 (\mod p + 1)$ ．いま $p \geq 3$ により $φ (p + 1) \leq \frac{p + 1}{2} < p$ であるから $(p, φ (p + 1)) = 1$ ．よって， $p + 1 ∣ n + 1 (\mod p + 1)$ であり，特に $n + 1 \geq p + 1$ であるから，最初に得られた $p \geq n$ とあわせて $n = p$ ．これは条件をみたす．

よって，求める組は（ $p$ を任意の素数として） $(n, p) = (p, p), (4, 2)$ である．

#27

★★★☆☆

$\frac{n^{p} - 1}{p^{2} - n^{2}}$ が非負整数となるような素数 $p$ と正整数 $n$ の組をすべて求めよ．

考え方

$p > n$ であることに注意しておく．分子の素因数は， $n - 1$ の素因数か， $p$ か， $p$ で割って $1$ 余るもののいずれかである．一方で，分母の約数を $p$ で割った余りは，基本的に $1$ になることはない．これでもう解けるだろう．

解答

$n = 1$ のときはつねに条件をみたすから， $1 < n < p$ とする．このとき， $p^{2} - n^{2} = (p + n) (p - n)$ の素因数を $p$ で割った余りは $0, 1$ にはなりえない．一方で， $\frac{n^{p} - 1}{n - 1}$ の素因数を $p$ で割った余りは $0$ か $1$ であるから， $(p^{2} - n^{2}, \frac{n^{p} - 1}{n - 1}) = 1$ ．よって $\frac{n - 1}{p^{2} - n^{2}}$ は正整数となるが， $n - 1 \geq p^{2} - n^{2}$ とはなりえない．

よって，求める組は（ $p$ を任意の素数として） $(n, p) = (1, p)$ である．

#28

判定中

IMO 1990 問3

$\frac{2^{n} + 1}{n^{2}}$ が整数となるような， $1$ より大きい整数 $n$ をすべて求めよ．

LTEの補題を有名にした，いわゆる「マスターデーモン」である．カギは $n$ の最小の素因数を使うことである．

解答

分子は奇数であるから $n$ も奇数である． $n$ の最小の素因数を $p$ とすると， $2^{n} \equiv - 1 (\mod p)$ であり，フェルマーの小定理により $2^{p - 1} \equiv 1 (\mod p)$ でもあるから， $2^{(n, p - 1)} \equiv - 1 (\mod p)$ ．ここで， $p$ が $n$ の最小の素因数であることから $(n, p - 1) = 1$ となるので， $3 \equiv 0 (\mod p)$ ，すなわち $p = 3$ である．

いま， $n = 3^{a} m$ （ $a$ は正整数， $m$ は $3$ で割り切れない正整数）と表すと，分母は $3$ で $2 a$ 回割り切れるが，分子はLTEの補題により（ $n$ は奇数である事に注意） $3$ で $a + 1$ 回しか割り切れない．よって， $a = 1$ が必要である．

$m > 1$ として，その最小の素因数 $q (\geq 5)$ をとると，同様にして $2^{(3 m, q - 1)} \equiv - 1 (\mod q)$ ． $q$ の最小性と $(- 1)^{3} = - 1$ に注意すれば， $2^{3} \equiv - 1 (\mod q)$ すなわち $q ∣ 9$ を得るが，これはありえない．よって $m = 1$ となり，求める $n$ は $3$ のみである．

指数が素数や素べきでなくても，その素因数をとって最小性などを駆使すればうまくいくこともあるという好例である．

次の問題は見た目のうえでは少し毛色が違うが，方向性はまったく同じである．

#29

判定中

IMO 2012 SLP N6

$x, y$ を正整数とする．任意の整数 $n$ について $x^{2^{n}} - 1$ が $2^{n} y + 1$ で割り切れるならば， $x = 1$ であることを示せ．

考え方

まず， $x^{2^{n}} - 1$ という形をふまえれば， $2^{n} y + 1$ の適当な素因数 $p$ をとればよさそうである． $p$ に課したい制約は， $x^{2^{n}} - 1 \equiv x^{(2^{n}, p - 1)} - 1 (\mod p)$ に注意すれば $p - 1$ があまり $2$ で割り切れないこと，さらに $x$ に対して十分大きいことである．

一つ目の制約を考えると，できれば小さい $n$ に対する $2^{n} y + 1$ の素因数をとりたい（ $v_{2} (p - 1)$ が小さく，抑えやすいので）．しかし，二つ目の制約をふまえてその点は譲歩してもらい，実は $n$ が大きくても $2^{n} y + 1$ の素因数 $p$ で $v_{2} (p - 1)$ が小さいものがあることを示したい．

いま， $n$ の大小はさておき $2^{n} (\mod p)$ は周期的だから， $p ∣ 2 y + 1$ かつ十分大きいある整数 $n$ に対して $p ∣ 2^{n} y + 1$ ，といったようにできる．ここで， $v_{2} (\frac{2^{n} y + 1}{p} - 1)$ は小さいので， $\frac{2^{n} y + 1}{p}$ の素因数 $q$ であって $v_{2} (q - 1)$ が小さいものが存在する．さらに $n$ を工夫してとれば， $q$ は大きくできる．というのも，フェルマーの小定理を使って，小さい素数 $r$ に対して $2^{n} y + 1 \equiv 2 y + 1 (\mod r)$ となるように $n$ をとってしまえばよいからである．

略解

$n = 1 + φ ((2 y + 1)^{2} \cdot x^{2 y + 1}!)$ とすると， $2^{n} y + 1 \equiv 0 (\mod 2 y + 1)$ である． $2^{n} y + 1 \equiv 2 y + 1 (\mod (2 y + 1)^{2})$ により， $\frac{2^{n} y + 1}{2 y + 1}$ は整数であり，かつ $2 y + 1$ と互いに素である．さらに， $2 y + 1$ を割り切らない $x^{2 y + 1}$ 以下の任意の素数 $q$ について $2^{n} y + 1 \equiv 2 y + 1 ≢ 0 (\mod q)$ であるから， $\frac{2^{n} y + 1}{2 y + 1}$ の素因数は $x^{2 y + 1}$ より大きい．また， $\frac{2^{n} y + 1}{2 y + 1} - 1 \equiv - \frac{2 y}{2 y + 1} ≢ 0 (\mod 2^{v_{2} (2 y) + 1})$ であるから， $\frac{2^{n} y + 1}{2 y + 1}$ の素因数 $p$ であって $v_{2} (p - 1) \leq v_{2} (2 y)$ をみたすものが存在する．仮定により $x^{2^{n}} \equiv 1 (\mod p)$ なので， $x^{2^{v_{2} (2 y)}} - 1 \equiv 0 (\mod p)$ ，すなわち $x^{2 y} - 1 \equiv 0 (\mod p)$ ．しかし， $p > x^{2 y + 1}$ なので，これは $x = 1$ を意味する．

このように， $p$ としていくらでも大きくとることで不等式評価に持ち込み，矛盾を導くことができる．分母が円分型である場合には，大きな素数 $p$ をとるためにジグモンディーの定理が使えることもある．

最後に，一見すると円分型ではないが，うまく利用できるものも見ていこう．

#30

判定中

Korea MO 2007

$p^{p} + q^{q} + 1$ が $p q$ で割り切れるような素数の組 $(p, q)$ をすべて求めよ．

解答

$p = q$ のときは明らかに不適なので，対称性により $p > q$ として考えれば十分． $p^{p} + q^{q} + 1 \equiv q^{q} + 1 \equiv 0 (\mod p)$ だから $(p - 1, q) = q$ または $q + 1 \equiv 0 (\mod p)$ となり，いずれにせよ $p > q$ から $p = q + 1$ ，すなわち $(p, q) = (3, 2)$ になる．よって，求める解は $(p, q) = (3, 2), (2, 3)$ ．

#31

判定中

PMO 2022 問6

以下をみたす正整数 $n_{1}, n_{2}, \dots, n_{2022}, m$ は存在するか： $({n_{1}}^{2020} + {n_{2}}^{2019}) ({n_{2}}^{2020} + {n_{3}}^{2019}) \dots ({n_{2021}}^{2020} + {n_{2022}}^{2019}) ({n_{2022}}^{2020} + {n_{1}}^{2019}) = 11^{m} .$

解答

結論から言えば存在しないのだが，この手の問題は一つうまく構成するだけというオチである可能性もあるので，本当に構成が思いつかないかは注意深く確かめた方がよい．

さて，構成を作ろうとしてもなぜうまくいかないのかを考えてみると，それぞれの文字が $11$ で割り切れる回数などをうまく調節しようとしても，どうにもできないのである．

とにかく， $n_{i}^{2020} + n_{i + 1}^{2019}$ が $11$ 以外の素因数をもつはずであることを示せばよいが，一つを単独で見ても一筋縄にはいかないので，任意の $i$ で $11$ のべきだったとしてどうなるかを見ないといけない．

$n_{1}, n_{2}, \dots, n_{2022}$ はいずれも $11$ で割り切れないとしてよい．対称性により， $i$ を動かしたときに $n_{i}^{2020} + n_{i + 1}^{2019}$ のうち最小のものが $n_{1}^{2020} + n_{2}^{2019} = 11^{k}$ であったとすると，任意の $i$ で $n_{i}^{2020} \equiv - n_{i + 1}^{2019} (\mod 11^{k})$ が成立する．いま $n_{1}^{2020^{2022}} \equiv - n_{1}^{2019^{2022}} (\mod 11^{k})$ だが， $n_{1}$ は $11$ で割り切れないので $n_{1}^{2020^{2022} - 2019^{2022}} \equiv - 1 (\mod 11^{k})$ ．

さて， $2020^{2022} - 2019^{2022}$ は $11, 10$ と互いに素であることがわかるので， $n_{1} \equiv - 1 (\mod 11^{k})$ である．よって $n_{1} \geq 11^{k} - 1$ だが， $(11^{k} - 1)^{2020} + 1 \leq n_{1}^{2020} + n_{2}^{2019} = 11^{k}$ であるから矛盾．

#32

★★★★★

Japan TST 2016 問9

$p < q < r < s$ なる素数の組 $(p, q, r, s)$ であって， $p^{s} - r^{q} = 3$ をみたすものをすべて求めよ．

解答

偶奇を見ることで $p, r$ の一方は $2$ であり，大小の制約とあわせて $p = 2$ とわかる．このとき， $2^{s} - s^{q} = 3 - (s^{q} - r^{q}) = 3 - (s - r) (s^{q - 1} + \dots + r^{q - 1}) < 3 - 2 \cdot 2 < 0$ から $s < q \log_{2} s$ が得られる．また， $2^{s} > 2^{s} - 3 = r^{q}$ から $s > q \log_{2} r$ がわかる．

与式を $2 (2^{s - 1} - 1) = r^{q} + 1$ と変形する．フェルマーの小定理から左辺は $s$ で割り切れるので， $r^{q} \equiv - 1 (\mod s)$ . したがって， $s ∣ r + 1$ または $s \equiv 1 (\mod q)$ となる．大小の制約から前者は成立せず， $s$ が奇数であることとあわせて $s = 2 k q + 1$ とかける．改めて与式は $2 (2^{2 k q} - 1) = r^{q} + 1$ となり，特に $2 (2^{k} - 1) (2^{k} + 1) ∣ r^{q} + 1$ ．

さて，以下の不等式評価により， $2 (2^{k} - 1) (2^{k} + 1)$ の素因数 $a$ は $q$ 以下である： $2^{k} - 1 < 2^{k} + 1 < 2^{\frac{s}{2 q}} + 1 < 2^{\frac{\log_{2} s}{2}} + 1 = \sqrt{s} + 1 < \frac{s}{\log_{2} s} + 1 < q + 1.$ このとき， $a ∣ r^{q} + 1$ は $a ∣ r^{(q, a - 1)} + 1 = r + 1$ を意味するので， $2 (2^{k} - 1) (2^{k} + 1) ∣ r + 1$ である（ $v_{q} (2 (2^{k} - 1) (2^{k} + 1)) \leq 1$ に注意）．ここで， $2 (2^{k} - 1) (2^{k} + 1) = 2^{\frac{s - 1}{q} + 1} - 2 > 2^{\frac{s}{q}} - 2 > r - 2$ により $2 (2^{k} - 1) (2^{k} + 1) \geq r - 1 > \frac{r + 1}{3}$ であるので， $2 (2^{k} - 1) (2^{k} + 1) = r + 1$ が成立する．

これを $s > q \log_{2} r$ に代入すると $2 k q + 1 > q \log_{2} (2^{2 k + 1} - 3)$ ．よって， $1 > q \log_{2} (2 - \frac{3}{2^{2 k}}) \geq q \log_{2} \frac{5}{4} .$ これにより $q = 3$ となる．このとき $s < q \log_{2} s$ から $(p, q, r, s) = (2, 3, 5, 7)$ に絞られ，これは条件をみたす．

4. いつ位数について考えるべき（でない）か？

ここまで，位数に関する議論を中心に応用例を見てきた．位数や原始根を使えば $a^{k} \equiv 1 (\mod n)$ なる $k$ に関する情報がわかることが多く，ここで $n$ をうまくとっておくことで有効な議論ができるのである．また，原始根をとることで単なる代数的操作になってしまうこともあることを見た．

逆に，位数の議論の限界について考えよう．まず，原始根は（存在こそすれど）具体的に求めることが難しい．たとえば，次の単純な予想が未解決であることからも，難しさが実感できるだろう：

Artinの原始根予想. 整数

a

が平方因子をもたないとき，

a

を原始根にもつ素数

p

が無限に存在するだろう．

すなわち， $a$ を固定して $p$ を動かすといった方向性の議論は，かなりの確率で筋が悪い．

また，位数は加法的な性質に乏しい．具体的には， $a, b, a + b$ の $mod p$ での位数には規則性があまりないので，その方針でうまくいくときには（ $a, b$ の自由度が圧倒的に高いなど）それなりの事情がある．

次に， $a^{p - 1} mod p$ はわかるが, $a^{p - 1} mod p^{2}$ についてはほとんど何もわからない． $p^{2} ∣ a^{p - 1} - 1$ なる素数 $p$ を「base $a$ の Wieferich素数」といい，各 $a$ に対して base $a$ の Wieferich素数が無限に存在するかも未解決である．すなわち，これについて議論するのも筋が悪いことが多い．

さらに， $\frac{a^{p} - 1}{a - 1}$ のような形が素数であるかどうかなども基本的にわからない．

そもそも，位数の議論は円分型の式（やそれに類するもの）に対して際立てて威力を発揮するものであるから，そうでない場合にはよく考える必要がある（もちろん，うまい式変形によって円分型に帰着できて解けるといった ad-hoc なパターンもある）．

演習問題

#33

判定中

$mod p$ における原始根は（ $p$ の倍数の差を除いて）いくつか．

#34

★★☆☆☆

JMO 2012 問3

$p$ を素数とする．以下の条件がすべての整数 $x$ について成り立つような正整数 $n$ をすべて求めよ：

$x^{n} - 1$ が $p$ で割り切れるならば， $p^{2}$ でも割り切れる．

#35

判定中

India TST 2019 Day1 問2

${a_{1}}^{2018} + a_{2}, {a_{2}}^{2018} + a_{3}, \dots, {a_{2018}}^{2018} + a_{1}$ がすべて $5$ べきとなるような正整数 $a_{1}, a_{2}, \dots, a_{2018}$ は存在しないことを示せ．

#36

★★★☆☆

BMO 2018 P4

$3 p^{q - 1} + 1$ が $11^{p} + 17^{p}$ を割り切るような素数の組 $(p, q)$ をすべて求めよ．

#37

判定中

素数 $p \geq 5$ に対して，以下をみたす $p - 2$ 以下の正整数 $a$ が存在することを示せ： $p^{2} ∤ a^{p - 1} - 1, p^{2} ∤ (a + 1)^{p - 1} - 1.$

#38

判定中

$n$ を $2$ 以上の整数とする．任意の素数 $p$ に対して， $\frac{p^{n} + 1}{p + 1}$ は $n^{2}$ で割り切れないことを証明せよ．

#39

判定中

$\frac{5^{3 p q} - 1}{(p^{2} + 10) (3^{q} - 8)}$ が整数となるような素数の組 $(p, q)$ をすべて求めよ．

#40

★★★★★

kkkaaa氏による

正整数 $a, b, c$ に対して， $| 2021^{a} - 20^{b} - 21^{c} |$ のとりうる最小値を求め，それを実現する組 $(a, b, c)$ をすべて求めよ．

#41

判定中

IMO 2005 問4

数列 $a_{1}, a_{2}, \dots$ を $a_{n} = 2^{n} + 3^{n} + 6^{n} - 1 (n = 1, 2, \dots)$ で定めたとき，この数列のどの項とも互いに素であるような正整数をすべて求めよ．

#42

判定中

IMO 2011 SLP N8

$k$ を正整数とし， $n = 2^{k} + 1$ としたとき，次の $2$ 条件が同値であることを示せ：

$n$ は素数である．
$1, 2, \dots, n - 1$ の並べ替え $a_{1}, a_{2}, \dots, a_{n - 1}$ と，整数列 $g_{1}, g_{2}, \dots, g_{n - 1}$ が存在して，任意の $i = 1, 2, \dots, n - 1$ に対して $n ∣ {g_{i}}^{a_{i}} - a_{i + 1}$ が成立する．ここで $a_{n} = a_{1}$ とする．

#43

判定中

ガウスの予備補題

$p$ を奇素数とし， $a$ を $p$ で割り切れない整数とする． $a i$ を $p$ で割った余りが $\frac{p + 1}{2}$ 以下ならば $f (i) = 1$ とし，そうでないならば $f (i) = - 1$ とするとき， $χ_{2} (p, a) = \prod_{i = 1}^{\frac{p - 1}{2}} f (i)$ を示せ．

#44

判定中

$a, b$ を互いに素な正整数とし， $m, n$ を非負整数とするとき，以下を示せ： $gcd (a^{m} - b^{m}, a^{n} - b^{n}) = | a^{gcd (m, n)} - b^{gcd (m, n)} | .$

参考.　 $+$ の一部，または全部を $-$ に変えた問題についてはどうか？

#45

判定中

$n$ を $2$ 以上の整数とするとき， $a_1\mid2^{a_2}-1, ~ a_2\mid2^{a_3}-1,~~\ldots,~~ a_n\mid2^{a_1}-1 $をみたす正の整数の組$ (a_1,\ldots,a_n)$ をすべて求めよ．

#46

★★★☆☆

Croatia TST 2016

$10^{9}$ より大きい素数 $p$ について， $4 p + 1$ も素数であるとき， $(4 p + 1)^{- 1}$ を十進小数展開すると，小数点以下の桁には $0, 1, \dots, 9$ がすべて現れることを示せ．

参考文献

Aditya Khurmi: “Modern Olympiad Number Theory”
小林一章・鈴木晋一（監訳），清水俊宏・西本将樹（訳）：『数論の精選104問』，朝倉書店，2010
フェルマーの小定理の証明と例題（高校数学の美しい物語）
フェルマーの小定理（Wikipedia）
Zsigmondyの定理（INTEGERS）
斎藤秀司：『整数論』，共立出版，1997
Lower bound for cyclotomic polynomials evaluated at an integer（MathStackExchange）