쿨렌 수

3. 쿨렌 소수

쿨렌 소수는 소수인 쿨렌 수를 말한다.^[1] 쿨렌 소수는 무한히 많을 것으로 예상되지만, 아직 증명되지 않았다.^[1]

1976년 크리스토퍼 훌리는 ''C''_''n''이 소수인 양의 정수 $n\; \backslash leq\; x$의 자연 밀도가 $x\; \backslash to\; \backslash infty$일 때 o(''x'')의 차수임을 보였다. 그런 의미에서 거의 모든 쿨렌 수는 합성수이다.^[1]

쿨렌 수 ''C''_''n''은 ''p''가 8''k'' − 3 형태의 소수일 경우 ''p'' = 2''n'' − 1로 나누어 떨어지며, 또한 페르마의 소정리에 따라 ''p''가 홀수 소수이면, ''p''는 각 ''m''(''k'') = (2^''k'' − ''k'') 

 (''p'' − 1) − ''k'' (for ''k'' > 0)에 대해 ''C''_''m''(''k'')를 나눈다. 또한 야코비 기호 (2 | ''p'')가 −1일 때 소수 ''p''는 ''C''_{(''p'' + 1)/2}를 나누고, 야코비 기호 (2 | ''p'')가 + 1일 때 ''p''는 ''C''_{(3''p'' − 1)/2}를 나눈다는 것이 밝혀졌다.

알려진 유일한 쿨렌 소수는 다음과 같은 ''n''에 해당한다.^[1]

: 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881

2009년에는 분산 컴퓨팅 프로젝트인 프라임그리드(PrimeGrid)를 통해 15번째와 16번째 쿨렌 소수가 발견되었다. 15번째 쿨렌 소수는 *C*_6328548 = 6328548 × 2^6328548 + 1 = 1582137 × 2^6328550 + 1이며, 2009년 4월에 발견되었다.^[7] 16번째 쿨렌 소수는 *C*_6679881이며, 2009년 8월에 발견되었다.^[8] 그 크기는 2,010,852자리이며, 발견 당시 알려진 소수 중 15번째로 컸다.^[9]

4. 소수 판정

쿨렌 수의 소수 판정에는 뤼카-레머-리젤 판정법(LLR)이 유효하며, PrimeGrid도 이를 사용하고 있다. 쿨렌 수의 정수성에 대해서는 다음과 같은 사실이 알려져 있다.

• ''p''가 8''k'' ± 5 형태의 소수일 때, ''p''는 ''C''_(''p''+1)/2를 나눈다. 또한, ''p''가 8''k'' ± 1 형태의 소수일 때, ''p''는 ''C''_{(3''p''−1)/2}를 나눈다.
• ''p''를 홀수 소수라고 하고, ''m''(''k'') = (2^''k'' − ''k'')(''p'' − 1) − ''k''라고 하면, 임의의 음이 아닌 정수 ''k''에 대해, ''p''는 ''C''_''m''(''k'')를 나눈다. 특히, ''k'' = 0, 1로 하면, ''p''는 ''C''_''p''−1와 ''C''_''p''−2를 나눈다.

5. 일반화된 쿨렌 수

일반화된 쿨렌 수는 *n* × *b*^*n* + 1 형태의 수로 정의되며, 여기서 *n* + 2 > *b*이다.^[2] 이 형태로 표현되는 소수를 일반화된 쿨렌 소수라고 한다. 우달 수는 제2종 쿨렌 수라고도 불린다.^[2]

2021년 10월 기준으로, 알려진 가장 큰 일반화된 쿨렌 소수는 2525532·73^2525532 + 1이며, 4,705,888 자릿수를 가진다. 이 수는 PrimeGrid 참가자인 Tom Greer에 의해 발견되었다.^[3][4]

페르마의 소정리에 따르면, 특정 조건을 만족하는 소수 *p*에 대해, *n*·*b*^*n* + 1은 *p*로 나누어지므로 소수가 아니다. 예를 들어, *n*이 6 mod 2와 합동일 때 (즉, 2, 8, 14, 20, ...), *n*·*b*^*n* + 1이 소수가 되려면 *b*는 3으로 나누어 떨어져야 한다 (단, *b* = 1 제외).^[5][6]

• n*·*b*^*n* + 1이 소수가 되는 가장 작은 *n* 값들은 다음과 같다 (현재 알려지지 않은 경우 물음표로 표시).^[5][6]

참조

_[1] 서적 Recurrence sequences American Mathematical Society
_[2] 간행물 On Generalized Cullen and Woodall Numbers That are Also Fibonacci Numbers https://cs.uwaterloo[...]
_[3] 웹사이트 PrimeGrid Official Announcement https://www.primegri[...] 2021-08-28
_[4] 웹사이트 PrimePage Primes: 2525532 · 73^2525532 + 1 https://primes.utm.e[...] 2021-11-14
_[5] 웹사이트 Generalized Cullen primes http://guenter.loeh.[...] 2017-05-06
_[6] 웹사이트 List of generalized Cullen primes base 101 to 10000 http://harvey563.tri[...] 2017-05-06
_[7] 뉴스 News archive, 2009-04-21 02:10 UTC http://www.primegrid[...] PrimeGrid
_[8] 뉴스 News archive, 2009-08-05 02:45 UTC http://www.primegrid[...] PrimeGrid
_[9] 웹사이트 The largest known primes: Top 100 http://primes.utm.ed[...] The Prime Pages