[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다.

 

$a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족하고,

만약 $p$가 소수이고, $a$와 $p$가 서로소이면 $a^{p-1}\equiv 1($mod $p)$를 만족한다.

 

수학적 귀납법을 이용하여 위의 식을 증명해보겠습니다.

먼저, $0\leq a\leq p-1$ 범위의 정수에서만 증명해도 충분합니다. 그 이유는 $a$를 $p$로 나눈 나머지는 항상 $0$보다 크거나 같고 $p-1$보다 작거나 같기 때문입니다.

 

1. $a = 0$일 때

 

$a$가 $0$인 경우에는 $0^{p} = 0\equiv 0(mod$ $p)$

 

2. $a = k$일 때 성립한다고 가정하고 $a = k+1$일 때

 

$a=k$일 때 성립한다고 가정했으므로, $k^{p}\equiv k(mod$ $p)$를 만족합니다.

이항 정리를 사용하여 $a = k + 1$일 때도 성립함을 증명합니다.

 

$(k+1)^{p}=\sum_{i=0}^{p}\binom{p}{i}k^{i}$

 

이때 이항 계수의 정의에 의해서

 

$\binom{p}{i} = \frac{p!}{(p-i)!i!}=\frac{p(p-1)\cdot \cdot \cdot(p-i+1)}{i(i-1)\cdot \cdot \cdot 1}$

 

이고, 위 식은 $1\leq i\leq p-1$일 때 $p$의 배수이므로 p로 나누면 없어지게 됩니다. 또한, $i$가 $0$ 또는 $p$이면 1입니다. 따라서,

 

$(k+1)^{p}\equiv \binom{p}{0}k^{0}+\binom{p}{p}k^{p} = k^{p}+1\equiv k+1($mod $p)$

 

$a=k+1$일 때도 성립함을 증명했습니다. 따라서,따라서, $a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족합니다.

 

$a$와 $p$가 서로소인 경우는 다음과 같이 유도할 수 있습니다.

 

$a^{p}\equiv a($mod $p)$이므로, $a^{p} - a = a(a^{p-1}-1)$은 $p$로 나누어 떨어집니다. 이때, $a$와 $p$가 서로소이므로 $a^{p-1}-1$은 $p$로 나누어 떨어집니다.

 

따라서, $a^{p - 1}\equiv 1($mod $p)$를 만족합니다.