개발스토리

페르마 정리(Fermat Theorem) • 만약 p가 소수라면 a는 p에 의해 나누어지지 않는 양의 정수이면, 다음이 성립한다 a^(p-1) ≡ 1 mod p test • a=7, p= 19, 7^18 ≡ x mod 19, x=? • 7^2 = 49 ≡ 11 mod 19 • 7^4 = 121 ≡ 7 mod 19 • 7^8 = 49 ≡ 11 mod 19 • 7^16 = 121 ≡ 7 mod 19 • a^(p-1) = 7^18 = 7^16 * 7^2 ≡ 7*11 ≡ 1 mod 19 페르마 정리의 다른 유용한 형태 • 만약 p가 소수이고 a가 양의 정수라 a^p ≡ a mod p가 성립한다. • 예) a=3, p=5, 3^5 = 243 ≡ 3 mod 5 • 예) a=10, p=5, 10^5 = 100000 ..