쿨렌 수

쿨렌 수(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개이다. (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개이다. (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월