フェルマーの小定理

ウィキペディア

フェルマーの小定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/22 05:13 UTC 版)

自然数の冪乗の和に関する定理の「フェルマーの大定理」あるいは「フェルマーの最終定理」とは異なります。

数論において、フェルマーの小定理（フェルマーのしょうていり、英: Fermat's little theorem）は、素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。

概要

${\displaystyle p}$

ウィキペディア小見出し辞書

フェルマーの小定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/02 16:08 UTC 版)

「ラグランジュの定理 (群論)」の記事における「フェルマーの小定理」の解説

フェルマーの小定理 ― p を素数とするとき、整数 x ∈ ℤ が p と互いに素ならば、x p - 1 ≡ 1 (mod p) となる。 証明 位数 p の巡回群 (ℤ/pℤ) の乗法群 (ℤ/pℤ)× = {1, 2, 3, … , p - 1} は位数 p - 1 の有限群になるから、(ℤ/pℤ)× の任意の元を a とすると、ラグランジュの定理の系(2) より、a p - 1 = 1 が成り立つ。したがって、a ∈ {1, 2, 3, …, p - 1} のとき a p - 1 - 1 が素数 p で割り切れるから、a p - 1 ≡ 1 (mod p) となる。よって、x ≡ a (mod p) のとき、x p - 1 ≡ a p - 1 (mod p) が成り立つので、x p - 1 ≡ 1 (mod p) を得る。 より一般に、合成数 n についても乗法群 (ℤ/nℤ)× を考えれば、オイラーの定理を導くこともできる。