자료구조 & 알고리즘/수학1 페르마의 소정리 $ 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 $ 이 성질을 이용해서 나머지를 매우 빠르고 쉽게 구할 수 있다. 예제 ww.. 2020. 9. 20. 이전 1 다음
