[정수론] 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리
정수론 4대 정리: 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리 정수론 4대정리에 대해 간단히 정리한다. 자세한 내용이나 증명은 이후 포스팅 할 예정이다.여기서는 정리의 내용과 간단한 활용방법에 대해 알아본다.페르마의 소정리 (Fermat's little theorem)정수 $a$, 소수 $p$에 대하여 다음이 성립한다.\[ a^p \equiv p \pmod{p} \]$a$가 $p$로 나누어지지 않는 경우에(즉 $p \nmid a$, $\gcd(p, a)=1$) 다음이 성립한다.\[ a^{p-1} \equiv 1 \pmod{p} \] 역은 성립하지 않는다. 즉, 소수가 아닌 합성수 $p$인 경우에도 $a^{p-1} \equiv 1 \pmod{p}$인 경우가 존재한다.이런 $p$..
2024. 8. 6.
