フェルマーの小定理と定義・具体例・証明・例題について
1. フェルマーの小定理とは
\[ a^{p-1} \equiv 1 \pmod{p} \]
つまり、整数 \( a \) を素数 \( p \) で割った余りを考えたとき、\( a \) を \( p-1 \) 乗した結果の余りは常に 1 になります。
1.1. 具体例
例えば、素数 \( p = 7 \) と整数 \( a = 3 \) を考えると、
\[ 3^6 \equiv 1 \pmod{7} \]
実際に計算すると、
\[ 3^6 = 729 \]
729 を 7 で割った余りは 1 となります。このように、フェルマーの小定理が成り立つことが確認できます。
2. フェルマーの小定理の証明
2.1. 証明1（数学的帰納法を利用した証明）
フェルマーの小定理の証明に先立って、まず次の補題を示します。
\[ a^p \equiv a \ (\text{mod} \ p) \]
この補題を数学的帰納法により示します。
\( a = 1 \) のとき、明らかに \( 1^p = 1 \) です。したがって、\( 1^p \equiv 1 \ (\text{mod} \ p) \) が成り立ちます。
ある任意の整数 \( m \) に対して \( m^p \equiv m \ (\text{mod} \ p) \) が成り立つと仮定します。
次に、\( m + 1 \) のとき、\( (m + 1)^p \) について考える。
二項定理を用いると、次のように展開できます。
\[ (m + 1)^p = m^p + \binom{p}{1}m^{p-1} + \binom{p}{2}m^{p-2} + \dots + \binom{p}{p-1}m + 1 \]
ここで、\(\binom{p}{k}\) は二項係数であり、\( p \) は素数であるため、\( k = 1, 2, \dots, p-1 \) について二項係数は \( p \) で割り切れます。したがって、次の式が成り立ちます。
\[ (m + 1)^p \equiv m^p + 1 \ (\text{mod} \ p) \]
さらに、仮定より \( m^p \equiv m \ (\text{mod} \ p) \) が成り立つので、
\[ (m + 1)^p \equiv m + 1 \ (\text{mod} \ p) \]
よって、補題はm+1の時も成り立つ。
したがって、数学的帰納法より、任意の正の整数 \( a \) に対して
\[ a^p \equiv a \ (\text{mod} \ p) \]
が成り立つことが示された。
今、\( p \) と \( a \) が互いに素であると仮定します。このとき、補題から \( a^p \equiv a \ (\text{mod} \ p) \) が成り立ちます。\( a \) が \( p \) と互いに素であるため、両辺を \( a \) で割ることができます。
\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]
これでフェルマーの小定理が証明されました。
2.2. 証明2（割った余りが異なることを利用）
フェルマーの小定理の証明に先立って、まず次の性質を示します。
次に、\( a, 2a, \dots, (p-1)a \) を \( p \) で割った余りを考えます。各 \( ka \) の \( p \) での余りを \( r_k \) とします。すなわち、\( r_k = ka \ (\text{mod} \ p) \) です。
このとき、もし \( r_i = r_j \) （ただし \( i \neq j \)）が成り立つと仮定するなら、次のようになります。
\[ ia \equiv ja \ (\text{mod} \ p) \]
両辺から \( ja \) を引くと、
\[ (i-j)a \equiv 0 \ (\text{mod} \ p) \]
\( p \) と \( a \) は互いに素なので、\( (i-j) \) が \( p \) で割り切れなければなりません。しかし、\( 1 \leq i, j \leq p-1 \) なので、\( i-j \) は \( p \) の倍数ではない。\( i = j \) となり、これは仮定に反します。したがって、全ての \( r_k \) は異なる余りを持ちます。
\( r_1, r_2, \dots, r_{p-1} \) は異なる余りを持つため、 \( 1, 2, \dots, p-1 \) のどれかに等しくなります。これにより、
\[ a \cdot 2a \cdot \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot \dots \cdot (p-1) \ (\text{mod} \ p) \]
左辺は、
\[ a^{p-1} \cdot (p-1)! \equiv (p-1)! \ (\text{mod} \ p) \]
となります。ここで、\( (p-1)! \) は \( p \) と互いに素（\( p \) は素数）なので、両辺を \( (p-1)! \) で割ることができ、
\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]
が成り立ち、これでフェルマーの小定理が証明されました。
3. 例題
3.1. 例題 1（計算問題）
\[ 3^{10} (\text{mod} \ 7) \]
フェルマーの小定理により、 \( 3^6 \equiv 1 (\text{mod} \ 7) \) であるので
$$ 3^{10} \equiv 3^6 \times 3^4 \equiv 1 \times 3^4 (\text{mod} \ 7) $$
したがって、$3^4$を計算すると、
$$3^4 \equiv3^2\times 3^2 \equiv 2\times 2 \equiv 4 (\text{mod} \ 7) $$
最終的に、\( 3^{10} (\text{mod} \ 7) = 4 \) です。
3.2. 例題 2（計算問題）
\[ 5^{15} (\text{mod} \ 11) \]
フェルマーの小定理により、 \( 5^{10} \equiv 1 (\text{mod} \ 11) \) であるため、
$$5^{15} = 5^{10} \times 5^5 \equiv 1 \times 5^5 (\text{mod} \ 11) $$
したがって、$5^5$を計算すると、
$$ 5^5 \equiv 5^3 \times 5^2 \equiv 4 \times 3 \equiv 1(\text{mod} \ 11) $$
したがって、\( 5^{15}(\text{mod} \ 11) = 1 \) です。
