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

奇素数 p に関してp ≡ 1 ( mod 4 ) と

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

証明）

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

『p ≡ 1 ( mod 4 ) ⇒ x² ≡ -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)! ≡ x² ≡ -1 (mod p)

よって

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

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

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

x^p-1 ≡ (x²)^q ≡ (-1)^q (mod p)

x^p-1 ≡ 1 (mod p)

なので

1 ≡ (-1)^q (mod p)

ここで

1 - (-1)^q

は q が奇数なら０で、偶数なら２になる。

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

したがって

(-1)^q = 1

q ≡ 0(mod 2)

p-1 ≡ 0(mod 4)

証明終