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}×2^4 \equiv 1×16=16$．

　補足をしておく．この問題であれば，$a^p \equiv a$の形式を用いて解いても大差ない．実際，$2^{1000}=2^{997}×2^3 \equiv 2×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×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×103$である．
　法を$97$として，$2^{10000}=2^{96×104+16} \equiv 2^{16}=65536 \equiv 61$．
（なおこの計算は，$97$を法とすれば$100 \equiv 3$であることを利用して，$65536 \equiv 6×3^2+55×3+36$とすれば簡単に計算できる．）
　法を$103$として，$2^{10000}=2^{102×98+4} \equiv 2^4=16$．
　よって，方程式$97x+61=103y+16$の整数解を求めればよい．$\mod 97$を取れば$6y \equiv 45$となり，$2y \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 4x \iff 4x \equiv 1 \equiv 104$
となり，$x \equiv 26$である．

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

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

(1)の解答

　$(p-2)^{p-2} \equiv (-2)^{p-2} \equiv x$とする．両辺を$-2$倍することで
　$(-2)^{p-1} \equiv -2x$となり，フェルマーの小定理より$-2x \equiv 1$である．
　$p$は奇素数なので$1-p$は$2$で割り切れる．よって$x \equiv \dfrac{p-1}{2}$．
　

(2)の解答

　$\mod 107$とする．
　$2^{102} \equiv 2^{102}×108^2 =2^{106}×729 \equiv 87$．
　$3^{103} \equiv 3^{103}×108 =3^{106}×4 \equiv 4$．
　$5^{105} \equiv 5^{105}×215 = 5^{106}×43 \equiv 43$．
　よって$87+4+43 \equiv 27$．　
　

(3)のヒント

　実は(2)がちょっとしたヒントである．$2^{202}×3^{303}$を変形することができる．
　

(3)の解答

　$\mod 103$とする．
　$2^2×3^3=108 \equiv 5$であることを使えば，$2^{202}×3^{303}×5^{505}=108^{101}×5^{505} \equiv 5^{606}$である．
　$5^{606} \equiv x$の整数解を求めたい．両辺$5^6$倍してからフェルマーの小定理を適用すると，$5^6 x \equiv 1$となるが，$5^6$を$103$で割った余りを考えると$72x \equiv 1$である．
　以下，$72x \equiv 104, 9x \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$は素数でないことを示せ．

解答