와그스태프 소수

정의

와그스태프 수(Wagstaff number)는 [math]\displaystyle{ \displaystyle W_n = \frac{2^n+1}{3}\; (n=2k-1,\ k \in \mathbb{N}) }[/math] 꼴로 표현되는 자연수이다. 와그스태프 소수(Wagstaff prime)는 와그스태프 수 중 소수인 경우를 말한다. 이름은 미국의 수학자 사무엘 와그스태프(Samuel S. Wagstaff Jr.)에게서 따온 것이다.

[math]\displaystyle{ W_n }[/math]이 정수이려면 [math]\displaystyle{ 2^n+1 }[/math]은 3의 배수가 되어야 하고, 이에 따라 [math]\displaystyle{ n }[/math]은 홀수 자연수가 되어야 한다. 메르센 수에서는 2의 지수가 임의의 자연수이면 되지만 여기서는 지수가 홀수인 경우만을 다룬다.

처음 10개 와그스태프 소수의 값은 아래와 같다.

• 3, 11, 43, 683, 2731, 43691, 174763, 2796023, 715827883, 2932031007403, …

성질

홀수 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ \displaystyle W_n = \frac{2^{2n}-1}{3(2^n-1)} = \frac{M_{2n}}{M_2 M_n} }[/math]과 같이 메르센 수의 비로 나타낼 수 있다.

와그스태프 수는 [math]\displaystyle{ \displaystyle W_n= 2^{n-1}-2^{n-2}+\cdots-2+1 }[/math] 꼴로 나타낼 수 있다. 메르센 수에서는 부호가 모두 +이지만 이쪽은 ± 부호가 번갈아 나타난다. 이진법으로 표현하면 1010…101011₍₂₎ 꼴로, 끝의 두 자리만 빼고 '10'이 번갈아 나타나며 전체 [math]\displaystyle{ n-1 }[/math]자릿수이다.

또한 두 부류는 홀수 지수에 대해 각각 [math]\displaystyle{ M_n=\frac{2^n-1}{2-1},\ W_n=\frac{(-2)^n-1}{(-2)-1} }[/math]과 같이 쓸 수도 있으며, 일부 부호만 살짝 다를 뿐 형태는 거의 비슷하다. 더불어 아래 여러 성질은 메르센 소수 문서의 성질과 함께 보면 닮은 점이 많다. 사실상 메르센 수와 쌍둥이인 셈.

기본 성질

1. 와그스태프 수 [math]\displaystyle{ \displaystyle W_n=\frac{2^n+1}{3} }[/math]이 소수이면 [math]\displaystyle{ \displaystyle n }[/math]도 소수이다.
   • 증명: 홀수 [math]\displaystyle{ \displaystyle n }[/math]이 소수가 아니라면, [math]\displaystyle{ \displaystyle n=ab,\ 3 \le a,b \lt n }[/math]인 홀수 약수 [math]\displaystyle{ a, b }[/math]가 존재한다. [math]\displaystyle{ \displaystyle 2^a=x }[/math]로 치환하면 [math]\displaystyle{ \displaystyle x\ge 8, W_n = \frac{2^{ab}+1}{3} = \frac{x^b+1}{3} = \frac{x+1}{3} \cdot (x^{b-1} - x^{b-2} +\cdots - x+1) }[/math]과 같이 쓸 수 있다. 여기서 [math]\displaystyle{ a }[/math]는 홀수이므로 [math]\displaystyle{ x+1=2^a+1 }[/math]은 3의 배수이다. 따라서 [math]\displaystyle{ \displaystyle \frac{x+1}{3} \mid W_n }[/math]이다. 그런데 [math]\displaystyle{ \displaystyle 3 \le \frac{x+1}{3} \lt W_n }[/math]이므로 [math]\displaystyle{ W_n }[/math]은 소수가 아니다.
   • 메르센 수와 마찬가지로 위 명제의 역은 성립하지 않는다. 지수가 소수여도 와그스태프 수는 합성수인 경우가 더 많다. 가령 29는 소수이지만 [math]\displaystyle{ W_{29}=178956971= 29\cdot 3033169 }[/math]이다.
2. [math]\displaystyle{ n }[/math]이 3 이상의 홀수일 때, [math]\displaystyle{ W_n }[/math]을 40으로 나눈 나머지는 3 또는 11이다. (즉 십진법으로 쓸 때 일의 자리수는 1 또는 3이다.)
   • 증명: [math]\displaystyle{ \displaystyle 2^7\equiv 2^3 \pmod{120} }[/math]이므로 임의의 자연수 [math]\displaystyle{ k }[/math]에 대해 [math]\displaystyle{ \displaystyle 2^{4k+3}\equiv 8 \pmod{120},\ 2^{4k+1}\equiv 32 \pmod{120} }[/math]가 성립한다. [math]\displaystyle{ n \equiv 3 \pmod 4 }[/math]이면 [math]\displaystyle{ \displaystyle 2^n \equiv 8 \pmod{120} \Leftrightarrow 3W_n \equiv 9 \pmod{120} }[/math]이고, [math]\displaystyle{ n \equiv 1 \pmod 4,\ n \ge 5 }[/math]이면 [math]\displaystyle{ \displaystyle 2^n \equiv 32 \pmod{120} \Leftrightarrow 3W_n \equiv 33 \pmod{120} }[/math]이다. 각 식의 양 변을 3으로 나누면 [math]\displaystyle{ W_n \equiv 3\ \text{or}\ 11 \pmod{40} }[/math]이 된다.
3. 서로 다른 3 이상의 소수 [math]\displaystyle{ p,q }[/math]에 대해 [math]\displaystyle{ W_p,W_q }[/math]는 서로소이다.
   • 증명: 먼저 [math]\displaystyle{ 2^{2p}-1, 2^{2q}-1 }[/math]의 최대공약수는 [math]\displaystyle{ 2^{\gcd(2p,2q)}-1 = 2^2-1 = 3 }[/math]이다. 한편 [math]\displaystyle{ 2^{2p}-1=3W_p(2^p-1),\ 2^{2q}-1=3W_q(2^q-1) }[/math]에서 [math]\displaystyle{ 2^p-1, 2^q-1 }[/math]는 2의 지수가 홀수이므로 3을 약수로 가지지 않는다. 그러므로 [math]\displaystyle{ \displaystyle \gcd \left(3W_p,3W_q \right) = 3 }[/math]이다. 따라서 [math]\displaystyle{ W_p,W_q }[/math]의 최대공약수는 1이다.

약수 관련 성질

1. [math]\displaystyle{ \displaystyle p }[/math]가 5 이상의 소수일 때, 와그스태프 수 [math]\displaystyle{ \displaystyle W_p }[/math]의 약수는 항상 [math]\displaystyle{ \displaystyle 2kp+1,\,k\in\mathbb{Z}^+ }[/math]의 형태이다.
   • 증명: [math]\displaystyle{ \displaystyle q }[/math]를 [math]\displaystyle{ \displaystyle W_p=\frac{2^p+1}{3} }[/math]의 소인수라 가정하자. [math]\displaystyle{ p \ge 5 }[/math]이면 [math]\displaystyle{ \gcd(W_3,W_p)=\gcd(3,W_p)=1 }[/math]이므로 [math]\displaystyle{ W_p }[/math]는 3의 배수가 아니며, 이는 곧 [math]\displaystyle{ q }[/math]는 3보다 커야 함을 뜻한다. 또한 페르마의 소정리에 의해 [math]\displaystyle{ \displaystyle 2^{q-1} \equiv 1 \pmod q }[/math]이며, [math]\displaystyle{ \displaystyle q \mid 2^{q-1}-1 }[/math]이라 쓸 수 있다. 한편 가정에 따라 [math]\displaystyle{ \displaystyle q \mid 2^p+1 }[/math], 즉 [math]\displaystyle{ \displaystyle q \mid 2^{2p}-1 }[/math]도 성립한다. 그러므로 [math]\displaystyle{ \displaystyle q\mid\gcd\left(2^{q-1}-1,2^{2p}-1\right) }[/math]이며, 유클리드 호제법으로 [math]\displaystyle{ \displaystyle q \mid 2^{\gcd(q-1,p)}-1 }[/math]과 같이 쓸 수 있다. 이때 [math]\displaystyle{ \displaystyle p }[/math]는 소수이고 [math]\displaystyle{ q-1 }[/math]은 짝수이므로, [math]\displaystyle{ \displaystyle \gcd(q-1,2p) }[/math]는 2 또는 [math]\displaystyle{ \displaystyle 2p }[/math]이다. 만약 최대공약수가 2이면, [math]\displaystyle{ \displaystyle q \mid 2^{\gcd(q-1,2p)}-1=2^2-1=3 }[/math]이므로, 앞서 알아본 [math]\displaystyle{ \displaystyle q\gt 3 }[/math]이라는 조건과 모순이다. 따라서 [math]\displaystyle{ \displaystyle \gcd\left(q-1,2p\right)=2p }[/math]이고, [math]\displaystyle{ \displaystyle 2p\mid q-1 }[/math]이다. 곧, 적당한 양의 정수 [math]\displaystyle{ \displaystyle k }[/math]에 대해 [math]\displaystyle{ \displaystyle q=2kp+1 }[/math]이다. 아울러 [math]\displaystyle{ \displaystyle W_p }[/math]의 모든 약수는 해당 수의 소인수 일부의 곱이고, 임의의 소인수는 [math]\displaystyle{ \displaystyle q_i=2kp+1 }[/math] 꼴이므로, 저 형태를 가진 소인수를 곱한 임의의 약수도 같은 형태이다.
   • 예: [math]\displaystyle{ W_{59} = 2833 \cdot 37171 \cdot 1824726041 }[/math]의 각 소인수들은 [math]\displaystyle{ p=59,\ k=24, 315, 15463780 }[/math]에 대응한다.
2. [math]\displaystyle{ n }[/math]이 홀수일 때, [math]\displaystyle{ W_n }[/math]의 약수를 8로 나눈 나머지는 1 또는 3이다. (이때 [math]\displaystyle{ n }[/math]이 소수일 필요는 없다)
   • 증명: [math]\displaystyle{ W_n }[/math]의 소인수 [math]\displaystyle{ q }[/math]를 가정하자. 그러면 [math]\displaystyle{ q \mid 3W_n=2^n+1 }[/math]이므로 [math]\displaystyle{ \displaystyle 2^n \equiv -1 \pmod q }[/math]가 성립한다. 여기서 양변에 2를 곱하면 [math]\displaystyle{ \displaystyle 2^{n+1} \equiv -2 \pmod q }[/math]이다. 이 식에서 좌변은 2의 지수가 짝수이므로 제곱수이며, [math]\displaystyle{ \displaystyle 2^{\frac{n+1}{2}}=x }[/math]라 하면 [math]\displaystyle{ \displaystyle x^2 \equiv -2 \pmod q }[/math]가 된다. 다시 말해 -2는 법 [math]\displaystyle{ q }[/math]에 대한 이차잉여이며, 이를 만족하는 [math]\displaystyle{ q }[/math]의 조건은 [math]\displaystyle{ q \equiv 1\ \text{or}\ 3 \pmod 8 }[/math]이다. 또한 어떤 [math]\displaystyle{ W_n }[/math]의 약수 [math]\displaystyle{ r }[/math]를 [math]\displaystyle{ r=q_1 q_2 \cdots q_k }[/math]와 같이 소인수[math]\displaystyle{ q_j (1\le j \le k) }[/math]의 곱으로 쓸 때, 소인수들 중 8로 나눈 나머지가 3인 항이 짝수 개이면 [math]\displaystyle{ r \equiv 1 \pmod 8 }[/math]이며 홀수 개이면 [math]\displaystyle{ r \equiv 3 \pmod 8 }[/math]이다. 따라서 모든 [math]\displaystyle{ W_n }[/math]의 약수를 8로 나눈 나머지는 1 또는 3이다.
   • 예: [math]\displaystyle{ W_{37} = 1777 \cdot 25781083 }[/math] 에서 각 소인수를 8로 나눈 나머지는 각각 1, 3이다.
3. 소수 [math]\displaystyle{ p }[/math]가 소피 제르맹 소수이고 4로 나눈 나머지가 1이면 [math]\displaystyle{ 2p+1 }[/math]은 [math]\displaystyle{ W_p }[/math]의 약수이다.
   • 증명: [math]\displaystyle{ p }[/math]가 소피 제르맹 소수이면 [math]\displaystyle{ 2p+1 }[/math]도 소수이다. 또한 [math]\displaystyle{ p \equiv 1 \pmod 4 }[/math]이면 [math]\displaystyle{ 2p+1 \equiv 3 \pmod 8 }[/math]이므로, 2는 법 [math]\displaystyle{ 2p+1 }[/math]에 대한 이차잉여가 아니다. 즉 오일러의 규준에 따르면 [math]\displaystyle{ \displaystyle 2^{\frac{(2p+1)-1}{2}} \equiv -1 \pmod{2p+1} }[/math]이 성립한다. 간단히 정리하면 [math]\displaystyle{ \displaystyle 2^p \equiv -1 \pmod{2p+1} }[/math]이고, [math]\displaystyle{ \displaystyle 2p+1 \mid 2^p+1 }[/math]을 만족한다. 따라서 [math]\displaystyle{ 2p+1 \mid W_p }[/math]
   • 예: [math]\displaystyle{ \displaystyle 11 \mid W_{5}(=11),\ 59 \mid W_{29},\ 83 \mid W_{41},\ 3947 \mid W_{1973},\ 4139 \mid W_{2069} }[/math]
   • 참고: [math]\displaystyle{ p }[/math]가 소피 제르맹 소수이면 페르마의 소정리에 따라 [math]\displaystyle{ 2^{2p} \equiv 1 \pmod{2p+1} }[/math] 즉 [math]\displaystyle{ 2p+1 \mid 2^{2p}-1 = 3M_pW_p }[/math]이다. [math]\displaystyle{ p }[/math]를 4로 나눈 나머지가 1이면 [math]\displaystyle{ 2p+1 \mid W_p }[/math], 나머지가 3이면 [math]\displaystyle{ 2p+1 \mid M_p }[/math]이다.

메르센 수와 성질 비교

이상 알아본 성질들을 메르센 수와 견주어보면 아래 표와 같이 정리할 수 있다. 여기서 [math]\displaystyle{ p }[/math]는 3 이상의 소수이다.

정의	[math]\displaystyle{ \displaystyle M_p=2^p-1 }[/math]	[math]\displaystyle{ \displaystyle W_p=\frac{2^p+1}{3} }[/math]
알려진 소수 (2021년 12월까지)	51개	32개
등비급수 표현	[math]\displaystyle{ \displaystyle M_p=\sum_{k=0}^{p-1}2^k }[/math]	[math]\displaystyle{ \displaystyle W_p=\sum_{k=0}^{p-1}(-2)^k }[/math]
뤼카 수열 표현	[math]\displaystyle{ \displaystyle M_p=U_p(1,-2) }[/math]	[math]\displaystyle{ \displaystyle W_p=V_p(1,-2) }[/math]
일의 자리수(십진법)	1 또는 7	1 또는 3
[math]\displaystyle{ p,q }[/math]가 서로소일 때	[math]\displaystyle{ M_p,M_q }[/math]는 서로소	[math]\displaystyle{ W_p,W_q }[/math]는 서로소
약수와 [math]\displaystyle{ p }[/math]의 관계	[math]\displaystyle{ q=2kp+1(p\ge 3) }[/math]	[math]\displaystyle{ q=2kp+1(p\ge 5) }[/math]
약수를 8로 나눈 나머지	1 또는 7	1 또는 3
[math]\displaystyle{ p }[/math]가 소피 제르맹 소수일 때	[math]\displaystyle{ p \equiv 3 \pmod 4 }[/math]이면 [math]\displaystyle{ 2p+1 \mid M_p }[/math]	[math]\displaystyle{ p \equiv 1 \pmod 4 }[/math]이면 [math]\displaystyle{ 2p+1 \mid W_p }[/math]

소수 찾기

와그스태프 수는 메르센 수와 달리 20세기 말에 와서야 성질 탐구와 소수 찾기가 이루어졌다. 사실 위 정의와 성질만 보면 그저 메르센 소수의 변형 정도로 보이겠지만 아래 '신 메르센 추측'과 관련이 있다는 점에서 나름 의미는 있다.

메르센 소수의 경우 뤼카-레머 소수판정법이라는 유용한 정리 덕에 2의 1억 제곱 규모의 수를 검사할 수 있고, 2021년 현재까지 51개가 발견되었다. 하지만 와그스태프 소수는 이에 대응하는 빠른 검사법이 현재 알려지지 않았다. 대부분은 일반적인 자연수에 적용하는 타원곡선 소수판정법으로 확인하고 있으며, 그마저도 2의 12만 제곱 범위까지 소수임을 검증해 냈다.

2의 12만 제곱 이상의 수들은 유력 소수 여부는 알고 있지만 이들이 확실한 소수인지는 아직 모른다. 와그스태프 소수 후보를 확인하는 방법으로 아래 정리가 있다.

어떤 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ W_p }[/math]가 소수이면, [math]\displaystyle{ 25^{2^{p-1}} \equiv 25 \pmod{2^p+1} }[/math]가 성립한다.

하지만 위 정리의 역은 알 수 없다. 다만 위 정리를 만족하지 않으면 소수가 아니라는 것이 확실하므로, 소수 후보를 상당수 걸러낼 수는 있다.

2013년 프랑스의 수학자인 토니 레이(Tony Reix)는 뤼카-레머 소수판정법의 변형으로 아래 추측을 내놓았다.

• [math]\displaystyle{ \displaystyle N_p=2^p+1,W_p=\frac{N_p}{3} }[/math]이라 하자. 그 다음 [math]\displaystyle{ \displaystyle \begin{cases}S_0 = 1/4 \mod{N_q} \\ S_{i+1} = s_i^2-2 \mod{N_q} \end{cases} }[/math] 로 정의되는 수열이 있다.
• [math]\displaystyle{ W_p }[/math]가 소수이면 [math]\displaystyle{ S_{p-1} \equiv S_0 \pmod{W_q} }[/math]가 성립한다. (증명됨)
• 그렇다면 반대로 [math]\displaystyle{ S_{p-1} \equiv S_0 \pmod{W_q} }[/math]이고, [math]\displaystyle{ 0\lt i\lt p-1 }[/math]인 모든 항에 대해 [math]\displaystyle{ S_i \not \equiv S_0 \pmod{W_q} }[/math]이면 [math]\displaystyle{ W_p }[/math]는 소수임을 보여라.

둘째 줄의 조건을 만족하는 수를 브르바-레이 유력 소수(Vrba-Reix PRP)라 부르고 있다.

제시된 조건은 초깃값을 [math]\displaystyle{ S_0=6 }[/math]으로 잡고 합동식을 [math]\displaystyle{ S_p \equiv S_2 \pmod{W_p} }[/math]로 바꾸어도 된다. 셋째 줄의 문제를 증명 시 상금으로 500 유로가 걸려 있다. 현재까지 증명한 사람은 나오지 않았으며, 만약 문제가 풀리면 아래 목록의 유력 소수들은 전부 소수로 확정된다.

신 메르센 추측

메르센 소수의 경우 처음에는 마랭 메르센이 아래와 같은 추측을 제시한 적이 있다.

• [math]\displaystyle{ p\le 257 }[/math]일 때, [math]\displaystyle{ M_p }[/math]가 소수가 되는 [math]\displaystyle{ p }[/math]의 값은 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257이다.

실제로는 [math]\displaystyle{ M_{61},M_{89},M_{107} }[/math]은 소수이고, [math]\displaystyle{ M_{67},M_{257} }[/math]은 소수가 아니라는 것이 판명났다.

비록 메르센의 추측은 반증되었지만, 이것을 변형한 새 추측이 1989년에 나왔다. 이를 신 메르센 소수(New Mersenne conjecture) 또는 베이트만-셀프릿지-와그스태프 추측(Bateman-Selfridge-Wagstaff conjecture)이라 부른다. 그 내용은 아래와 같다.

[math]\displaystyle{ p }[/math]가 소수일 때, 아래 세 명제 중 둘이 참이면 나머지 하나도 참이어야 한다.

1. 적당한 자연수 [math]\displaystyle{ k }[/math]가 존재하여 [math]\displaystyle{ p=2^k\pm 1 }[/math] 또는 [math]\displaystyle{ p=4^k\pm 3 }[/math] 꼴로 표현된다.
2. 메르센 수 [math]\displaystyle{ M_p }[/math]는 소수이다.
3. 와그스태프 수 [math]\displaystyle{ W_p }[/math]는 소수이다.

현재까지는 셋 중 둘만 참인 예는 전혀 나오지 않았다. 아래는 [math]\displaystyle{ p \lt 10^5 }[/math] 범위에서 소수들을 분류한 것이다.

• 세 명제 모두 참: 3, 5, 7, 13, 17, 19, 31, 61, 127
• 첫째 명제만 참: 67, 257, 1021, 4093, 4099, 8191, 16381, 65537, 65539
• 둘째 명제만 참: 89, 107, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243
• 셋째 명제만 참: 11, 23, 43, 79, 101, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369
• 세 명제 모두 거짓: 위의 소수들을 제외한 전부

첫째 명제가 저렇게 세워진 것은 처음 제시된 메르센의 추측과 관련이 있다. 메르센이 제시한 소수는 모두 [math]\displaystyle{ p=2^k\pm 1 }[/math] 내지는 [math]\displaystyle{ p=4^k\pm 3 }[/math] 형태를 하고 있기에, 메르센 본인도 이 기준으로 수를 적었을 것이라 유추가 된다. 그런데 이게 사실이라면, [math]\displaystyle{ 61=4^3-3 }[/math]인데 왜 61이 누락되었는 지는 의문. 당시에는 [math]\displaystyle{ M_{19} }[/math]까지만 확실하게 알고 있었고 [math]\displaystyle{ M_{61} }[/math]이 소수하는 사실은 몰랐다.

와그스태프 소수 목록

2022년 8월 17일까지 발견된 와그스태프 소수는 모두 33개, 유력 소수는 11개이다. 확정된 소수 중 가장 큰 항은 [math]\displaystyle{ W_{117239} }[/math]이다. 유력 소수까지 포함하면 44번째 항인 [math]\displaystyle{ W_{15135397} }[/math]까지 알려졌다. 현재까지는 2의 1000만 제곱 이하로는 유력 소수 검사가 끝난 상태이다. 즉 아래 목록에 없는 1000만 이하의 소수 지수는 와그스태프 소수 후보에서 모두 제외되었다.

와그스태프 소수는 20세기 말에 이르러서야 연구 대상이 되었기에 발견 연도나 발견자 관련 정보는 얼마 되지 않는다. 아래 표에서 33번째까지가 확정된 소수이며, ? 표시된 34~44번째는 아직 소수로 확정되지 않은 유력 소수이다.

순서	[math]\displaystyle{ \displaystyle p }[/math]	자리수	발견 일시 및 발견자
1	3	1
2	5	2
3	7	2
4	11	3
5	13	4
6	17	5
7	19	6
8	23	7
9	31	9
10	43	13
11	61	18
12	79	24
13	101	30
14	127	38
15	167	50
16	191	58
17	199	60
18	313	94
19	347	104
20	701	211
21	1709	514
22	2617	788
23	3539	1065	1989년 12월 (확정)
24	5807	1748	1998년 12월 (확정)
25	10501	3161	1996년 5월 (확정)
26	10691	3218	2004년 10월 (확정)
27	11279	3395	1998년 1월 (확정)
28	12391	3730	1996년 5월 (확정)
29	14479	4359	2004년 11월 (확정)
30	42737	12865	2007년 8월 (확정)
31	83339	25088	2014년 9월 (확정)
32	95369	28709	2021년 8월 (확정)
33	117239	35292	2022년 8월 (확정)
34?	127031	38240
35?	138937	41824
36?	141079	42469
37?	267017	80380
38?	269987	81274
39?	374321	112682
40?	986191	296873	2008년, Vincent Diepeveen (유력)
41?	4031399	1213572	2010년 2월, Anton Vrba, Tony Reix (유력)
42?	13347311	4017941	2013년 9월, Ryan Propper (유력)
43?	13372531	4025533	2013년 9월, Ryan Propper (유력)
44?	15135397	4556209	2021년 6월, Ryan Propper (유력)

관련 문서

• 메르센 소수
• 단위 반복 소수