페르마의 소정리

$ p $가 소수일때, 임의의 정수 a에 대해서 $ a^p - a $는 p의 배수이다. 이를 모듈러 연산으로 표현하면 다음과 같다. 

 

$ a^p \equiv a \pmod p $

 

괄호 안의 의미는 양 변에 mod p 가 생략되었다는 뜻이다. 

예를 들어, a = 3 이고 p = 7이면 $ 3^7 = 2187 - 3 = 2184 mod 7 = 0 $ 을 성립한다. 

 

만약 a가 p로 나누어지지 않으면, 양변을 a로 나누어 동치인 식을 만들 수 있다. 

 

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

 

위 성질을 이용해서 임의의 x에 대해서 다음과 같이 일반화할 수 있다. 

 

$ a^x \equiv a^{x \mod (p-1)} \pmod p $ 

 

이 성질을 이용해서 나머지를 매우 빠르고 쉽게 구할 수 있다. 

 

예제

 

www.acmicpc.net/problem/13172

13172번: Σ

 

 

 

 

 

Reference

위키피디아