基本的な合同式が使えることを前提とする.より具体的には, この記事 の問題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$とする.
(解1:$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$であることがわかる.
(解2:$a^{p-1} \equiv 1$を用いる)
$997^k$を$996$で割った余りは$1$である.よってある整数$n$が存在して$2^{997^k} =(2^{996})^n×2$と表すことができ,$2^{997^k} \equiv 2$である.
解1はうまく工夫して解いているが,解2は単純に$996$で割った余りを考えればよい.この問題であれば,解1でも上手に解けているが,「$2^{997}$を$2$に置き換える」よりは「指数部分を$996$で割る」ほうが,方針が明快だろう.
勿論,状況に応じてどちらも使えることが望ましいが,基本的には解2が優ることが多い.練習問題を解いてみよう.
(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$は素数ではない.)
改めてフェルマーの小定理の式を見よう.$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$で割った余りを求めよ.
OMC対策としては不要かもしれないが,証明問題の対策についても書いておこう.
次の問題は,フェルマーの小定理を適用して解くこともできる.
$p$が素数ならば,$p^4+14$は素数でないことを示せ.
フェルマーの小定理を大学受験で使ってよいのかについては諸説ある.実際,上の問題であれば$\mod 3$で場合分けするだけで解けるのだから,フェルマーの小定理を持ち出すのは少し大げさな感じがする.
受験する大学のレベルにもよるから,一概には言えないかもしれないが,一般論として,フェルマーの小定理はあまり使わない方がよいだろう.(もしくは,フェルマーの小定理の証明を覚えておいて,それをきちんと記述するという裏技もあり得る.)
ほぼ同じ方針ではあるが,類題を用意した.
$p$が素数ならば,$p^{22}-24$は素数でないことを示せ.
もう一題,フェルマーの小定理を利用した超有名問題がある.
そちらを練習問題として後に残し,先に,自作の類題を見ていただこう.
任意の素数$p$に対して,次の条件を満たすある正整数$n≧3$が存在することを示せ.
(条件)$3^n+4^n-25$は$p$の倍数である.
次の問題が,先ほど書いた「超有名問題」である.解答はインターネット上に(動画も含め)いくらでも存在するので,わからなければ各自で調べてほしい.
数列$a_1, a_2, \cdots$を
$a_n=2^n+3^n+6^n-1$
で定める.この数列のどの項とも互いに素であるような自然数をすべて決定せよ.
最後にOMCの例題を載せておく.