フェルマーの小定理

フェルマーの小定理とは、フェルマーが証明しなかった定理である。

概要

p を素数とし、a を p と互いに素な整数とすると次の式が成り立つというもの。

a^p-1 ≡ 1 (mod p)

≡ (mod p)はpで割った時の余りが等しいという意味。この定理の逆は成り立たない、がそんなに気にするほどでもないので確率的素数判定に用いられている。

「小」定理があるなら「大」定理はどこ？ と思う人もいるかもしれない。大定理はフェルマーの最終定理のことで、これと区別するために小定理と呼ばれている。ちなみに最終定理よりも小定理のほうがいろいろと応用範囲が広く、素数や剰余を扱う問題では頻出の定理である。

このフェルマーの小定理を拡張したオイラーの定理、オイラーの定理をさらに拡張したカーマイケルの定理が存在する。

例題

2¹⁸⁴¹を19で割った余りを求めよ。

答え

2¹⁸⁴¹ ≡ 2⁵ ≡ 13 (mod 19)

関連項目

• 数学
• 素数
• 暗号
• フェルマー
• カーマイケル数
• RSA暗号