素数に関するオイラーの定理

素数に関するオイラーの定理
奇素数 p に関してp ≡ 1 ( mod 4 ) と

x2 ≡ -1 (mod p) が解を持つこととは同値である。

証明)

q = (p-1)/2 とおく。

『p ≡ 1 ( mod 4 ) ⇒ x2 ≡ -1 (mod p) が解を持つ』 の証明

p ≡ 1 ( mod 4 ) より q は偶数。

(p-1)! ≡ 1・2・3・ … ・(q-2)・(q-1)・q・(q+1)・(q+2)・ … ・(p-2)・(p-1) (mod p)

≡ 1・2・3・ … ・(q-2)・(q-1)・q・(q+1-p)・(q+2-p)・ … ・(q-2-p)・(p-1-p) (mod p)

≡ 1・2・3・ … ・(q-2)・(q-1)・q・(-q)・(-q+1)・(-q+2)・ … ・(-2)・(-1) (mod p)

≡ q!・q!・(-1)q (mod p)

ここで q は偶数なので

(-1)q = 1

∴(p-1)! ≡ q!・q! (mod p)

ウィルソンの定理より

(p-1)! ≡ -1 (mod p)

なので q! = x とおくと

(p-1)! ≡ x2 ≡ -1 (mod p)

よって

p ≡ 1 ( mod 4 ) ⇒ x2 ≡ -1 (mod p) は解を持つ。

『x2 ≡ -1 (mod p) が解を持つ ⇒ p ≡ 1 ( mod 4 )』 の証明

x2 ≡ -1 (mod p) は解を持つなら

xp-1 ≡ (x2)q ≡ (-1)q (mod p)

フェルマーの小定理より

xp-1 ≡ 1 (mod p)

なので

1 ≡ (-1)q (mod p)

ここで

1 - (-1)q

は q が奇数なら0で、偶数なら2になる。

しかし p は奇数なので q は0にしかなり得ない。

したがって

(-1)q = 1

q ≡ 0(mod 2)

p-1 ≡ 0(mod 4)

証明終

 素数に関するオイラーの定理