フェルマーの小定理の解説

フェルマーの小定理は数論の基本的な定理の一つで、素数の性質を利用して計算を簡単にするための重要な結果です。

フェルマーの小定理

フェルマーの小定理は次のように表されます：

\(p\) を素数とし、\(a\) を \(p\) で割り切れない整数とすると、次の式が成り立ちます：

\[a^{p-1} \equiv 1 \pmod{p}\]

さらに、一般形として：

\[a^p \equiv a \pmod{p}\]

具体例

例1: \(a = 2\)、\(p = 7\) の場合、\(2^{7-1} = 64\) を計算します：

• \[2^6 = 64\]
• 64 を 7 で割ると、64 は 7 × 9 = 63 の1つ余りです：
• \[64 \equiv 1 \pmod{7}\]

例2: \(a = 3\)、\(p = 11\) の場合、\(3^{11-1} = 3^{10}\) を計算します：

• \[3^{10} = 59049\]
• 59049 を 11 で割ると、59049 は 11 × 5368 + 1 です：
• \[59049 \equiv 1 \pmod{11}\]

フェルマーの小定理の応用

フェルマーの小定理は、特にモジュラー逆数を計算するときに役立ちます。

モジュラー逆数とは、ある数 \(a\) に対して、\(a \cdot b \equiv 1 \pmod{m}\) を満たす \(b\) のことです。

具体例

例: 7 の 13 におけるモジュラー逆数を求める：

• フェルマーの小定理によれば、\((a^{p-1} \equiv 1 \pmod{p})\) です：
• したがって、\(7^{12} \equiv 1 \pmod{13}\)
• 7 の逆数 \((b)\) は、\((7^{12-1} \equiv b \pmod{13})\) です：
• \[7^{11} \equiv b \pmod{13}\]
• 計算すると、\((7^{11} \mod 13) = b\) です。

練習問題

次の問題を解いて、フェルマーの小定理の理解を深めましょう：

1. \(a = 4\)、\(p = 13\) に対して、\(4^{13-1} \mod 13\) を計算しなさい。
2. \(a = 5\)、\(p = 17\) に対して、\(5^{16} \mod 17\) を計算しなさい。
3. \(a = 9\)、\(p = 19\) に対して、\(9^{18} \equiv 1 \pmod{19}\) であることを確認しなさい。