반응형 오일러 정리 썸네일형 리스트형 PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈) [목차] 1. 페르마의 소정리 2. 오일러 정리 3. 활용 1) 이항 계수 nCr 빠르게 구하기 4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법 1. 페르마의 소정리 (Fermat's little theorem) 페르마의 소정리는 다음과 같다. "소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다. 증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다) 먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq.. 이전 1 다음