쿨렌 수(Cullen number)는 [math]\displaystyle{ C_n=n \cdot 2^n+1 (n \geq 1) }[/math]의 꼴로 표현되는 자연수로, 제임스 쿨렌(James Cullen)에서 이름이 붙었다. 쿨렌 소수(Cullen prime)는 쿨렌 수 중 소수인 수들을 말한다.
쿨렌 수는 프로트 수의 특수한 형태이므로 프로트의 정리로 소수 여부를 알아낼 수 있다.
특징[편집 | 원본 편집]
쿨렌 수의 특정 항에서 바로 이전 항의 두 배를 빼면 메르센 수가 된다. 즉 [math]\displaystyle{ C_n-2C_{n-1}=2^n-1=M_n }[/math]. 또, [math]\displaystyle{ C_n=2U_n(4, 4)+1 }[/math]로도 표현이 되며, 여기서 [math]\displaystyle{ U_n }[/math]은 제1종 뤼카 수열이다.
임의의 홀수 소수 [math]\displaystyle{ p }[/math]를 약수로 가지는 쿨렌 수가 존재한다.
- [math]\displaystyle{ p \equiv \pm 1 \pmod 8 }[/math]이면 [math]\displaystyle{ p \mid C_{\frac{3p-1}{2}} }[/math]이다.
- 증명: 2는 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여이므로, 오일러의 규준에 의해 [math]\displaystyle{ 2^{\frac{p-1}{2}} \equiv 1 \pmod p }[/math]이다. 양 변을 세제곱하고 [math]\displaystyle{ 3p-1 }[/math]을 곱하면 [math]\displaystyle{ (3p-1)2^{\frac{3p-3}{2}} \equiv 3p-1 \equiv -1 \pmod p }[/math]이고, 다시 양 변에 1을 더하면 [math]\displaystyle{ \frac{3p-1}{2} \cdot 2^{\frac{3p-1}{2}}+1 \equiv 0 \pmod p }[/math]이다. 따라서 [math]\displaystyle{ C_{\frac{3p-1}{2}} \equiv 0 \pmod p }[/math]를 얻는다.
- [math]\displaystyle{ p \equiv \pm 3 \pmod 8 }[/math]이면 [math]\displaystyle{ p \mid C_{\frac{p+1}{2}} }[/math]이다.
- 증명: 2는 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여가 아니므로 [math]\displaystyle{ 2^{\frac{p-1}{2}} \equiv -1 \pmod p }[/math]이다. 양 변에 [math]\displaystyle{ p+1 }[/math]을 곱하면 [math]\displaystyle{ (p+1)2^{\frac{p-1}{2}} \equiv -(p+1) \equiv -1 \pmod p }[/math]이고, 다시 양 변에 1을 더하면 [math]\displaystyle{ \frac{p+1}{2} \cdot 2^{\frac{p+1}{2}}+1 \equiv 0 \pmod p }[/math]이다. 그러므로 [math]\displaystyle{ C_{\frac{p+1}{2}} \equiv 0 \pmod p }[/math]를 얻는다.
위 두 성질에 의해 [math]\displaystyle{ 3 \mid C_2, 5 \mid C_3, 7 \mid C_{10}, 11 \mid C_6, \cdots }[/math] 등을 얻는다.
쿨렌 소수 목록[편집 | 원본 편집]
2022년 8월 30일까지 발견된 쿨렌 소수는 모두 16개이다.[1] (OEIS의 수열 A005849)
순번 | [math]\displaystyle{ n }[/math] | [math]\displaystyle{ C_n }[/math] | 자릿수 | 발견 일시 |
---|---|---|---|---|
1 | 1 | 3 | 1 | |
2 | 141 | [math]\displaystyle{ 141 \cdot 2^{141}+1 }[/math] | 45 | 1958년 |
3 | 4713 | [math]\displaystyle{ 4713 \cdot 2^{4713}+1 }[/math] | 1423 | 1984년 12월 |
4 | 5795 | [math]\displaystyle{ 5795 \cdot 2^{5795}+1 }[/math] | 1749 | 1984년 12월 |
5 | 6611 | [math]\displaystyle{ 6611 \cdot 2^{6611}+1 }[/math] | 1994 | 1984년 12월 |
6 | 18496 | [math]\displaystyle{ 289 \cdot 2^{18502}+1 }[/math] | 5573 | 1984년 12월 |
7 | 32292 | [math]\displaystyle{ 8073 \cdot 2^{32294}+1 }[/math] | 9726 | 1997년 5월 |
8 | 32469 | [math]\displaystyle{ 289 \cdot 2^{18502}+1 }[/math] | 5573 | 1997년 5월 |
9 | 59656 | [math]\displaystyle{ 8073 \cdot 2^{32294}+1 }[/math] | 9726 | 1997년 5월 |
10 | 90825 | [math]\displaystyle{ 141 \cdot 2^{141}+1 }[/math] | 27347 | 1997년 5월 |
11 | 262419 | [math]\displaystyle{ 4713 \cdot 2^{4713}+1 }[/math] | 79002 | 1998년 3월 |
12 | 361275 | [math]\displaystyle{ 361275 \cdot 2^{361275}+1 }[/math] | 108761 | 1998년 7월 |
13 | 481899 | [math]\displaystyle{ 481899 \cdot 2^{481899}+1 }[/math] | 145072 | 1998년 9월 |
14 | 1354828 | [math]\displaystyle{ 338707 \cdot 2^{1354830}+1 }[/math] | 407850 | 2005년 8월 |
15 | 6328548 | [math]\displaystyle{ 1582137 \cdot 2^{6328550}+1 }[/math] | 1905090 | 2009년 4월 |
16 | 6679881 | [math]\displaystyle{ 6679881 \cdot 2^{6679881}+1 }[/math] | 2010852 | 2009년 8월 |
우달 수[편집 | 원본 편집]
우달 수(Woodall number)는 쿨렌 수의 정의에서 1의 부호가 바뀐 수이다. 즉 [math]\displaystyle{ W_n=n \cdot 2^n-1 }[/math]이며, '제2종 쿨렌 수'라고도 불린다. 우달 소수(Woodall prime)는 우달 수 중 소수인 수들을 말한다. 이쪽은 뤼카-레머-리젤 소수판정법으로 소수 여부를 가려낼 수 있다.
[math]\displaystyle{ n }[/math]이 2의 거듭제곱이면 우달 수는 메르센 수가 된다. 즉 [math]\displaystyle{ W_{2^k}=2^{k+2^k}-1=M_{k+2^k} }[/math]
앞서 소개한 쿨렌 수와 비슷하게, 임의의 홀수 소수 [math]\displaystyle{ p }[/math]를 약수로 가지는 우달 수를 찾을 수 있다. 단, 쿨렌 수와는 조건과 성질이 서로 바뀌어 있으며, 위와 같은 방식으로 증명할 수 있다.
- [math]\displaystyle{ p \equiv \pm 1 \pmod 8 }[/math]이면 [math]\displaystyle{ p \mid C_{\frac{p+1}{2}} }[/math]이다.
- [math]\displaystyle{ p \equiv \pm 3 \pmod 8 }[/math]이면 [math]\displaystyle{ p \mid C_{\frac{3p-1}{2}} }[/math]이다.
2022년 8월 30일까지 발견된 우달 소수는 모두 34개이다.[2] (OEIS의 수열 A002234) 이 중 [math]\displaystyle{ W_2=M_3, W_{512}=M_{521} }[/math]은 메르센 소수이기도 하다.
순번 | [math]\displaystyle{ n }[/math] | [math]\displaystyle{ W_n }[/math] | 자릿수 | 발견 일시 |
---|---|---|---|---|
1 | 2 | 7 | 1 | |
2 | 3 | 23 | 2 | |
3 | 6 | 383 | 3 | |
4 | 30 | 32212254719 | 11 | |
5 | 75 | [math]\displaystyle{ 75 \cdot 2^{75}-1 }[/math] | 25 | |
6 | 81 | [math]\displaystyle{ 81 \cdot 2^{81}-1 }[/math] | 27 | |
7 | 115 | [math]\displaystyle{ 115 \cdot 2^{115}-1 }[/math] | 37 | |
8 | 123 | [math]\displaystyle{ 123 \cdot 2^{123}-1 }[/math] | 40 | |
9 | 249 | [math]\displaystyle{ 249 \cdot 2^{249}-1 }[/math] | 78 | |
10 | 362 | [math]\displaystyle{ 181 \cdot 2^{363}-1 }[/math] | 112 | |
11 | 384 | [math]\displaystyle{ 3 \cdot 2^{391}-1 }[/math] | 119 | |
12 | 462 | [math]\displaystyle{ 231 \cdot 2^{463}-1 }[/math] | 142 | |
13 | 512 | [math]\displaystyle{ 2^{521}-1 }[/math] | 157 | |
14 | 751 | [math]\displaystyle{ 751 \cdot 2^{751}-1 }[/math] | 229 | |
15 | 822 | [math]\displaystyle{ 411 \cdot 2^{823}-1 }[/math] | 251 | |
16 | 5312 | [math]\displaystyle{ 83 \cdot 2^{5318}-1 }[/math] | 1603 | 1984년 12월 |
17 | 7755 | [math]\displaystyle{ 7755 \cdot 2^{7755}-1 }[/math] | 2339 | 1984년 12월 |
18 | 9531 | [math]\displaystyle{ 9531 \cdot 2^{9531}-1 }[/math] | 2874 | 1984년 12월 |
19 | 12379 | [math]\displaystyle{ 12379 \cdot 2^{12379}-1 }[/math] | 3731 | 1984년 12월 |
20 | 15822 | [math]\displaystyle{ 7911 \cdot 2^{15823}-1 }[/math] | 4768 | 1987년 12월 |
21 | 18885 | [math]\displaystyle{ 18885 \cdot 2^{18885}-1 }[/math] | 5690 | 1987년 12월 |
22 | 22971 | [math]\displaystyle{ 22971 \cdot 2^{22971}-1 }[/math] | 6920 | 1997년 5월 |
23 | 23005 | [math]\displaystyle{ 23005 \cdot 2^{23005}-1 }[/math] | 6930 | 1997년 5월 |
24 | 98726 | [math]\displaystyle{ 49363 \cdot 2^{98727}-1 }[/math] | 29725 | 1997년 5월 |
25 | 143018 | [math]\displaystyle{ 71509 \cdot 2^{143019}-1 }[/math] | 43058 | 1998년 4월 |
26 | 151023 | [math]\displaystyle{ 151023 \cdot 2^{151023}-1 }[/math] | 45468 | 1998년 5월 |
27 | 667071 | [math]\displaystyle{ 667071 \cdot 2^{667071}-1 }[/math] | 200815 | 2000년 9월 |
28 | 1195203 | [math]\displaystyle{ 1195203 \cdot 2^{1195203}-1 }[/math] | 359799 | 2005년 7월 |
29 | 1268979 | [math]\displaystyle{ 1268979 \cdot 2^{1268979}-1 }[/math] | 382007 | 2007년 6월 |
30 | 1467763 | [math]\displaystyle{ 1467763 \cdot 2^{1467763}-1 }[/math] | 441847 | 2007년 6월 |
31 | 2013992 | [math]\displaystyle{ 251749 \cdot 2^{2013995}-1 }[/math] | 606279 | 2007년 8월 |
32 | 2367906 | [math]\displaystyle{ 1183953 \cdot 2^{2367907}-1 }[/math] | 712818 | 2007년 9월 |
33 | 3752948 | [math]\displaystyle{ 938237 \cdot 2^{3752950}-1 }[/math] | 1129757 | 2007년 12월 |
34 | 17016602 | [math]\displaystyle{ 8508301 \cdot 2^{17016603}-1 }[/math] | 5122515 | 2018년 3월 |
각주
- ↑ Prime pages, Top 20: Cullen primes
- ↑ Prime pages, Top 20: Woodall primes
소수의 종류 | |
---|---|
소수 순서쌍 | |
정리 및 추측 | |
소수 관련 주제 |