フェルマーの小定理
1640年にフェルマー(Pierre de Fermat 1601-1665)によって示された定理で、非常に有用なものです。
|
フェルマーの小定理
|
|
p が素数で a が p の倍数でなければ ap-1 ≡ 1(mod p) |
（証明）
例えば
12 = 5(mod 7)
である。さらに
12×1 ≡ 5(mod 7)
12×2 ≡ 3(mod 7)
12×3 ≡ 1(mod 7)
12×4 ≡ 6(mod 7)
12×5 ≡ 4(mod 7)
12×6 ≡ 2(mod 7)
これらを辺々かけあわせると
12(7-1) × 6! ≡ 6!(mod 7)
となります。同様に
a × 1 ≡ m1(mod p)
a × 2 ≡ m2(mod p)
a × 3 ≡ m3(mod p)
↓
a × (p-1) ≡ m(p-1)(mod p)
これらを辺々かけあわせると
a(p-1) ×(p-1)! ≡ (p-1)! (mod p)
ここで p は素数なので p と (p-1)! は互いに素である。
a(p-1) ≡ 1 (mod p)
（証明終）
