OMC対策（N分野：フェルマーの小定理）

本記事の前提知識

　基本的な合同式が使えることを前提とする．より具体的には，この記事の問題1,2がある程度解ければ十分である．　

フェルマーの小定理（基本編）

　OMCにおいて，フェルマーの小定理は非常に重要である．OMCの仕様上，整数値しか解答として受け付けないためである．
　例えばある問いの答えが $2^{1000}$ であるとき，数学オリンピックや大学受験の問題であれば，そのまま解答できるだろう．しかしOMCではそうはいかない．OMCでは，例えば次のような問われ方をする．「求めた値を素数 $997$ で割った余りを解答してください．」
　つまりフェルマーの小定理を使えることは，OMCにおいてはスタートラインだと言っても過言ではない．
　では早速，その定理を紹介しよう．　

フェルマーの小定理

　素数 $p$ と， $p$ の倍数でない正整数 $a$ について， $a^{p - 1} \equiv 1 \mod p$ が成り立つ．

　フェルマーの小定理は，次のように表現されることも多い．

　素数 $p$ と整数 $a$ に対して， $a^{p} \equiv a \mod p$ が成り立つ．

　個人的にはこちらの方が簡潔で好みだが，定理1の表現の方が実用性は高い．
　実際に問題を解いてみよう．

　 $2^{1000}$ を $997$ で割った余りを求めよ．

（解）合同式は $\mod 997$ とする．
　フェルマーの小定理より $2^{996} \equiv 1$ であり， $2^{1000} = 2^{996} \times 2^{4} \equiv 1 \times 16 = 16$ ．

　補足をしておく．この問題であれば， $a^{p} \equiv a$ の形式を用いて解いても大差ない．実際， $2^{1000} = 2^{997} \times 2^{3} \equiv 2 \times 2^{3} = 16$ となる．
　しかし一般的には，定理1の表現（つまり $a^{p - 1} \equiv 1$ ）の方が使い勝手は良い．
　次の例題はどうだろう．

　 $2^{997^{k}}$ を $997$ で割った余りを求めよ．

　合同式は $\mod 997$ とする．
（解１： $a^{p} \equiv a$ を用いる）
　 $2^{997^{k}} = (2^{997})^{997^{k - 1}} \equiv 2^{997^{k - 1}}$ である． $k - 1$ 回同じことを繰り返すと， $2^{997^{k - 1}} \equiv 2$ であることがわかる．

（解２： $a^{p - 1} \equiv 1$ を用いる）
　 $997^{k}$ を $996$ で割った余りは $1$ である．よってある整数 $n$ が存在して $2^{997^{k}} = (2^{996})^{n} \times 2$ と表すことができ， $2^{997^{k}} \equiv 2$ である．

　解１はうまく工夫して解いているが，解２は単純に $996$ で割った余りを考えればよい．この問題であれば，解１でも上手に解けているが，「 $2^{997}$ を $2$ に置き換える」よりは「指数部分を $996$ で割る」ほうが，方針が明快だろう．
　勿論，状況に応じてどちらも使えることが望ましいが，基本的には解２が優ることが多い．練習問題を解いてみよう．

(1)　 $2^{102} + 3^{103} + 5^{105}$ を素数 $103$ で割った余りを求めよ．
(2)　素数 $p$ に対して $(p + 2)^{p + 2}$ を $p$ で割った余りを求めよ．
(3)　素数 $p ≧ 5$ に対して $(p - 3)^{(p - 2)^{p - 1}}$ を $p$ で割った余りを求めよ．
(4)　 $2^{10000}$ を $9991$ で割った余りを求めよ．（※ $9991$ は素数ではない．）

(1)のヒント

　フェルマーの小定理を適用して，

2^{102} \equiv a

，

3^{103} \equiv b

，

5^{105} \equiv c

となる数

a, b, c

をそれぞれ求めよう．
　

(1)の解答

　合同式は

\mod 103

とする．
　フェルマーの小定理より

2^{102} \equiv 1

，

3^{103} \equiv 3

，

5^{105} \equiv 5^{3} = 125

である．
　よって

2^{102} + 3^{103} + 5^{105} \equiv 1 + 3 + 125 \equiv 26

である．
　

(2)の解答

(p + 2)^{p + 2} \equiv 2^{p + 2} \equiv 2^{3} \mod p

である．
よって，

p = 2

のとき余り

0

，

p = 3

のとき余り

2

，

p = 5

のとき余り

3

，

p = 7

のとき余り

1

，

11

以上の素数

p

に対しては余り

8

である．
　

(3)のヒント

(p - 2)^{p - 1}

を

p - 1

で割った余りを求めたい．合同式の性質を活用しよう．　
　

(3)の解答

(p - 2)^{p - 1}

を

p - 1

で割った余りを求めたいが
　　

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

である（

5

以上の素数は奇素数なので

p - 1

は常に偶数）．
　よって求めるべき値は

(p - 3)^{1} = p - 3

である．
　

(4)のヒント

9991

を素因数分解して，それぞれの素因数

p

に対して

2^{10000}

を

p

で割った余りを求める．
　その後，連立合同式を解けばよい．（連立合同式の解き方がわからなければ，この問題は飛ばすのが吉である．）
　

(4)の解答

9991 = 100^{2} - 3^{2} = 97 \times 103

である．
　法を

97

として，

2^{10000} = 2^{96 \times 104 + 16} \equiv 2^{16} = 65536 \equiv 61

．
（なおこの計算は，

97

を法とすれば

100 \equiv 3

であることを利用して，

65536 \equiv 6 \times 3^{2} + 55 \times 3 + 36

とすれば簡単に計算できる．）
　法を

103

として，

2^{10000} = 2^{102 \times 98 + 4} \equiv 2^{4} = 16

．
　よって，方程式

97 x + 61 = 103 y + 16

の整数解を求めればよい．

\mod 97

を取れば

6 y \equiv 45

となり，

2 y \equiv 15 \equiv 112

と計算していけば

y = 56

を得る．よって

5784

が答えである．　
　

フェルマーの小定理（応用編その１）

　改めてフェルマーの小定理の式を見よう． $a^{p - 1} \equiv 1$ であった．
　この式からすると，指数が $p - 1$ 以上でなければフェルマーの小定理は適用できないように見えるが，実際はもう少しだけ応用が利く．例えば次の例題である．

　 $2^{100}$ を素数 $103$ で割った余りを求めよ．

　合同式は $\mod 103$ とする．
　 $2^{100} \equiv x$ となる整数 $x$ を求めたい．式 $2^{100} \equiv x$ の両辺を $4$ 倍すると
　　 $2^{102} \equiv 4 x ⟺ 4 x \equiv 1 \equiv 104$
となり， $x \equiv 26$ である．

　このように，合同式の性質をうまく活用することで，指数が $p - 1$ 未満の場合でも，フェルマーの小定理を活用することができる．なお，本解答は
　　 $2^{100} \equiv 2^{100} \times 104 = 2^{102} \times 26 \equiv 26$
と書くこともできる．あるいは，分数の合同式が使えるのであれば
　　 $2^{100} \equiv \frac{2^{100}}{2^{102}} = \frac{1}{4} \equiv \frac{104}{4} = 26$
と書くことも可能だが，これは上級者向けだろう．
　少しだけ練習問題を用意した．計算が面倒なものもあるが，合同式の扱いに慣れる練習だと思って取り組んでみてほしい．

(1)　素数 $p ≧ 3$ に対して $(p - 2)^{p - 2}$ を $p$ で割った余りを求めよ．
(2)　 $2^{102} + 3^{103} + 5^{105}$ を素数 $107$ で割った余りを求めよ．
(3)　 $2^{202} \times 3^{303} \times 5^{505}$ を素数 $103$ で割った余りを求めよ．

(1)の解答

(p - 2)^{p - 2} \equiv (- 2)^{p - 2} \equiv x

とする．両辺を

- 2

倍することで
　

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

となり，フェルマーの小定理より

- 2 x \equiv 1

である．
　

p

は奇素数なので

1 - p

は

2

で割り切れる．よって

x \equiv \frac{p - 1}{2}

．
　

(2)の解答

\mod 107

とする．
　

2^{102} \equiv 2^{102} \times 108^{2} = 2^{106} \times 729 \equiv 87

．
　

3^{103} \equiv 3^{103} \times 108 = 3^{106} \times 4 \equiv 4

．
　

5^{105} \equiv 5^{105} \times 215 = 5^{106} \times 43 \equiv 43

．
　よって

87 + 4 + 43 \equiv 27

．　
　

(3)のヒント

　実は(2)がちょっとしたヒントである．

2^{202} \times 3^{303}

を変形することができる．
　

(3)の解答

\mod 103

とする．
　

2^{2} \times 3^{3} = 108 \equiv 5

であることを使えば，

2^{202} \times 3^{303} \times 5^{505} = 108^{101} \times 5^{505} \equiv 5^{606}

である．
　

5^{606} \equiv x

の整数解を求めたい．両辺

5^{6}

倍してからフェルマーの小定理を適用すると，

5^{6} x \equiv 1

となるが，

5^{6}

を

103

で割った余りを考えると

72 x \equiv 1

である．
　以下，

72 x \equiv 104, 9 x \equiv 13 \equiv - 90, x \equiv - 10 \equiv 93

と変形していけばよい．答えは

93

である．
　

フェルマーの小定理（応用編その２）

　OMC対策としては不要かもしれないが，証明問題の対策についても書いておこう．
　次の問題は，フェルマーの小定理を適用して解くこともできる．

京都大(2021)

　 $p$ が素数ならば， $p^{4} + 14$ は素数でないことを示せ．

解答

p \neq 5

のとき，

p^{4} + 14 \equiv 1 + 14 \mod 5

より，

p^{4} + 14

は

5

で割り切れる．

p^{4} + 14

は明らかに

5

より大きいので素数でない．
　

p = 5

のときは，

5^{4} + 14 = 639

．これは

3

で割り切れるので素数でない．
　

　フェルマーの小定理を大学受験で使ってよいのかについては諸説ある．実際，上の問題であれば $\mod 3$ で場合分けするだけで解けるのだから，フェルマーの小定理を持ち出すのは少し大げさな感じがする．
　受験する大学のレベルにもよるから，一概には言えないかもしれないが，一般論として，フェルマーの小定理はあまり使わない方がよいだろう．（もしくは，フェルマーの小定理の証明を覚えておいて，それをきちんと記述するという裏技もあり得る．）
　ほぼ同じ方針ではあるが，類題を用意した．

　 $p$ が素数ならば， $p^{22} - 24$ は素数でないことを示せ．

解答

p \neq 23

のとき，

p^{22} - 24 \equiv 1 - 24 \mod 23

より，

p^{22} - 24

は

23

で割り切れる．
　

p = 23

のときは，

23^{22} - 24

が

5

で割り切れるため素数でない（確かめよ）．
　

　もう一題，フェルマーの小定理を利用した超有名問題がある．
　そちらを練習問題として後に残し，先に，自作の類題を見ていただこう．

　任意の素数 $p$ に対して，次の条件を満たすある正整数 $n ≧ 3$ が存在することを示せ．
（条件） $3^{n} + 4^{n} - 25$ は $p$ の倍数である．

ヒント

　任意の素数

p

に対して，

3^{n} + 4^{n} - 25 \equiv 0

となるような正整数

n

が存在するということである．
　　

解答

n = p + 1

のときを考えると，

p

を法として

3^{p + 1} + 4^{p + 1} - 25 \equiv 3^{2} + 4^{2} - 25 \equiv 0

である．つまり

3^{p + 1} + 4^{p + 1} - 25

は

p

の倍数である．
　

　次の問題が，先ほど書いた「超有名問題」である．解答はインターネット上に（動画も含め）いくらでも存在するので，わからなければ各自で調べてほしい．

IMO(2005)

　数列 $a_{1}, a_{2}, \dots$ を
　　 $a_{n} = 2^{n} + 3^{n} + 6^{n} - 1$
で定める．この数列のどの項とも互いに素であるような自然数をすべて決定せよ．

　最後にOMCの例題を載せておく．

OMCの例題

OMC185(B)
OMC101(E)

投稿日：4月4日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

て

1009

他の人のコメント

コメントはありません。

読み込み中

て

OMC対策（N分野：フェルマーの小定理）

本記事の前提知識
フェルマーの小定理（基本編）
フェルマーの小定理（応用編その１）
フェルマーの小定理（応用編その２）