카르마이클 수(Carmichael number)란 무엇인가?

수학에서 카르마이클 수(Carmichael number)는 소수가 아님에도 페르마의 소정리를 만족하는 매우 특이한 합성수입니다. 이러한 특성 때문에, 카르마이클 수는 소수 판별 과정에서 착각을 일으킬 수 있는 위험한 수로 잘 알려져 있습니다. 이번 글에서는 카르마이클 수의 정의, 역사적 배경, 수학적 성질, 그리고 몇 가지 예제를 통해 개념을 자세히 살펴보겠습니다.

카르마이클 수의 정의

카르마이클 수는 다음 조건을 만족하는 합성수 \(n\)을 의미합니다.

임의의 정수 \(a\)가 \(n\)과 서로소일 때, 다음이 성립합니다.

\[ a^{n-1} \equiv 1 \pmod{n} \]

이는 소수에 대해서 성립하는 페르마의 소정리를 그대로 따르는 성질입니다. 그러나, 카르마이클 수는 소수가 아닌 합성수이므로 매우 예외적인 존재라고 할 수 있습니다.

카르마이클 수의 역사적 배경

카르마이클 수는 1910년, 수학자 로버트 카르마이클(Robert Carmichael)에 의해 발견되었습니다. 소수 판별법 중 하나인 '페르마 테스트'는 어떤 수가 소수인지를 빠르게 판별하기 위해 널리 사용되었는데, 카르마이클 수는 이 테스트를 무력화하는 대표적인 반례로 유명합니다.

카르마이클 수의 성질

1. 합성수임에도 페르마의 소정리를 만족

페르마의 소정리는 원래 소수에 대해서만 성립하는 정리입니다. 즉, 소수 \(p\)에 대하여, \(a\)가 \(p\)와 서로소라면 다음이 성립합니다.

\[ a^{p-1} \equiv 1 \pmod{p} \]

그런데 카르마이클 수는 소수가 아님에도 불구하고 모든 서로소 정수 \(a\)에 대해 위 조건을 만족합니다.

2. 최소 3개의 서로 다른 소인수로 구성

모든 카르마이클 수는 최소한 3개의 서로 다른 소인수를 가집니다. 예를 들어, 가장 작은 카르마이클 수는 561이며, 이는 다음과 같이 인수분해할 수 있습니다.

\[ 561 = 3 \times 11 \times 17 \]

3. 각 소인수 \(p\)에 대해 조건 만족

카르마이클 수 \(n\)의 모든 소인수 \(p\)에 대해 다음이 성립해야 합니다.

\[ p-1 \mid n-1 \]

이 성질은 카르마이클 수의 생성 과정에서도 중요한 역할을 합니다.

카르마이클 수의 예제

가장 작은 카르마이클 수: 561

561은 다음과 같이 인수분해됩니다.

\[ 561 = 3 \times 11 \times 17 \]

각 소인수에 대해 확인해 보면 다음과 같습니다.

\(3-1 = 2\), \(11-1 = 10\), \(17-1 = 16\)
561-1 = 560은 2, 10, 16 모두로 나누어 떨어집니다. 따라서 561은 카르마이클 수입니다.

다른 대표적인 카르마이클 수

다음은 대표적인 작은 카르마이클 수 목록입니다.

561, 1105, 1729, 2465, 2821, 6601

이들은 모두 합성수이지만, 페르마의 소정리를 만족합니다.

카르마이클 수와 소수 판별법의 관계

카르마이클 수는 페르마 소수 판별법(Fermat Primality Test)의 허점을 드러내는 대표적인 예입니다. 페르마 테스트는 주어진 수 \(n\)에 대하여 다음을 검사합니다.

\[ a^{n-1} \equiv 1 \pmod{n} \]

모든 서로소 \(a\)에 대해 위 조건을 만족하면 소수로 판정하는 방식인데, 카르마이클 수는 합성수임에도 이를 만족하기 때문에 오류를 발생시킵니다.

현대 수론에서의 카르마이클 수

현대 수론에서는 페르마 테스트 대신 밀러-라빈 테스트(Miller-Rabin Test)와 같은 확률적 소수 판별법이 더 많이 사용됩니다. 이러한 테스트는 카르마이클 수와 같은 특이한 수를 더욱 정교하게 걸러내는 알고리즘을 포함하고 있습니다.

결론

카르마이클 수는 소수가 아님에도 불구하고 페르마의 소정리를 만족하는 특이한 합성수입니다. 이는 소수 판별법에서 허점을 노출시키는 대표적인 사례로, 수학적으로도 매우 흥미로운 대상입니다.

카르마이클 수는 최소 3개의 서로 다른 소인수를 가지며, 각 소인수에 대해 \(p-1\)이 \(n-1\)의 약수가 되는 성질을 만족합니다. 가장 작은 카르마이클 수는 561이며, 수론 연구에서 자주 등장하는 수입니다.

현대 수론에서는 보다 강력한 소수 판별법을 통해 카르마이클 수를 효과적으로 걸러내고 있지만, 이들의 존재는 여전히 수학적 호기심과 연구 대상이 되고 있습니다.

결국, 카르마이클 수는 단순한 수학적 특이 현상을 넘어, 수론의 깊이를 탐구하는 데 중요한 실마리를 제공하는 특별한 숫자들입니다.