용어 목록 > 페르마의 소정리 (Fermat's Little Theorem)

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

쉽게 풀면

p가 소수이고 a가 p의 배수가 아니라면, a를 p-1번 곱한 값을 p로 나누면 나머지가 항상 1이 됩니다. 예를 들어 p가 7이고 a가 3이면 3의 6제곱인 729를 7로 나눈 나머지는 1입니다. 아주 큰 수의 거듭제곱 나머지를 직접 계산하지 않고도 알 수 있게 해 주는 규칙입니다.

왜 중요한가

거듭제곱의 지수를 작게 줄여 주기 때문에 모듈러 산술 계산의 핵심 도구이며, RSA 암호의 복호화가 올바르게 작동하는 근거이기도 합니다. 또한 큰 수가 소수인지 빠르게 걸러 내는 확률적 소수판정법의 출발점이 됩니다.

논문에서는 이렇게 쓰입니다

조금 더 깊게 보면

군론의 관점에서 보면 p로 나눈 나머지 중 0이 아닌 것들이 곱셈에 대해 크기 p-1의 군을 이루고, 라그랑주 정리에 의해 원소의 위수가 p-1을 나누므로 곧바로 따라 나옵니다. 법이 소수가 아닌 일반 상황으로 확장한 것이 오일러 정리이며, 지수 자리에 오일러 파이 함수 값이 들어갑니다. 역은 성립하지 않아 조건을 만족하면서도 합성수인 카마이클 수가 존재하며, 이 때문에 페르마 판정법만으로는 소수를 확정할 수 없습니다.

주의할 점

페르마의 마지막 정리와는 완전히 다른 정리입니다. 또 a가 p의 배수인 경우에는 나머지가 0이 되어 성립하지 않으므로, 서로소 조건을 빠뜨리면 안 됩니다.

관련 용어