アットウィキロゴ
知識メモ
アットウィキロゴ
知識メモ
ページ一覧
p：素数、a：自然数のとき、
a^p \equiv a \mod p
特に、aとpが互いに素であるとき、
a^{p-1} \equiv 1 \mod p


（証明）
\forall x,y \in \mathbb{Z},

(x+y)^p
=x^p + \left(\sum_{r=1}^{p-1} \binom{p}{r} x^{p-r} y^r \right) + y^p
=x^p + y^p + \left(\sum_{r=1}^{p-1} \frac{p!}{r! (p-r)!} x^{p-r} y^r \right)
=x^p + y^p + pA \ \ \ \ \ (A \in \mathbb{Z})

なぜなら、
\frac{p!}{r! (p-r)!}
の分母にはpが含まれておらず、pは素数であるから、約分して自然数に直せば必ず約数にpを含むため。

よって、
\forall x,y \in \mathbb{Z}, \ (x+y)^p \equiv x^p + y^p \mod p

いま、x+y は整数になるので、さらに任意の整数 z をとれば
\{(x+y)+z\}^p \equiv (x+y)^p + z^p \equiv x^p + y^p + z^p \mod p

同様に、この操作をa回続ければ一般に
(x_1 + x_2 + ... + x_a)^p \equiv x_1^p + x_2^p + ... + x_a^p \mod p
を得る。全ての x_i を 1 とおけば
a^p \equiv a \mod p


また、このとき
a^p - a = a(a^{p-1} - 1) \equiv 0 \mod p
より
a \equiv 0 \mod p \ \ or \ \ a^{p-1} - 1 \equiv 0 \mod p
であり、aとpが互いに素であるならば前者は成立しないので、後者の
a^{p-1} - 1 \equiv 0 \mod p
が成立する事となる。

タグ：

代数学
「フェルマーの小定理」をウィキ内検索
最終更新：2012年08月09日 18:49