原始根を使ったウィルソンの定理の証明の意味がわかった…^^

ウィルソンの定理のエレガントな証明はすでにアップしてますが…

Wikiに載ってる証明が簡単ですね ☆

原始根に慣れて来てやっとわかったり♪

*彼が最初に証明されたようですけど…

どうやってされたのか我知らず…^^;

https://ja.wikipedia.org/wiki/ウィルソンの定理より Orz～

「ウィルソンの定理は初等整数論における素数に関する次のような定理である。

p が素数ならば (p-1)! ≡ -1 (mod p) が成り立つ。p>1の場合、逆も成り立つ。

p が大きくなるにつれて計算量が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。

証明

p = 2 の場合は成り立つので、以下pは奇素数とする。

pは素数だから法pに関する原始根aが存在する。このとき、フェルマーの小定理より、

a^{p-1} \equiv 1 \pmod{p}.

aは原始根だから、a¹, a², … ,a^p-1(≡1)はそれぞれpを法として還元すると、1, 2, … ,p-1の並べ替えである。よって、

a^1 a^2 ... a^{p-1} \equiv (p-1)! \pmod{p}

となる。一方、

a^1 a^2 ... a^{p-1} = a^{1+2+...+(p-1)} = a^{p(p-1)/2}

が成り立つ。

b=a^p(p-1)/2とおくと、b² ≡ 1 (mod p) だからb ≡ ±1 (mod p) である。

示したいのはb ≡ -1 (mod p) なのでb ≡ 1 (mod p) と仮定して矛盾を導く。

aは原始根だから、フェルマーの小定理より、p(p-1)/2はp-1で割り切れる。

ゆえにp/2は整数となるが、これはpが奇数であることに反する。Q.E.D.」

これよりも、以下のサイトのものの方がわかり易いですね♪

*原始根の定義が r^(p-1)≡1　mod p

・・・p-1乗で初めてこれを満たす数が原始根 r

= 原始根 rは、p-1が最小の乗数になる数なので...

r^m≡1 なら、mはp-1の倍数なのね ^^

*ルジャンドルさんが証明した方法も見つけたのでまたいずれ ^^

アットランダム≒ブリコラージュ