단위 반복 소수

단위 반복 수(Repunit)는 특정 기수법에서 모든 자리가 1씩 반복되는 수를 말한다. 단위 반복 소수(Repunit prime)는 단위 반복 수 중 소수인 수들이다.

단위 반복 소수는 회문 소수와 재배열 가능 소수에 포함된다. 또, 2진법 단위 반복 소수는 곧 메르센 소수이다.

정의

[math]\displaystyle{ b }[/math]진법 [math]\displaystyle{ n }[/math]자리 단위 반복 수는 등비수열의 합으로 표현할 수 있으며, 해당 진법에서 1이 [math]\displaystyle{ n }[/math]번 나온다.

[math]\displaystyle{ R_n^{(b)}=1111 \cdots 11_{(b)}=\sum_{k=0}^{n-1} b^k=\frac{b^n-1}{b-1}, n \geq 1 }[/math]

이 정의에 따르면 3 이상의 모든 자연수 [math]\displaystyle{ N }[/math]은 [math]\displaystyle{ N-1 }[/math]진법 기준 두 자리 단위 반복 수로 나타낼 수 있다.

단위 반복 수의 성질

아래 성질들은 메르센 소수에서 서술한 메르센 수의 성질과 비슷하다.

• [math]\displaystyle{ R_n^{(b)}=U_n(b+1, b) }[/math] ― 여기서 [math]\displaystyle{ U_n }[/math]은 뤼카 수열이다.
  • 증명: [math]\displaystyle{ a_0=0, a_n=R_n^{(b)} }[/math]이라 하면, 단위 반복 수의 정의에 따라 [math]\displaystyle{ a_n-a_{n-1}=R_n^{(b)}-R_{n-1}^{(b)}=b^n (n \geq 1) }[/math]이다. 그러면 [math]\displaystyle{ a_n-a_{n-1}=b(a_{n-1}-a_{n-2}) }[/math]이고, 정리하면 [math]\displaystyle{ a_n=(b+1)a_{n-1}-ba_{n-2} (n \geq 1) }[/math]이다. [math]\displaystyle{ a_0=0, a_1=1 }[/math]이므로 주어진 수열은 제1종 뤼카 수열이다.
• [math]\displaystyle{ \gcd(R_m^{(b)}, R_n^{(b)})=R_{\gcd(m, n)}^{(b)} }[/math]
• [math]\displaystyle{ R_n^{(b)} }[/math]가 소수이면 [math]\displaystyle{ n }[/math]도 소수이다.
  • 증명: [math]\displaystyle{ n }[/math]이 소수가 아니라면 [math]\displaystyle{ n=uv, 1\lt u, v \lt n }[/math]인 약수가 존재한다. [math]\displaystyle{ (b-1)R_{uv}^{(b)}=b^{uv}-1 }[/math]에서 [math]\displaystyle{ b^u-1=c }[/math]라 하면 [math]\displaystyle{ c \mid (b-1)R_{uv}^{(b)}, 1\lt c\lt R_{uv}^{(n)} }[/math]이다. 이때 [math]\displaystyle{ c \nmid b-1 }[/math]이므로 [math]\displaystyle{ c \mid R_n^{(b)} }[/math], 즉 주어진 수는 소수가 아님을 알 수 있다.
• [math]\displaystyle{ n }[/math]이 홀수이고 [math]\displaystyle{ R_n^{(b)} }[/math]의 약수 [math]\displaystyle{ q }[/math]가 있다면 [math]\displaystyle{ b }[/math]는 법 [math]\displaystyle{ q }[/math]에 대한 이차잉여이다.
  • 증명: [math]\displaystyle{ q \mid R_n^{(b)} }[/math]는 합동식인 [math]\displaystyle{ b^n \equiv 1 \pmod q }[/math]와 같이 쓸 수 있다. 양 변에 [math]\displaystyle{ b }[/math]를 곱하면 [math]\displaystyle{ (b^{\frac{n+1}{2}})^2 \equiv b \pmod q }[/math]이다. 좌변은 자연수의 제곱 꼴로 써지므로, 이차잉여의 정의에 따라 진술은 참이다.
  • 예: 삼진법 단위 반복 수에서는 [math]\displaystyle{ \left(\frac{3}{q} \right)=1 }[/math]이므로 [math]\displaystyle{ q \equiv \pm 1 \pmod{12} }[/math]이다.
• [math]\displaystyle{ p }[/math]가 홀수 소수일 때, [math]\displaystyle{ R_p^{(b)} }[/math]의 소인수 [math]\displaystyle{ q }[/math]는 [math]\displaystyle{ q=2kp+1 (k \in \mathbb{N}) }[/math]의 꼴로 표현되거나 [math]\displaystyle{ b-1 }[/math]의 약수이다.
  • 증명: [math]\displaystyle{ q \mid R_p^{(b)} }[/math]이면 [math]\displaystyle{ \gcd(b, q)=1 }[/math]이다. 해당 조건은 [math]\displaystyle{ q \mid b^p-1 }[/math]로 쓸 수 있다. [math]\displaystyle{ q }[/math]가 소수일 때, 페르마의 소정리에 의해 [math]\displaystyle{ b^{q-1} \equiv 1 \pmod q }[/math]이다. 즉 [math]\displaystyle{ q \mid \gcd(b^p-1, b^{q-1}-1)=b^{\gcd(p, q-1)}-1 }[/math]이다. [math]\displaystyle{ p }[/math]가 소수라는 가정으로 [math]\displaystyle{ \gcd(p, q-1) }[/math]은 1과 [math]\displaystyle{ p }[/math] 둘 중 하나이다. 전자의 경우 [math]\displaystyle{ q \mid b-1 }[/math]이고, 후자는 [math]\displaystyle{ p \mid q-1 }[/math]을 의미한다. 따라서 [math]\displaystyle{ q=mp+1 }[/math]의 꼴로 써지며, 여기서 [math]\displaystyle{ m }[/math]은 짝수이므로 진술의 식과 같은 모양이 된다.
• [math]\displaystyle{ b=c^r }[/math]을 만족하는 1보다 큰 자연수 [math]\displaystyle{ c, r }[/math]이 존재하면 [math]\displaystyle{ n \gt r }[/math]에서 [math]\displaystyle{ R_n^{(b)} }[/math]은 단위 반복 소수가 아니다.
  • 증명: [math]\displaystyle{ R_n^{(b)}=\frac{b^n-1}{b-1}=\frac{c^{rn}-1}{c^r-1} }[/math]에서 [math]\displaystyle{ c^n-1 \mid c^{rn}-1=(c^r-1)R_n^{(b)} }[/math]이므로 [math]\displaystyle{ s \mid R_n^{(b)}, s=\frac{c^n-1}{\gcd(c^n-1, c^r-1)}\lt R_n^{(b)} }[/math]이다. 이때 [math]\displaystyle{ n\gt r \Rightarrow n \nmid r }[/math]이므로 [math]\displaystyle{ \gcd(n, r)\lt n,\ \gcd(c^n-1, c^r-1)\lt c^n-1 }[/math]이다. 그러므로 [math]\displaystyle{ s\gt 1 }[/math]을 이끌어내고, [math]\displaystyle{ R_n^{(b)} }[/math] 내에서는 비자명한 약수가 존재함을 알 수 있다.
  • 예: 사진법에서는 [math]\displaystyle{ R_2^{(4)}=5 }[/math], 팔진법에서는 [math]\displaystyle{ R_3^{(8)}=73 }[/math]으로 단위 반복 소수가 각각 하나뿐이다. 아울러 구진법에서는 소수가 전혀 없다.

알려진 소수와 빈도

아래 목록은 정해진 [math]\displaystyle{ b }[/math]에 대해 [math]\displaystyle{ R_n^{(b)} }[/math]가 소수인 2022년 8월 28일까지 알려진 [math]\displaystyle{ n }[/math]의 목록을 나열한 것이다. 기울임체 표시는 확정된 소수가 아닌 유력 소수이다. (유력 소수 여부는 각 OEIS 링크의 문서에서 Extension 문단에 적혀 있다)

• 이진법(메르센 소수): 소수 51개 (OEIS의 수열 A000043)
  • 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933
• 삼진법: 소수 16개, 유력 소수 5개 (OEIS의 수열 A028491)
  • 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, 2215303, 2704981, 3598867
• 오진법: 소수 15개, 유력 소수 4개 (OEIS의 수열 A004061)
  • 3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, 13873, 16519, 201359, 396413, 1888279, 3300593
• 육진법: 소수 13개, 유력 소수 3개 (OEIS의 수열 A004062)
  • 2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, 79987, 608099, 1365019
• 칠진법: 소수 6개, 유력 소수 4개 (OEIS의 수열 A004062)
  • 5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, 1264699
• 십진법: 소수 6개, 유력 소수 5개 (OEIS의 수열 A004023)
  • 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, 5794777, 8177207

이진법의 경우 메르센 수의 소수 여부를 결정하는 뤼카-레머 소수판정법으로 확실한 소수를 천만 자리 범위에서도 비교적 쉽게 찾을 수 있다. 하지만 다른 진법에서는 이에 상응하는 빠른 소수판정법이 현재로서는 없고, 연산량이 많은 타원곡선 소수판정법을 주로 이용한다. [math]\displaystyle{ n\gt 3 \times 10^4 }[/math] 범위에서는 소수 여부를 가려내기 매우 힘들기에 현재 대부분 유력 소수 상태에 머물러 있다.

단위 반복 소수에 관한 추측으로 두 가지가 있다. 단, [math]\displaystyle{ b }[/math]가 특정 자연수의 거듭제곱이 아니라는 전제를 한다.

1. 각 진법에서 소수의 개수는 무한하다.
2. [math]\displaystyle{ 1\lt n\lt N }[/math] 범위 내에서 [math]\displaystyle{ b }[/math]가 클수록 소수 [math]\displaystyle{ R_n^{(b)} }[/math]의 개수는 적어진다. (즉 소수의 빈도가 내려간다)