카마이클 수

위키백과 ― 우리 모두의 백과사전.

수론에서 카마이클 수(Carmichael number)는 합성수 n이 그보다 작고 n과 서로소인 임의의 b에 대해 합동식 bn − 1 ≡ 1 (mod n) 를 만족할 때, 그 n을 가리키는 용어이다. 카마이클 수가 만족하는 조건은 소수가 만족하는 페르마의 소정리로, 의사소수의 하나이다. 미국의 수학자 로버트 카마이클의 이름을 따 명명되었다.

카마이클 수가 중요한 이유는 페르마 소수 판별법이 잘못 작동하기 때문이다. 페르마 판별법은 어떤 수가 소수인지 아닌지 판별하는데, 카마이클 수는 소수가 아니지만 페르마 판별법으로는 소수로 판별된다. 따라서 페르마 판별법은 항상 올바르게 판별한다고 할 수 없다. 다만, 큰 수에서는 카마이클 수가 드물게 나타나므로 페르마 판별법이 판별을 잘못할 위험도 줄어든다.

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.