페르마의 소정리(Fermat's Little Theorem)

*페르마의 소정리(Fermat's Little Theorem) 

-> 우선 페르마의 소정리를 활용하기 위해서는 기본적으로 모듈러 산술(연산)과 합동식에 대한 이해가 선행되어야 한다. 다음 포스팅을 참고하도록 하자. sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)

-> 페르마의 소정리는 특정한 상황에서 어떤 수의 나머지를 빠르게 구할 때 사용이 가능하다. 특정한 상황은 아래 정리를 참고하도록 하자.

페르마의 소정리

 쉽게 말해 a^(p - 1)과 1을 p로 나눈 나머지는 같다, 즉, a^(p - 1)의 나머지는 1이다라는 말이다.

-> 예를 들어, 97이라는 소수가 있고 5는 97의 배수가 아니기 때문에 5^(97 - 1) ≡ 1 (mod 97)이 성립한다는 것을 위 정리를 통해 알 수 있다. 여기에서 합동 관계의 거듭 제곱에 관련된 성질을 이용하면, 어마어마하게 큰 수의 나머지도 간단하게 구할 수 있는 경우가 존재함을 알 수 있게된다.