정수론 #4-3 :: 윌슨 정리

Wilson’s Theorem

$\begin{gather*}(p-1)!\equiv -1 \mod p \end{gather*}$

 

ex)

$\begin{gather*}4!=4\cdot3\cdot2\cdot1\equiv-1\mod 5 \end{gather*}$

4 ≡ -1 mod 5

3 * 2 ≡ 1 mod 5 ⇒ inverse of mod 5

⇒ 4! ≡ -1 mod 5

 

---

 

증명

추측) 1, p-1을 제외한 나머지 곱은 서로 다른 둘씩 짝을 지어서 inverse를 만족.

⇒ 당연히 걔네는 self inverse가 아니다.

 

$\begin{gather*}x^2 ≡ 1 \mod p \end{gather*}$

 

그럼 위를 만족하는 self inverse는 1과 p-1뿐이다.를 증명하면 된다.

 

ex) 1^2 ≡ 1 mod 5, 4^2 = 16 ≡ 1 mod 5

$\begin{gather*}(x-1)(x+1) ≡ 0 \mod p \\ \Rightarrow p|(x-1)(x+1) \\ \Rightarrow p|(x-1), \ \ \ \ p|(x+1) \\ \therefore x ≡ 1, \ \ \ x≡ -1 \mod p \end{gather*}$

 

mod p에서 해는 최대 2개. (d차 다항식)

 

prime divisor property에 의하여 p|(x-1) or p|(x+1)이므로

self inverse는 실제로 1 혹은 p-1뿐이다.