フェルマーの小定理を使いこなす！例題と応用で徹底理解
目次
フェルマーの小定理とは
フェルマーの小定理は、素数と合同式に関する非常に重要な定理で、次のように表されます：
素数 \( p \) と、\( p \) で割り切れない整数 \( a \) に対して、 \[ a^{p-1} \equiv 1 \pmod{p} \] が成り立ちます。
これは一見単純な式に見えますが、数論や暗号理論など、さまざまな分野で広く使われています。
フェルマーの小定理の基本的な使い方
フェルマーの小定理のポイントは、「素数で割った余り」に関する問題で威力を発揮することです。特に、非常に大きな累乗の計算を簡単にすることができます。
例えば、\( 7^{100} \bmod 13 \) のような問題は直接計算すると大変ですが、フェルマーの小定理を使えば一瞬で解けます。
基本例題
例題1：\( 3^{6} \bmod 7 \) を求めよ。
7は素数であり、3は7で割り切れないのでフェルマーの小定理が使えます。
フェルマーの小定理より、 \[ 3^{6} \equiv 1 \pmod{7} \] よって、答えは 1。
例題2：\( 5^{100} \bmod 13 \) を求めよ。
13は素数で、5は13で割り切れない。
フェルマーの小定理より、 \[ 5^{12} \equiv 1 \pmod{13} \] なので、\( 5^{100} \) を \( 12 \) で割った余りを使って変形します。
\( 100 \div 12 = 8 \) 余り 4 なので、 \[ 5^{100} = (5^{12})^8 \cdot 5^4 \equiv 1^8 \cdot 5^4 \equiv 5^4 \pmod{13} \] \[ 5^4 = 625,\quad 625 \bmod 13 = 625 – 13 \times 48 = 1 \] よって、答えは 1。
例題3：\( 2^{2023} \bmod 17 \) を求めよ。
17は素数、2は17で割り切れない。
\[ 2^{16} \equiv 1 \pmod{17} \] 2023を16で割ると、2023 ÷ 16 = 126 余り 7。 \[ 2^{2023} = (2^{16})^{126} \cdot 2^7 \equiv 1^{126} \cdot 2^7 = 2^7 \pmod{17} \] \[ 2^7 = 128,\quad 128 \bmod 17 = 128 – 17 \times 7 = 9 \] 答えは 9。応用問題
応用1：合同式による証明問題
次の命題を証明せよ：
\( p \) を素数とし、\( a \) が \( p \) の倍数でないとき、\( a^{p(p-1)} \equiv a^p \pmod{p^2} \)
これはフェルマーの小定理の拡張の一部であり、群論的なアプローチや二項定理を使って証明されますが、詳細な証明は大学範囲になるため、ここでは省略します。ただし、「\(\mod p^2\)」まで拡張して考えることが可能な場面もあるということを紹介します。
応用2：暗号理論との関連
RSA暗号では、フェルマーの小定理の類似として「オイラーの定理」が使われています。これは、
\[ a^{\phi(n)} \equiv 1 \pmod{n} \]ただし、\( n \) が任意の自然数で、\( a \) が \( n \) と互いに素のときに成り立ちます。 フェルマーの小定理はこのオイラーの定理の特別な場合（\( n \) が素数）です。
フェルマーの小定理の証明（簡略）
証明のアイディアは、\( a, 2a, 3a, \dots, (p-1)a \) を \( p \) で割った余りが、\( 1, 2, \dots, p-1 \) の順列になることを利用します。
積をとってみましょう： \[ a \cdot 2a \cdot 3a \cdots (p-1)a = a^{p-1} \cdot (1 \cdot 2 \cdot \dots \cdot (p-1)) \] 一方、 \[ 1a, 2a, \dots, (p-1)a \mod p \] は \( 1, 2, \dots, p-1 \) の順列になるので、積の余りは \[ a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p} \] よって、 \[ a^{p-1} \equiv 1 \pmod{p} \] が導かれます（ただし、\( (p-1)! \) は \( p \) と互いに素なので割り算可能）。
まとめ
- フェルマーの小定理は、素数と累乗計算に関わる非常に強力な道具。
- 特に「大きな指数を持つ数の合同式」問題に効果的。
- RSA暗号などの現代的な応用にもつながる重要な知識。
この定理の本質を理解することで、数論の面白さや奥深さを実感できるでしょう。
