페르마의 소정리

너무나도 유명한 페르마의 마지막 정리에 기가 눌려서 그렇지 이쪽도 나름 유명한 정리이다. 1640년에 처음으로 발표되었다. 근데 증명을 안 해 놓은 건 똑같다. 아니 페르마의 성격상 정리 해 놓고 공개 안 한 걸지도 모른다 카더라. 원고 형식의 증명은 1683년경 빌헬름 라이프니츠에 의해서, 출판 형식의 증명은 1736년 레온하르트 오일러에 의해서 증명되었다. 정리의 내용은 다음과 같다.

소수 $p$와 양의 정수 $a$에 대해 $\gcd \left(a,p\right)=1$ 이면 $a^{p-1}\equiv 1{\pmod {p}}$

증명

집합 $A=\left\{a,2a,3a,\cdots ,\left(p-1\right)a\right\}$을 생각하자. 먼저, 각 원소는 $p$로 나누어 떨어지지 않는다. 만약 적당한 정수 $1\leq k\leq p-1$에 대해 $p\mid ka$이면, $p\not \mid a$이므로 $p\mid k$인데, 이는 모순이다. 또한, 어느 두 원소도 법 $p$에 대해 동일하지 않다. 만약 $ia\equiv ja{\pmod {p}}$이면, $\gcd \left(p,a\right)=1$이므로 $i\equiv j{\pmod {p}}$이고, $1\leq i,\,j\leq p-1$이므로 $i=j$이어야만 한다. 따라서, 집합 $A$는 법 $p$에 대한 완전잉여계이다. 이는 곧 $A\equiv \left\{1,2,3,\cdots ,p-1\right\}$임을 의미한다 (순서까지 같을 필요는 없다). 따라서, $a\cdot 2a\cdot \cdots \cdot \left(p-1\right)a\equiv 1\cdot 2\cdot \cdots \cdot \left(p-1\right)\equiv \left(p-1\right)!{\pmod {p}}$이고, 정리하면 $a^{p-1}\left(p-1\right)!\equiv \left(p-1\right)!{\pmod {p}}$이다. 윌슨의 정리에 의해 $-a^{p-1}\equiv -1{\pmod {p}}$이고, 곧 $a^{p-1}\equiv 1{\pmod {p}}$이다.
페르마 소정리는 매우 다양한 방법으로 증명이 가능하다. 기약잉여계를 이용한 방법 뿐만아니라 합동식, 순환소수의 성질을 이용하여도 증명이 가능하다.

따름 정리

$p$가 소수이고 $a$가 양의 정수이면, $a^{p}\equiv a{\pmod {p}}$가 성립한다.

증명은 매우 간단한데, $p\mid a$이면 좌·우변 다 0이므로 동일, $p\not \mid a$이면 위 페르마의 소정리에 의해 바로 유도된다.

$p$가 소수이고 $a$가 $p\not \mid a$인 양의 정수이면, ${\bar {a}}\equiv a^{p-2}{\pmod {p}}$이다 (${\bar {a}}$는 $a$의 법 $p$에 관한 역수).

역시 페르마의 소정리에 의해 바로 유도된다.

일반화

페르마의 소정리를 일반화 시킨 것이 바로 오일러의 정리이다. 자세한 것은 항목 참조.