페르마의 소정리 :: 증명하기

 페르마의 소정리는 합동식 관련 문제를 해결할 때,  자주 쓰이는 정리로 오일러 정리의 구체화라고 할 수 있습니다. 

특히, 정수론에서 필수적인 정리입니다.

---

 

▶ 정의

      $p$가 소수이고 $gcd(a,p) = 1$일 때,  $a^{p-1} \equiv 1 \pmod{p}$

 

 

★ 증명

  원소 $(p-1)$개의 유한 집합 $ R = \{a,2a,\cdots,(p-1)a\}$를 정의합니다.  (이를 $p$의 기약 잉여계라고도 합니다.)

 $a$와 $p$는 서로소이므로, 이 원소들은 $p$로 나눴을 때, 나머지는 $1$부터 $(p-1)$ 중에 있을 것입니다.

 만약, 나머지가 $1$부터 $(p-1)$ 까지 일대일 대응이라면

                              $\left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots , (p-1) \right\}$ 이 성립합니다.

 

  $\{a,2a,\cdots,(p-1)a\}$ 에서 임의의 서로 다른 두 원소 $ia$ 와 $ja$ 를 정의하겠습니다.

 이때, $ia$ 와 $ja$ 를 $p$로 나눈 나머지가 같다고 가정하면, $ia \equiv ja \pmod{p}$ 가 성립합니다.

 $a$ 와 $p$도 서로소 이므로 $a$를 소거하면  $i \equiv j \pmod{p}$ 도 성립하게 됩니다.

 이때, $i$ 와 $j$는 $0$보다 크고 $p$보다 작으므로 $i=j$가 된다. → $ia=ja$

 그런데, 위의 가정에서 '서로 다른' 두 원소 $ia$ 와 $ja$로 조건을 잡은 것에 모순이 생깁니다.

  ∴ 귀류법에 의해 유한 집합 $R$ 의 서로 다른 두 임의의 원소는  $p$로 나눈 나머지들과 일대일 대응이 됩니다.

  

 나머지는 모두 다르므로, $\left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\}$ 이$\pmod{p}$ 에 성립합니다.

$p$는 소수여서, $(p-1)!$과 서로소 이므로,

$(p-1)! a^{p-1} \equiv (p-1)! \pmod{p}$ 가 성립한다. 여기서, $(p-1)!$를 소거하면,

    ∴ $a^{p-1} \equiv 1 \pmod{p}$

 

                                                                                                                                             

      

 

---

방문해주셔서 감사합니다.