Prime number

소수(prime number, 또는 prime)는 두 개의 더 작은 자연수를 곱(product)으로 형성될 수 없는 1보다 큰 자연수(natural number)입니다. 소수가 아닌 1보다 큰 자연수는 합성수(composite number)라고 불립니다. 예를 들어, 5는 소수인데 왜냐하면 그것을 곱(product)으로 쓰는 유일한 방법은 1 × 5 또는 5 × 1, 5 그 자체를 포함하기 때문입니다. 어쨌든, 4은 합성수인데 왜냐하면 그것은 곱 (2 × 2)이기 때문입니다.이것에서 두 숫자는 4보다 작기 때문입니다. 소수는 산술의 기본 정리(fundamental theorem of arithmetic)때문에 숫자 이론(number theory)에서 핵심적입니다: 1보다 큰 모든 각 자연수는 소수 그 자체 또는 그것들의 순서까지(up to) 유일한 소수의 곱으로 인수화될 수 있습니다.

소수가 되는 속성은 소수성(primality)이라고 불립니다. 나눗셈 시도(trial division)라고 불리는 주어진 숫자 $n$ 의 소수성을 검사하는 느리지만 간단한 방법은 $n$ 이 2와 ${\sqrt {n}}$ 사이의 임의의 정수의 배수인지 테스트합니다. 더 빠른 알고리듬은 빠르지만 오류의 작은 가능성을 가지는 밀러-라빈 소수성 테스트(Miller–Rabin primality test)와 다항 시간(polynomial time)에 항상 정답을 산출하지만 실용적인 면에서는 너무 느린 AKS 소수성 테스트(AKS primality test)를 포함합니다. 특별히 빠른 방법은 메르센 숫자(Mersenne number)와 같은 특수 형식의 숫자에 대해 유용합니다. 2018년 01월 기준, 가장 큰 알려진 소수(largest known prime number)는 24,862,048 십진 자릿수(decimal digits)를 가집니다.^[1]

기원전 300년경에 유클리드에 의해 시연(demonstrated by Euclid)된 바와 같이 무한하게 많은(infinitely many) 소수가 있습니다. 합성수로부터 소수를 구별하는 알려진 간단한 공식은 없습니다. 어쨌든, 큰 숫자의 자연수 내의 소수의 분포는 통계적으로 모델링될 수 있습니다. 그 방향의 첫 번째 결과는 19세기 말에 입증된 소수 정리(prime number theorem)이며, 이는 무작위로 선택된 숫자가 소수일 확률(probability)은 자릿수의 숫자, 즉 그의 알고리듬(logarithm)에 반비례(inversely proportional)한다고 말합니다.

소수에 관한 여러 가지 역사적인 질문은 여전히 해결되지 않았습니다. 이것들은 2보다 큰 모든 짝수 정수는 두 소수의 합으로 표현될 수 있다는 골드바흐의 추측(Goldbach's conjecture)과 그것들 사이에는 짝수 한 개만 있는 소수의 쌍이 무한히 많다는 쌍둥이 소수(twin prime) 추측을 포함합니다. 그러한 질문은 숫자의 해석적(analytic) 또는 대수적(algebraic) 관점에 초점을 맞춘 숫자 이론의 다양한 분야의 발전에 박차를 가했습니다. 소수는 그것의 인수로 큰 숫자를 인수화(factoring)하는 것의 어려움에 의존하는 공개-키 암호화(public-key cryptography)와 같은 정보 기술(information technology)의 여러 곳에 사용됩니다. 추상 대수학(abstract algebra)에서, 소수처럼 일반화된 방식으로 행동하는 대상은 소수 원소(prime element)와 소수 아이디얼(prime ideal)을 포함합니다.

Definition and examples

자연수 (1, 2, 3, 4, 5, 6, 등)는 만약 그것이 1보다 크고 더 작은 두 자연수의 곱으로 쓸 수 없으면 소수라고 불립니다. 소수가 아닌 1보다 큰 숫자는 합성수(composite numbers)라고 불립니다.^[2] 다시 말해, $n$ 항목을 하나보다 많은 항목으로 이루어진 더 작은 같은 크기의 그룹으로 나눌 수 없거나,^[3] $n$ 점을 폭이 일보다 많은 점 너비와 일보다 많은 점 높이인 직사각형 그리드로 정렬할 수 없으면 $n$ 은 소수입니다.^[4] 예를 들어, 1부터 6까지의 숫자 중, 숫자 2, 3, 및 5는 소수인데,^[5] 왜냐하면 (나머지 없이) 그것들을 균등하게 나누는 다른 숫자가 없기 때문입니다. 1은 소수가 아닌데, 왜냐하면 그것은 정의에서 특별히 제외되기 때문입니다. 4 = 2 × 2 및 6 = 2 × 3은 모두 합성입니다.

자연수 $n$ 의 약수(divisors)는 $n$ 을 균등하게 나누는 자연수입니다. 모든 각 자연수는 약수로 1과 자기 자신 둘 다를 가집니다. 만약 그것이 임의의 다른 약수를 가지면, 그것은 소수가 될 수 없습니다. 이것은 소수의 동등한 정의로 이어집니다: 그것들은 정확히 두 개의 양의 약수를 갖는 숫자입니다. 그것들 둘은 1과 그 숫자 자체입니다. 1은 오직 하나의 약수, 자기 자신을 가지기 때문에, 이 정의에 의해 소수가 아닙니다.^[6] 같은 것을 표현하는 또 다른 방법은 숫자 $n$ 이 1보다 크고 숫자 $2,3,\dots ,n-1$ 중 어느 것도 $n$ 을 균등하게 나누지 않으면 소수라는 것입니다.^[7]

처음 25개의 소수 (100보다 작은 모든 소수)는 다음과 같습니다:^[8]

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (OEIS에서 수열 A000040).

2보다 큰 짝수 $n$ 은 소수가 아닌데, 왜냐하면 임의의 그러한 숫자는 $2\times n/2$ 의 곱으로 표현될 수 있기 때문입니다. 그러므로, 2를 제외한 모든 각 소수는 홀수이고, 홀수 소수(odd prime)라고 불립니다.^[9] 마찬가지로, 보통의 십진 시스템으로 쓸 때, 5보다 큰 모든 소수는 1, 3, 7, 또는 9로 끝납니다. 다른 자릿수로 끝나는 숫자는 모두 합성수입니다: 0, 2, 4, 6, 또는 8로 끝나는 십진수는 짝수이고, 0 또는 5로 끝나는 십진수는 5로 나눌 수 있습니다.^[10]

모든 소수의 집합(set)은 때때로 $\mathbf {P}$ (굵은-글꼴 대문자 P)^[11] 또는 $\mathbb {P}$ (칠판 굵은-글꼴 대문자 P)로 표시됩니다.^[12]

History

기원전 1550년경의 린드 수학적 파피루스(Rhind Mathematical Papyrus)에는 소수와 합성수에 대한 다양한 형식의 이집트 분수(Egyptian fraction) 전개가 있습니다.^[13] 어쨌든, 소수에 대한 명시적 연구의 가장 오래된 기록은 고대 그리스 수학에서 나옵니다. 유클리드의 원론(Elements, 기원전 300년경)은 소수의 무한성(infinitude of primes)과 산술의 기본 정리를 입증하고, 메르센 소수(Mersenne prime)에서 완전한 숫자(perfect number)를 구성하는 방법을 보여줍니다.^[14] 또 다른 그리스 발명품, 에라토스테네스의 체(Sieve of Eratosthenes)는 여전히 소수 목록을 구성하는 데 사용됩니다.^[15]^[16]

기원후 1000년경, 이슬람 수학자 이븐 알-하이삼(Ibn al-Haytham, Alhazen)은 소수를 $(n-1)!+1$ 을 균등하게 나누는 숫자 $n$ 으로 특성화하는 윌슨의 정리(Wilson's theorem)를 발견했습니다. 그는 역시 모든 짝수 완전한 숫자가 메르센 소수를 사용한 유클리드의 구성에서 나온 것이라고 추측했지만, 그것을 입증할 수는 없었습니다.^[17] 또 다른 이슬람 수학자 이븐 알-반나 알-마라쿠시(Ibn al-Banna' al-Marrakushi)는 에라토스테네스의 체는 위쪽 경계의 제곱근까지 소수 약수만 고려함으로써 속도를 높일 수 있음을 관찰했습니다.^[16] 피보나치(Fibonacci)는 이슬람 수학의 혁신을 유럽으로 가져갔습니다. 그의 저서 Liber Abaci (1202)는 제곱근까지만 약수를 사용하여 소수성을 테스트하기 위한 나눗셈 시도(trial division)를 처음으로 설명했습니다.^[16]

1640년에서, 피에르 드 페르마(Pierre de Fermat)는 (증명 없이) 페르마의 작은 정리(Fermat's little theorem, 나중에 라이프니츠와 오일러에 의해 입증됨)를 설명했습니다.^[18] 페르마는 역시 페르마 숫자 $2^{2^{n}}+1$ 의 소수성을 조사했고,^[19] 마린 메르센(Marin Mersenne)은 $p$ 자체가 소수인 $2^{p}-1$ 형식의 소수, 메르센 소수(Mersenne primes)를 연구했습니다.^[20] 크리스티안 골드바흐(Christian Goldbach)는 1742년 오일러에게 보낸 편지에서 모든 각 짝수는 두 소수의 합이라는 골드바흐의 추측(Goldbach's conjecture)을 공식화했습니다.^[21] 오일러는 모든 짝수 완전한 숫자가 메르센 소수로부터 구성될 수 있다는 알하젠의 추측 (지금의 유클리드-오일러 정리)을 입증했습니다.^[14] 그는 소수의 무한성과 소수의 역수의 합 ${\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots$ 의 발산에 대한 그의 증명에서 이 영역에 수학적 해석 방법을 도입했습니다.^[22] 19세기 초에, 르장드르와 가우스는 $x$ 가 무한대로 갈 때, $x$ 까지의 소수의 개수는 $x/\log x$ 에 점근적(asymptotic)이라고 추측했으며, 여기서 $\log x$ 는 $x$ 의 자연 로그(natural logarithm)입니다. 소수의 이러한 높은 밀도의 약한 결과는 1852년 패스너리 체비쇼프(Pafnuty Chebyshev)에 의해 입증된 모든 각 $n>1$ 에 대해 $n$ 과 $2n$ 사이의 소수가 있다는 버트런드의 공준(Bertrand's postulate)이었습니다.^[23] 제타 함수에 관한 1859년 논문에서 베른하르트 리만(Bernhard Riemann)의 아이디어는 르장드르와 가우스의 추측을 입증하기 위한 개요를 기술했습니다. 비록 밀접하게 관련된 리만 가설(Riemann hypothesis)은 아직 입증되지 않았지만, 리만의 개요는 1896년 아다마르(Hadamard)와 드 라 발레 푸생(de la Vallée Poussin)에 의해 완성되었고, 그 결과는 이제 소수 정리(prime number theorem)로 알려져 있습니다.^[24] 또 다른 중요한 19세기 결과는 특정 산술 진행(arithmetic progressions)이 무한하게 많은 소수를 포함한다는 산술 진행에 대한 디리클레의 정리였습니다.^[25]

많은 수학자들은 나눗셈 시도가 실제로 적용될 수 있는 것보다 더 큰 숫자에 대한 소수성 테스트(primality tests)를 연구해 왔습니다. 특정 숫자 형식으로 제한되는 방법에는 페르마 숫자에 대한 페팽의 테스트(Pépin's test, 1877),^[26] 프로트의 정리(Proth's theorem, 1878년경),^[27] 루카스-레머 소수성 테스트(Lucas–Lehmer primality test, 1856년 시작), 및 일반화된 루카스 소수성 테스트(Lucas primality test)가 포함됩니다.^[16]

1951년 이래로, 컴퓨터에서 이들 테스트를 사용하여 모든 가장 큰 알려진 소수(largest known primes)가 발견되어 왔습니다.^[a] 더 큰 소수에 대한 검색은 Great Internet Mersenne Prime Search 및 기타 분산 컴퓨팅 프로젝트를 통해 수학계 외부의 관심을 불러일으켰습니다.^[8]^[29] 소수가 순수 수학 이외의 분야에서는 거의 사용되지 않는다는^[b] 아이디어는 1970년대에 소수를 그것들의 기반으로 사용하는 공개-키 암호화(public-key cryptography)와 RSA 암호화 시스템이 발명되면서 산산이 부서졌습니다.^[32]

전산화된 소수성 테스트와 인수분해의 실질적인 중요성 증가로 인해 많은 수의 제한되지 않은 형식을 처리할 수 있는 개선된 방법이 개발되었습니다.^[15]^[33]^[34] 소수의 수학적 이론은 역시 소수의 임의적으로 긴 산술 진행이 있다는 그린-타오 정리(Green–Tao theorem, 2004)와 경계진 크기의 소수 틈(prime gaps)이 무한하게 많이 존재한다는 장이탕(Yitang Zhang)의 2013년 증명과 함께 발전했습니다.^[35]

Primality of one

대부분의 초기 그리스인들은 1을 숫자로 생각조차 하지 않으므로,^[36]^[37] 그들은 그것의 소수성을 고려할 수 없었습니다. Nicomachus, Iamblichus, Boethius, 및 Cassiodorus를 포함한 그리스와 후기 로마 전통에서 몇몇 학자들도 소수를 홀수의 세분으로 고려했으므로, 그들은 2도 소수로 고려하지 않았습니다. 어쨌든, 유클리드와 대다수의 다른 그리스 수학자들은 2를 소수로 고려했습니다. 중세 이슬람 수학자들은 1을 숫자가 아닌 것으로 보는 그리스인의 견해를 대체로 따랐습니다.^[36] 중세와 르네상스 시대에, 수학자들은 1을 숫자로 취급하기 시작했고, 그들 중 일부는 그것을 첫 번째 소수로 포함했습니다.^[38] 18세기 중반에 크리스티안 골드바흐(Christian Goldbach)는 레온하르트 오일러(Leonhard Euler)와의 서신에서 1을 소수로 나열했습니다; 어쨌든, 오일러 자신은 1을 소수로 고려하지 않았습니다.^[39] 19세기에 많은 수학자들은 여전히 1을 소수로 고려했고,^[40] 1을 포함하는 소수 목록은 1956년까지 계속 출판되었습니다.^[41]^[42]

만약 소수의 정의가 1을 소수라고 부르도록 변경되면, 소수를 포함하는 많은 명제가 더 어색한 방법으로 다시 쓸 필요가 있습니다. 예를 들어, 산술의 기본 정리는 1보다 큰 소수로의 인수분해라는 용어로 바꿔야 할 필요가 있는데, 왜냐하면 모든 각 숫자는 1의 사본 수에 관계없이 여러 인수분해를 가지기 때문입니다.^[40] 마찬가지로, 에라토스테네스의 체(sieve of Eratosthenes)는 1을 소수로 취급하면 1의 배수 (즉, 다른 모든 숫자)를 모두 제거하고 단일 숫자 1만 출력하기 때문에 올바르게 작동하지 않습니다.^[42] 소수의 일부 다른 기술적 특성은 역시 숫자 1에 대해서도 유지되지 않습니다: 예를 들어, 오일러의 토션트 함수(Euler's totient function) 또는 약수의 합 함수(sum of divisors function)에 대한 공식은 소수에 대한 공식과 그것들이 1에 대한 공식과 다릅니다.^[43] 20세기 초에, 수학자들은 1이 소수로 나열되는 것이 아니라, 오히려 "단위(unit)"로 자체의 특수 카테고리에 나열하는 데 동의하기 시작했습니다.^[40]

Elementary properties

Unique factorization

숫자를 소수의 곱으로 쓰는 것은 그 숫자의 소수 인수분해(prime factorization)라고 불립니다. 예를 들어:

{\begin{aligned}34866&=2\times 3\times 3\times 13\times 149\\&=2\times 3^{2}\times 13\times 149.\end{aligned}}

곱에서 용어는 소수 인수(prime factors)라고 불립니다. 같은 소수 인수는 두 번 이상 발생할 수 있습니다; 이 예제는 소수 인수 $3$ 의 복사본이 두 개 있습니다. 소수가 여러 번 발생할 때, 지수(exponentiation)는 같은 소수의 여러 복사본을 함께 그룹화하기 위해 사용될 수 있습니다: 예를 들어, 위의 곱을 쓰는 두 번째 방법에서, $3^{2}$ 은 $3$ 의 제곱(square) 또는 두 번째 거듭제곱을 나타냅니다.

일반적으로 숫자 이론과 수학에서 소수의 핵심적인 중요성은 산술의 기본 정리(fundamental theorem of arithmetic)에서 비롯됩니다.^[44] 그 정리에 따르면 1보다 큰 모든 각 정수는 하나 이상의 소수의 곱으로 나타낼 수 있습니다. 더 강력하게, 이 곱은 같은 숫자의 두 소수 인수분해는 그것들의 순서가 다를 수 있지만 같은 소수의 같은 사본의 개수를 가진다는 점에서 독특합니다.^[45] 따라서, 정수 인수분해(integer factorization) 알고리듬을 사용하여 인수분해를 찾는 방법에는 많은 다른 방법이 있지만, 그것들은 모두 같은 결과를 생성해야 합니다. 소수는 따라서 자연수의 "기본 빌딩 블록"으로 고려될 수 있습니다.^[46]

소수 인수분해의 고유성에 대한 몇 가지 증명은 유클리드의 보조정리(Euclid's lemma)를 기반으로 합니다: 만약 $p$ 가 소수이고 $p$ 가 정수 $a$ 와 $b$ 의 곱 $ab$ 를 나누면, $p$ 는 $a$ 를 나누거나 $p$ 는 $b$ 를 나눕니다 (또는 둘 다 나눕니다).^[47] 반대로, 만약 숫자 $p$ 가 곱을 나눌 때 항상 그 곱의 적어도 하나의 인수를 나눈다는 속성을 가지고 있으면, $p$ 는 소수여야 합니다.^[48]

Infinitude

무한하게 많은 소수가 있습니다. 이것을 말하는 또 다른 방법은 다음 소수의 수열이 결코 끝나지 않는다는 것입니다:

2, 3, 5, 7, 11, 13, ...

이 명제는 고대 그리스 수학자 유클리드를 기리기 위해 유클리드의 정리(Euclid's theorem)라고 참조되는데, 왜냐하면 이 명제에 대한 첫 번째 알려진 증명이 그에게 귀속되기 때문입니다. 오일러에 의한 해석적 증명, 페르마 숫자에 기반한 골드바흐의 증명,^[49] 일반적인 토폴로지를 사용한 푸르스텐베르그의 증명,^[50] 및 쿠머의 우아한 증명을 포함하여 소수의 무한성에 대한 더 많은 증명이 알려져 있습니다.^[51]

유클리드의 증명(Euclid's proof)은 소수의 모든 각 유한 목록이 불완전하다는 것을 보여줍니다.^[52] 핵심 아이디어는 임의의 주어진 목록에서 소수를 함께 곱하고 1을 더하는 것입니다. 만약 목록이 소수 $p_{1},p_{2},\ldots ,p_{n}$ 으로 구성되면, 이것은 다음 숫자를 제공합니다:

N=1+p_{1}\cdot p_{2}\cdots p_{n}.

기본 정리에 의해, $N$ 은 하나 이상의 인수를 갖는 다음 소수 인수분해를 가집니다:

N=p'_{1}\cdot p'_{2}\cdots p'_{m}

$N$ 은 이들 각 인수로 균등하게 나눌 수 있지만, $N$ 은 주어진 목록에서 소수의 어떤 것으로 나눌 때 1의 나머지를 가지므로, $N$ 의 소수 인수 중 어느 것도 주어진 목록에 있을 수 없습니다. 모든 소수의 유한한 목록이 없기 때문에, 무한하게 많은 소수가 있어야 합니다.

가장 작은 소수의 곱에 1을 더한 숫자는 유클리드 숫자(Euclid numbers)라고 불립니다.^[53] 그것들 중 처음 5개는 소수지만, 6번째는 합성수입니다:

1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,

Formulas for primes

소수에 대한 효율적인 공식은 알려져 있지 않습니다. 예를 들어, 여러 변수에서도 소수 값만 취하는 비-상수 다항식(polynomial)은 없습니다.^[54] 어쨌든, 모든 소수 또는 소수만 인코딩하는 수많은 표현이 있습니다. 한 가지 가능한 공식은 윌슨의 정리(Wilson's theorem)를 기반으로 하고 숫자 2를 여러 번 생성하고 모든 다른 소수는 정확히 한 번 생성합니다.^[55] 역시 9개의 변수에서 디오판토스 방정식(Diophantine equations)의 집합과 다음 속성을 갖는 하나의 매개변수가 있습니다: 그 매개변수가 소수인 것과 결과 방정식의 시스템이 자연수에 걸쳐 해를 가지는 것은 필요충분 조건입니다. 이것은 모든 그것의 양수 값이 소수라는 속성을 갖는 단일 공식을 얻기 위해 사용될 수 있습니다.^[54]

소수-생성 공식의 다른 예제는 밀스의 정리(Mills' theorem)와 라이트(Wright)의 정리에서 나옵니다. 이들은 다음이 첫 번째 공식에서 임의의 자연수 $n$ 에 대해 소수이고, 두 번째 공식에서 임의의 개수의 지수임을 만족하는 실수 상수 $A>1$ 와 $\mu$ 가 있다고 주장합니다:^[56]

\left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor

여기서 $\lfloor {}\cdot {}\rfloor$ 는 해당 숫자보다 작거나 같은 가장 큰 정수, 바닥 함수(floor function)를 나타냅니다. 어쨌든, $A$ 또는 $\mu$ 의 값을 계산하기 위해 먼저 소수를 생성해야 하므로 소수를 생성하는 데는 유용하지 않습니다.^[54]

Open questions

소수에 대한 많은 추측이 제기되어 왔습니다. 종종 기본 공식을 가지고 있는, 이러한 추측 중 다수는 수십 년 동안 증명을 하지 못했습니다: 1912년부터 네 가지 란다우의 문제(Landau's problems)는 모두 아직 해결되지 않았습니다.^[57] 그들 중 하나는 2보다 큰 모든 각 짝수 정수 $n$ 은 두 소수의 합으로 쓸 수 있다고 주장하는 골드바흐의 추측입니다.^[58] 2014년 기준, 이 추측은 $n=4\cdot 10^{18}$ 까지의 모든 숫자에 대해 검증되어 왔습니다.^[59] 이것보다 더 약한 명제는, 예를 들어, 모든 각 충분하게 큰 홀수 정수는 3개의 소수의 합으로 쓸 수 있다고 말하는 비노그라도프의 정리(Vinogradov's theorem)는 입증되었습니다.^[60] 천의 정리(Chen's theorem)에 따르면 모든 각 충분하게 큰 짝수 정수는 소수와 반소수(semiprime, 소수의 곱)의 합으로 표현될 수 있습니다.^[61] 역시, 10보다 큰 임의의 짝수 정수는 6개의 소수의 합으로 쓸 수 있습니다.^[62] 그러한 질문을 연구하는 숫자 이론의 한 가지는 덧셈 숫자 이론(additive number theory)이라고 불립니다.^[63]

또 다른 유형의 문제는 연속된 소수 사이의 차이, 소수 틈(prime gaps)에 관한 것입니다. 임의적으로 큰 소수 틈의 존재는 임의의 자연수 $n$ 에 대해 수열 $n!+2,n!+3,\dots ,n!+n$ 은 $n-1$ 합성수로 구성된다고 주목함으로 알 수 있습니다.^[64] 어쨌든, 큰 소수 틈은 이 논증이 보여주는 것보다 훨씬 일찍 발생합니다.^[65] 예를 들어, 길이 8의 첫 번째 소수 틈은 소수 89와 97 사이에 있으며,^[66] $8!=40320$ 보다 훨씬 작습니다. 무한하게 많은 쌍둥이 소수(twin primes), 차이 2를 갖는 소수의 쌍이 있다고 추측됩니다; 이것이 쌍둥이 소수 추측(twin prime conjecture)입니다. 폴리냐크의 추측(Polignac's conjecture)은 더 일반적으로 모든 각 양의 정수 $k$ 에 대해 $2k$ 만큼 차이가 나는 무한하게 많은 연속 소수의 쌍이 있다고 말합니다.^[67] 안드리카의 추측(Andrica's conjecture),^[67] 브로카드의 추측(Brocard's conjecture),^[68] 르장드르의 추측(Legendre's conjecture),^[69] 및 오퍼만의 추측(Oppermann's conjecture)은^[68] 모두 1에서 $n$ 까지의 소수 사이의 가장 큰 틈이 많아야 근사적으로 ${\sqrt {n}},$ 이어야 한다는 것을 제안하며, 이는 리만 가설에서 따르는 것으로 알려진 결과이고, 반면 훨씬 더 강력한 크라메르 추측(Cramér conjecture) 집합은 $O((\log n)^{2})$ 에서 가장 큰 틈 크기를 가집니다.^[67] 소수 틈은 2개보다 많은 소수 사이의 차이에서 패턴, 소수 $k$ -튜플(prime $k$ -tuples)로 일반화될 수 있습니다. 그것들의 무한성과 밀도는 첫 번째 하디-리틀우드 추측(first Hardy–Littlewood conjecture)의 주제이며, 이는 소수가 소수 정리에 의해 주어진 밀도를 갖는 숫자의 무작위 수열과 유사하게 행동한다는 휴리스틱(heuristic)에 의해 동기가 부여될 수 있습니다.^[70]

Analytic properties

해석적 숫자 이론(Analytic number theory)은 연속 함수(continuous functions), 극한(limits), 무한 급수(infinite series), 및 무한대와 무한소(infinitesimal)의 관련된 수학의 렌즈를 통해 숫자 이론을 연구합니다.

이 연구 분야는 레온하르트 오일러(Leonhard Euler)와 그의 첫 번째 주요 결과, 바젤 문제(Basel problem)에 대한 해결책으로 시작되었습니다. 그 문제는 오늘날 리만 제타 함수(Riemann zeta function)의 값 $\zeta (2)$ 로 인식될 수 있는 무한 합 $1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots$ 의 값을 요청했습니다. 이 함수는 소수와 수학에서 가장 중요한 미해결 문제 중 하나인 리만 가설(Riemann hypothesis)과 밀접하게 연결되어 있습니다. 오일러는 $\zeta (2)=\pi ^{2}/6$ 임을 보여주었습니다.^[71] 이 숫자의 역수, $6/\pi ^{2}$ 는 넓은 범위에서 균등하게 선택된 두 개의 무작위 숫자가 상대적으로 소수(relatively prime, 공통 인수가 없음)일 극한하는 확률입니다.^[72]

얼마나 많은 소수가 주어진 큰 한계점보다 작은지에 대한 질문과 같은 큰 것에서 소수의 분포는 소수 정리(prime number theorem)에 의해 설명되지만, 효율적인 $n$ -번째 소수에 대한 공식은 알려져 있지 않습니다. 산술 진행에 대한 디리클레의 정리는, 그것의 기본 형식에서, 다음 선형 다항식이

p(n)=a+bn

상대적으로 소수 정수 $a$ 와 $b$ 와 함께 무한하게 많은 소수 값을 취합니다. 더 강한 형식의 정리는 이들 소수 값의 역수의 합이 발산하고, 같은 b를 갖는 서로 다른 선형 다항식이 근사적으로 같은 소수의 비율을 가진다는 것을 나타냅니다. 비록 고차 다항식에서 소수의 비율에 대한 추측이 공식화되었지만, 그것들은 여전히 입증되지 않았고, (정수 인수에 대해) 종종 무한하게 소수인 이차 다항식이 존재하는지 여부는 알려져 있지 않습니다.

Analytical proof of Euclid's theorem

무한하게 많은 소수가 있다는 오일러의 증명은 소수의 역수(reciprocals)의 합을 고려합니다:

{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.

오일러는 어떤 임의적인 실수 $x$ 에 대해, 이 합이 $x$ 보다 큰 소수 $p$ 가 존재한다는 것을 보여주었습니다.^[73] 이것은 무한하게 많은 소수가 있다는 것을 보여주는데, 왜냐하면 유한하게 많은 소수가 있었다면 그 합은 $x$ 마다 커지는 것이 아니라 가장 큰 소수에서 최댓값에 도달할 것이기 때문입니다. 이 합의 성장률은 메르텐스의 두 번째 정리(Mertens' second theorem)에 의해 보다 정확하게 설명됩니다.^[74] 비교를 위해, 다음 합은

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

$n$ 이 무한대로 갈 때 무한대로 증가하지 않습니다 (바젤 문제 참조). 이런 의미에서, 소수는 자연수의 제곱보다 더 자주 발생하지만, 두 집합 모두는 무한합니다.^[75] 브룬의 정리(Brun's theorem)는 쌍둥이 소수(twin primes)의 역수의 합이 유한하다고 말합니다:

\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,

브룬의 정리 때문에, 무한하게 많은 쌍둥이 소수가 존재한다는 쌍둥이 소수 추측(twin prime conjecture)을 풀기 위해 오일러의 방법을 사용할 수 없습니다.^[75]

Number of primes below a given bound

소수-세는 함수(prime-counting function) $\pi (n)$ 은 $n$ 보다 크지 않은 소수의 개수로 정의됩니다.^[76] 예를 들어 $\pi (11)=5$ 인데, 왜냐하면 11보다 작거나 같은 5개의 소수가 있기 때문입니다. 마이젤-레머 알고리듬(Meissel–Lehmer algorithm)과 같은 방법은 각 소수를 $n$ 까지 나열하는 것보다 더 빠르게 $\pi (n)$ 의 정확한 값을 계산할 수 있습니다.^[77] 소수 정리(prime number theorem)는 $\pi (n)$ 이 $n/\log n$ 에 대해 점근적이라고 명시하며, 이는 다음과 같이 표시됩니다:

\pi (n)\sim {\frac {n}{\log n}},

그리고 이는 $n$ 이 무한대로 커짐에 따라 오른쪽 분수에 대한 $\pi (n)$ 의 비율이 1에 가까워진다는 것을 의미합니다.^[78] 이것은 $n$ 보다 작은 무작위로 선택된 숫자가 소수일 가능성이 (근사적으로) $n$ 에서 자릿수의 개수에 반비례한다는 것을 의미합니다.^[79] 그것은 역시 $n$ 번째 소수는 $n\log n$ 에 비례하고^[80] 따라서 소수 틈의 평균 크기는 $\log n$ 에 비례함을 의미합니다.^[65] $\pi (n)$ 에 대한 보다 정확한 추정은 오프셋 로그 적분(offset logarithmic integral)에 의해 제공됩니다:^[78]

\pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.

Arithmetic progressions

산술 진행(arithmetic progression)은 수열에서 연속된 숫자가 모두 같은 차이를 가짐을 만족하는 유한 또는 무한 수열입니다.^[81] 이 차이는 진행의 모듈러스(modulus)라고 불립니다.^[82] 예를 들어, 다음은

3, 12, 21, 30, 39, ...,

모듈러스 9를 갖는 무한 산술 진행입니다. 산술 진행에서, 모든 숫자는 모듈러스로 나눌 때 같은 나머지를 가집니다; 이 예제에서, 그 나머지는 3입니다. 모듈러스 9와 나머지 3이 모두 3의 배수이기 때문에, 수열에서 모든 각 원소도 마찬가지입니다. 그러므로, 이 수열은 오직 하나의 소수, 3 자체만 포함합니다. 일반적으로, 다음 무한 진행은

a,a+q,a+2q,a+3q,\dots

그것의 나머지 $a$ 와 모듈러스 $q$ 가 상대적으로 소수일 경우에만 하나보다 많은 소수를 가질 수 있습니다. 만약 그것들이 상대적으로 소수이면, 산술 진행에 대한 디리클레의 정리는 진행이 무한하게 많은 소수를 포함한다고 주장합니다.^[83]

Prime numbers in arithmetic progression mod 9.

Primes in the arithmetic progressions modulo 9. Each row of the thin horizontal band shows one of the nine possible progressions mod 9, with prime numbers marked in red. The progressions of numbers that are 0, 3, or 6 mod 9 contain at most one prime number (the number 3); the remaining progressions of numbers that are 2, 4, 5, 7, and 8 mod 9 have infinitely many prime numbers, with similar numbers of primes in each progression

그린-타오 정리(Green–Tao theorem)는 소수로만 구성된 임의적으로 긴 유한 산술 진행이 있음을 보여줍니다.^[35]^[84]

Prime values of quadratic polynomials

오일러는 다음 함수가

n^{2}-n+41

$1\leq n\leq 40$ 에 대해 소수를 산출하지만, 복합수가 그것의 이후 값 중에 나타난다고 언급했습니다.^[85]^[86] 이 현상에 대한 설명에 대한 검색은 헤그너 숫자(Heegner numbers)의 심층 대수적 숫자 이론(algebraic number theory)과 클래스 숫자 문제(class number problem)로 이어졌습니다.^[87] 하디-리틀우드 추측 F는 정수 계수(coefficients)를 갖는 이차 다항식(quadratic polynomials)의 값 중 소수의 밀도를 로그 적분과 다항식 계수의 관점에서 예측합니다. 어떤 이차 다항식도 무한하게 많은 소수 값을 취하는 것으로 입증되지 않았습니다.^[88]

울람 나선(Ulam spiral)은 소수가 강조-표시된 원점을 둘러싸는 동-중심 사각형에서 나선형으로, 자연수를 이-차원 그리드에 배열합니다. 시각적으로, 소수는 다른 대각선이 아닌 특정 대각선에 모여 있는 것처럼 보이며, 이는 일부 이차 다항식이 다른 것보다 더 자주 소수 값을 취함을 시사합니다.^[88]

Zeta function and the Riemann hypothesis

1859년부터 시작된 수학에서 가장 유명한 미해결 문제 중 하나이자 밀레니엄 상 문제(Millennium Prize Problems) 중 하나는 리만 제타 함수(Riemann zeta function) ζ(s)의 영(zeros)이 어디에 있는지 묻는 리만 가설(Riemann hypothesis)입니다. 이 함수는 복소수에 대한 해석적 함수(analytic function)입니다. 실수 부분이 1보다 큰 복소수 $s$ 에 대해 그것은 모든 정수에 걸쳐 무한 합(infinite sum)과 소수에 걸쳐 무한 곱(infinite product) 모두와 같습니다:

\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.

오일러에 의해 발견된 합과 곱 사이의 이러한 상등은 오일러 곱(Euler product)이라고 불립니다.^[89] 오일러 곱은 산술의 기본 정리에서 유도될 수 있고, 제타 함수와 소수 사이의 긴밀한 연결을 보여줍니다.^[90] 그것은 무한하게 많은 소수가 있다는 또 다른 증명으로 이어집니다: 만약 오직 유한하게 많은 소수가 있으면, 합-곱 상등은 $s=1$ 에서도 유효하지만, 합은 발산할 것이고, (그것이 조화 급수(harmonic series) $1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots$ 입니다). 반면에 그 곱은 유한할 것이므로, 모순입니다.^[91]

리만 가설에 따르면 제타 함수의 영(zeros)은 모두 음의 짝수이거나, 1/2과 같은 실수 부분(real part)을 갖는 복소수입니다.^[92] 소수 정리(prime number theorem)의 원래 증명은 1과 같은 실수 부분을 갖는 영은 없다는 이 가설의 약한 형태에 기반을 두었지만,^[93]^[94] 다른 더 기본적인 증명이 발견되어 왔습니다.^[95] 소수-세는 함수는 각 항이 제타 함수의 영들 중 하나에서 오는 합으로 리만의 명시적 공식(Riemann's explicit formula)으로 표현될 수 있습니다; 이 합의 주요 항은 로그 적분이고, 남아있는 항은 합을 주 항의 위와 아래에서 변동하도록 하는 원인이 됩니다.^[96] 이런 의미에서, 영들은 소수가 얼마나 규칙적으로 분포되는지 제어합니다. 만약 리만 가설이 참이면, 이들 변동은 작을 것이고, 소수 정리에 의해 주어진 소수의 점근적 분포(asymptotic distribution)는 훨씬 더 짧은 구간 (숫자 $x$ 에 가까운 구간에 대해 $x$ 의 제곱근에 대한 길이)에서도 유지될 것입니다.^[94]

Abstract algebra

Modular arithmetic and finite fields

모듈러 산술은 모듈러스라고 불리는 자연수 $n$ 에 대해 숫자 $\{0,1,2,\dots ,n-1\}$ 만 사용함으로써 보통의 산술을 수정합니다. 임의의 다른 자연수는 $n$ 으로 나눈 후 그것의 나머지에 의해 대체함으로써 이 시스템에 매핑될 수 있습니다.^[97] 모듈러 합, 차이, 및 곱은 보통의 정수의 합, 차이, 또는 곱의 결과에 대해 나머지에 의해 같은 대체를 수행함으로써 계산됩니다.^[98] 정수의 상등은 모듈러 산술에서 합동(congruence)에 해당합니다: $x$ 와 $y$ 는 그것들이 $n$ 에 의한 나눗셈 후 같은 나머지를 가질 때 합동입니다 ( $x\equiv y$ mod $n$ 으로 씁니다).^[99] 어쨌든, 이 숫자 시스템에서, 모든 비-영 숫자에 의한 나눗셈(division)이 가능한 것과 모듈러스가 소수인 것은 필요충분 조건입니다. 예를 들어, 소수 $7$ 을 모듈러스와 함께, $3$ 에 의한 나눗셈은 가능합니다: $2/3\equiv 3{\bmod {7}}$ , 왜냐하면 양쪽 변에 $3$ 을 곱함으로써 분모를 제거하면 유효한 공식 $2\equiv 9{\bmod {7}}$ 을 제공합니다. 어쨌든, 합성수 모듈러스 6과 함께, $3$ 에 의한 나눗셈은 불가능합니다. $2/3\equiv x{\bmod {6}}$ 에 대한 유효한 해가 없습니다: $3$ 에 의해 곱함으로써 분모를 제거하면 왼쪽 변이 $2$ 가 되고 오른쪽 변은 $0$ 또는 $3$ 이 됩니다. 추상 대수학(abstract algebra)의 용어에서, 나눗셈을 수행하는 능력은 소수 모듈로 모듈러 산술이 필드(field) 또는, 더 구체적으로, 유한 필드(finite field)를 형성하는 반면 다른 모듈러스는 링(ring)만 제공하고 필드는 제공하지 않음을 의미합니다.^[100]

소수에 대한 몇 가지 정리는 모듈러 산술을 사용하여 형식화될 수 있습니다. 예를 들어, 페르마의 작은 정리(Fermat's little theorem)는 $a\not \equiv 0$ (mod $p$ )이면 $a^{p-1}\equiv 1$ (mod $p$ )이라고 말합니다.^[101] $a$ 의 모든 선택에 걸쳐 이것을 합하면 $p$ 가 소수일 때마다 유효한 다음 방정식을 제공합니다:

\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},

기가의 추측(Giuga's conjecture)에 따르면 이 방정식은 $p$ 가 소수가 되기 위한 충분 조건이기도 합니다.^[102] 윌슨의 정리(Wilson's theorem)에 따르면 정수 $p>1$ 가 소수인 것과 팩토리얼 $(p-1)!$ 이 $-1$ mod $p$ 와 합동인 것은 필요충분 조건입니다. 합성수 $\;n=r\cdot s\;$ 에 대해, 이것은 유지되지 않는데, 왜냐하면 그것의 인수 중 하나가 $n$ 과 $(n-1)!$ 둘 다를 나누고, 따라서 $(n-1)!\equiv -1{\pmod {n}}$ 가 불가능하기 때문입니다.^[103]

p-adic numbers

정수 $n$ 의 $p$ -진수 차수 $\nu _{p}(n)$ 은 $n$ 의 소수 인수분해에서 $p$ 의 사본 숫자입니다. 같은 개념은 분수 $m/n$ 의 $p$ -진수 차수를 $\nu _{p}(m)-\nu _{p}(n)$ 으로 정의함으로써 정수에서 유리수로 확장될 수 있습니다. 임의의 유리수 $q$ 의 $p$ -진수 절댓값 $|q|_{p}$ 는 그런-다음 $|q|_{p}=p^{-\nu _{p}(q)}$ 로 정의됩니다. 정수에 그것의 $p$ -진수 절댓값을 곱하면 인수분해에서 $p$ 의 인수가 취소되고, 다른 소수만 남습니다. 두 실수 사이의 거리가 그것들 거리의 절댓값에 의해 측정될 수 있는 것처럼, 두 유리수 사이의 거리는 그것들의 $p$ -진수 거리, 그것들 차이의 $p$ -진수 절댓값으로 측정될 수 있습니다. 이 거리 정의에 대해, 두 숫자는 그것들의 차이가 $p$ 의 높은 거듭제곱으로 나누어질 때 서로 가깝습니다 (그것들은 작은 거리를 가집니다). 실수가 유리수와 그 거리로부터 형성될 수 있는 것과 같은 방법으로, 완비 필드(complete field)를 형성하기 위해 여분의 극한하는 값을 더함으로써, $p$ -진수 거리를 갖는 유리수는 다른 완비 필드, $p$ -진수 숫자로 확장될 수 있습니다.^[104]^[105]

차수, 절댓값, 및 그것들로부터 파생된 완비 필드의 그림은 대수적 숫자 필드와 그것들의 평가 (필드의 곱셈 그룹에서 차수라고도 하는 전체적으로 순서화된 덧셈 그룹으로의 특정 매핑), 절댓값 (노름이라고도 하는 필드에서 실수로의 특정 곱셈 매핑),^[104] 및 장소 (완비라고도 하는 주어진 필드가 조밀한 집합인 완비 필드로의 확장)으로 일반화될 수 있습니다.^[106] 예를 들어 유리수에서 실수로의 확장은 숫자 사이의 거리가 보통 그것들 차이의 절댓값인 곳입니다. 덧셈 그룹에 대한 해당하는 매핑은 절댓값의 로그이지만, 이것이 평가의 모든 요구 사항을 충족하지는 않습니다. 오스트로우스키의 정리(Ostrowski's theorem)에 따르면, 동치의 자연적 개념까지, 그것들 차수와 절댓값을 갖는 실수와 $p$ -진수 숫자는 유일한 평가, 절댓값, 및 유리수에 대한 위치입니다.^[104] 지역적-전역적 원칙(local-global principle)은 유리수에 걸쳐 특정 문제가 그것들의 각 위치에서 해를 함께 연결함으로써 해결될 수 있도록 하며, 숫자 이론에 대한 소수의 중요성을 다시 강조합니다.^[107]

Prime elements in rings

교환 링(commutative ring)은 덧셈, 뺄셈, 및 곱셈이 정의된 대수적 구조(algebraic structure)입니다. 정수는 링이고, 정수에서 소수는 두 가지 다른 방법, 소수 원소(prime elements)와 기약 원소(irreducible elements)에서 링으로 일반화되어 왔습니다. 링 $R$ 의 원소 $p$ 는 만약 그것이 비-영이고, 곱셈의 역원을 가지지 않고 (즉, 그것이 단위가 아님), 다음 요구 사항을 충족하면 소수라고 불립니다: $p$ 가 $R$ 의 두 원소의 곱 $xy$ 를 나눌 때마다, 그것은 역시 $x$ 또는 $y$ 중 적어도 하나를 나눕니다. 원소는 만약 그것이 단위도 아니고 두 다른 비-단위 원소의 곱도 아니면 기약입니다. 정수의 링에서, 소수와 기약 원소는 같은 집합을 형성합니다:

\{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.

임의적인 링에서, 모든 소수 원소는 기약입니다. 그 전환은 일반적으로 유지되지 않지만, 고유한 인수분해 도메인(unique factorization domains)에 대해 유지됩니다.^[108]

산술의 기본 정리는 고유한 인수 분해 영역에서 (정의에 의해) 계속 유지됩니다. 그러한 도메인의 예제는 가우스 정수(Gaussian integers) $\mathbb {Z} [i]$ , $a+bi$ 형식의 복소수 링이며, 여기서 $i$ 는 허수 단위(imaginary unit)를 나타내고 $a$ 와 $b$ 는 임의적인 정수입니다. 그것의 소수 원소는 가우스 소수(Gaussian primes)로 알려져 있습니다. 정수 중에서 소수인 모든 각 숫자가 가우스 정수에서 소수로 유지되는 것은 아닙니다; 예를 들어, 숫자 2는 두 개의 가우스 소수 $1+i$ 와 $1-i$ 의 곱으로 쓸 수 있습니다. 3 mod 4와 합동인 유리수 (정수에서 소수 원소)는 가우스 소수이지만, 1 mod 4와 합동인 유리수 소수는 그렇지 않습니다.^[109] 이것은 두 제곱의 합에 대한 페르마 정리(Fermat's theorem on sums of two squares)의 결과이며, 이는 홀수 소수 $p$ 가 두 제곱의 합, $p=x^{2}+y^{2}$ 로 표현될 수 있고, 따라서 정확히 $p$ 가 1 mod 4일 때 $p=(x+iy)(x-iy)$ 로 인수화-가능이라고 말합니다.^[110]

Prime ideals

모든 각 링이 고유한 인수분해 도메인은 아닙니다. 예를 들어, 숫자 $a+b{\sqrt {-5}}$ (정수 $a$ 와 $b$ )의 링에서, 숫자 $21$ 은 두 인수분해 $21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})$ 를 가지며, 여기서 4개의 인수 중 어떤 것도 더 이상 줄일 수 있으므로, 그것은 고유한 인수분해를 가지지 않습니다. 고유 인수분해를 더 큰 링 클래스로 확장하기 위해, 숫자의 개념은 아이디얼(ideal), 그것의 원소 쌍의 모든 합과 링 원소를 갖는 그것의 원소의 모든 곱을 포함하는 링의 원소의 부분집합으로 대체될 수 있습니다. 소수 원소에 의해 생성된 주요 아이디얼이 소수 아이디얼이라는 의미에서 소수 원소를 일반화한 소수 아이디얼(Prime ideals)은 교환 대수, 대수적 숫자 이론, 및 대수적 기하학에서 중요한 연구 도구이자 연구 대상입니다. 정수의 링의 소수 아이디얼은 아이디얼 (0), (2), (3), (5), (7), (11), ...입니다. 산술의 기본 정리는 라이커-뇌터 정리(Lasker-Noether theorem)로 일반화하며, 이는 뇌터 교환 링의 모든 각 아이디얼을 소수 거듭제곱(prime powers)의 적절한 일반화인 으뜸 아이디얼(primary ideals)의 교차점으로 표현합니다.^[111]

링의 스펙트럼(spectrum of a ring)은 그 점이 링의 소수 아이디얼인 기하학적 공간입니다.^[112] 산술 기하학(Arithmetic geometry)도 이 개념의 이점을 누리고, 기하학과 숫자 이론 둘 다에서 많은 개념이 존재합니다. 예를 들어, 대수적 숫자 이론의 기본 문제인 확장 필드(extension field)로 들어 올릴 때 소수 아이디얼의 인수분해 또는 분기(ramification)는 기하학에서 분기(ramification in geometry)와 어느 정도 유사합니다. 이들 개념은 정수에만 관련된 숫자-이론적 질문에도 도움이 될 수 있습니다. 예를 들어, 이차 숫자 필드의 정수의 링에서 소수 아이디얼은 제곱근 모듈로 정수 소수의 존재와 관련된 명제인 이차 상호관계(quadratic reciprocity)를 증명하는 데 사용될 수 있습니다.^[113] 페르마의 마지막 정리(Fermat's Last Theorem)를 입증하기 위한 초기 시도는 쿠머(Kummer)의 정규 소수(regular primes), 원분 정수(cyclotomic integers)에서 고유 인수분해의 실패로 연결된 정수 소수의 도입으로 이어졌습니다.^[114] 대수적 숫자 필드에서 여러 소수 아이디얼의 곱에 얼마나 많은 정수 소수 인수가 포함되는지에 대한 질문은 체브타로프의 밀도 정리(Chebotarev's density theorem)에 의해 다루어지며, 이는 (원분 정수에 적용될 때) 특별한 경우로 산술 진행에서 소수에 대한 디리클레의 정리를 가집니다.^[115]

Group theory

유한 그룹(finite groups) 이론에서. 쉴로브 정리(Sylow theorems)는 소수 $p^{n}$ 의 거듭제곱이 그룹의 차수를 나누면, 그 그룹이 차수 $p^{n}$ 의 부분그룹을 가진다는 것을 의미합니다. 라그랑주의 정리(Lagrange's theorem)에 의해, 소수 차수의 임의의 그룹은 순환 그룹(cyclic group)이고, 번사이드의 정리(Burnside's theorem)에 의해, 그 차수가 두 개의 소수로만 나누어지는 임의의 그룹은 해결-가능(solvable)입니다.^[116]

Computational methods

오랫동안, 일반적으로 숫자 이론과 특히 소수에 대한 연구는 마모를 균등하게 분배하기 위해 소수를 매진 기어 이빨을 사용하는 것 외에는 수학 이외의 응용을 갖지 않는^[b] 순수 수학의 정식 사례로 여겨졌습니다.^[117] 특히, 영국의 수학자 G. H. 하디(G. H. Hardy)와 같은 숫자 이론자들은 군사적 의미가 전혀 없는 일을 했다고 자부했습니다.^[118]

숫자 이론의 순수성에 대한 이러한 전망은 1970년대, 소수가 공개-키 암호화(public-key cryptography) 알고리듬 생성에 대해 기초로 사용될 수 있다고 공개적으로 발표되었을 때 산산조각이 났습니다.^[32] 이러한 응용은 소수로 계산하는 데 알고리듬(algorithms)과 특히 주어진 숫자가 소수인지 여부를 결정하는 방법인 소수성 테스트(primality testing)에 대한 중요한 연구로 이어져 왔습니다. 가장 기본적인 소수성 테스트 루틴, 나눗셈 시도는 너무 느려서 큰 숫자에 유용하지 않습니다. 현대 소수성 테스트 중 하나의 그룹은 임의적인 숫자에 적용할 수 있는 반면 더 효율적인 테스트는 여러 특수 유형에 사용할 수 있습니다. 대부분의 소수성 테스트는 인수가 소수인지 여부만 알려줍니다. 역시 합성수 인수의 소수 인수 (또는 그것의 모든 소수 인수)를 제공하는 루틴은 인수분해(factorization) 알고리듬이라고 불립니다. 소수는 체크섬, 해시 테이블, 및 유사-무작위 숫자 생성기 계산에도 사용됩니다.

Trial division

주어진 정수 $n$ 의 소수성을 확인하는 가장 기본적인 방법은 시도 나눗셈(trial division)이라고 불립니다. 이 방법은 $n$ 을 2에서 $n$ 의 제곱근(square root)까지의 각 정수로 나눕니다. $n$ 을 나누는 임의의 그러한 정수는 $n$ 을 복합수로 균등하게 설정합니다; 그렇지 않으면 그것은 소수입니다. 제곱근보다 큰 정수는 $n=a\cdot b$ 일 때마다, 두 인수 $a$ 와 $b$ 중 하나가 $n$ 의 제곱근보다 작거나 같기 때문에 확인할 필요가 없습니다. 또 다른 최적화는 이 범위에서 인수로 소수만 확인하는 것입니다.^[119] 예를 들어, 37이 소수인지 확인하기 위해, 이 방법은 2에서 ${\sqrt {37}}$ 까지의 범위에 있는 소수인 2, 3, 및 5로 그것을 나눕니다. 각 나눗셈은 비-영 나머지를 생성하므로, 37은 실제로 소수입니다.

비록 이 방법이 설명하기 간단하지만, 그것이 수행하는 테스트의 숫자가 이들 정수의 자릿수의 개수의 함수로 지수적으로 성장하기 때문에 큰 정수의 소수성을 테스트하는 데는 비실용적입니다.^[120] 어쨌든, 이 필터를 통과하는 숫자에 대한 더 복잡한 방법을 사용하기 전에, 작은 인수를 갖는 합성수를 빠르게 발견하기 위해, 약수 크기의 제곱근보다 더 작은 극한으로 시도 나눗셈이 여전히 사용됩니다.^[121]

Sieves

Animation of the sieve of Eratosthenes — The sieve of Eratosthenes starts with all numbers unmarked (gray). It repeatedly finds the first unmarked number, marks it as prime (dark colors) and marks its square and all later multiples as composite (lighter colors). After marking the multiples of 2 (red), 3 (green), 5 (blue), and 7 (yellow), all primes up to the square root of the table size have been processed, and all remaining unmarked numbers (11, 13, etc.) are marked as primes (magenta).

컴퓨터 이전에, 주어진 한계까지 모든 소수 또는 소수 인수분해를 나열하는 수학 테이블이 공통적으로 인쇄되었습니다.^[122] 소수 목록을 생성하는 가장 오래된 방법은 에라토스테네스의 체라고 불립니다.^[123] 애니메이션은 이 방법의 최적화된 변형을 보여줍니다.^[124] 같은 문제에 대해 점근적으로 효율적인 또 다른 체질 방법은 앳킨의 체(sieve of Atkin)입니다.^[125] 고급 수학에서, 체 이론(sieve theory)은 다른 문제에 유사한 방법을 적용합니다.^[126]

Primality testing versus primality proving

임의적인 주어진 숫자 $n$ 이 소수인지 여부에 대한 가장 빠른 최신 테스트 중 일부는 확률론적 (또는 몬테 카를로) 알고리듬이며, 그것들은 잘못된 답을 생성할 작은 무작위 기회가 있음을 의미합니다.^[127] 예를 들어, 주어진 숫자 $p$ 에 대한 솔로베이-스트라센 소수성 테스트(Solovay–Strassen primality test)는 $2$ 에서 $p-2$ 까지 무작위로 숫자 $a$ 를 선택하고 $a^{(p-1)/2}\pm 1$ 가 $p$ 로 나누어지는지 여부를 확인하기 위해 모듈러 지수(modular exponentiation)를 사용합니다.^[c] 만약 그렇다면 예라고 대답하고 그렇지 않으면 아니오라고 대답합니다. 만약 $p$ 가 실제로 소수이면, 그것은 항상 예라고 답하지만, $p$ 가 합성수이면 많아야 1/2의 확률로 예라고 답하고 적어도 1/2의 확률로 아니오라고 답합니다.^[128] 이 테스트를 같은 숫자에 대해 $n$ 번 반복하면, 합성수가 매번 테스트를 통과할 확률은 최대 $1/2^{n}$ 입니다. 이는 테스트 횟수에 따라 지수적으로 감소하기 때문에, 그것은 반복 테스트를 통과한 숫자가 소수라는 (확실하지는 않지만) 높은 신뢰도를 제공합니다. 다른 한편, 만약 테스트가 실패하면, 그 숫자는 확실히 합성수입니다.^[129] 그러한 테스트를 통과한 합성수는 유사소수(pseudoprime)라고 불립니다.^[128]

대조적으로, 일부 다른 알고리듬은 답변이 항상 정확함을 보장합니다: 소수는 항상 소수로 결정되고 합성수는 항상 합성수로 결정됩니다. 예를 들어, 이것은 시도 나눗셈에 해당됩니다. 올바른 출력이 보장된 알고리듬은 AKS 소수성 테스트(AKS primality test)와 같은 결정론적 (비-무작위) 알고리듬과^[130] 알고리듬에 의한 만들어진 무작위 선택이 타원 곡선 소수성 증명(elliptic curve primality proving)의 일부 변형과 같은 최종 답에 영향을 미치지 않는 무작위 라스베이거스 알고리듬 둘 다를 포함합니다.^[127] 곡선 소수성 증명. 타원 곡선 방법은 숫자가 소수라는 결론을 내릴 때, 빠르게 검증될 수 있는 소수성 증명서(primality certificate)를 제공합니다.^[131] 타원 곡선 소수성 테스트는 정확성이 보장된 소수성 테스트 중에서 가장 빠른 것이지만, 그것의 실행-시간 분석은 엄격한 증명이 아닌 휴리스틱 논증(heuristic arguments)을 기반으로 합니다. AKS 소수성 테스트(AKS primality test)는 수학적으로 입증된 시간 복잡성을 가지고 있지만, 실제로 타원 곡선 소수성 증명보다 느립니다.^[132] 이들 방법은 소수를 찾을 때까지 무작위 숫자를 생성하고 테스트함으로써 큰 무작위 소수를 생성하기 위해 사용될 수 있습니다; 이것을 수행할 때, 더 빠른 확률론적 테스트는 보장된 올바른 알고리듬이 남아있는 숫자가 소수인지 확인하기 위해 사용되기 전에 대부분의 합성수를 빠르게 제거할 수 있습니다.^[d]

다음 테이블은 이들 테스트 중 일부를 나열하고 있습니다. 실행 시간은 테스트할 숫자인 $n$ 과, 확률 알고리듬에 대해, 수행된 테스트의 숫자 $k$ 의 함으로 표시됩니다. 게다가, $\varepsilon$ 는 임의적으로 작은 양수이고, log는 불특정 밑수의 로그(logarithm)입니다. 큰 O 표기법(big O notation)은 무차원 단위에서 시간의 단위로 그것을 변환하기 위해 각 시간 범위에 상수 인수를 곱해야 함을 의미합니다; 이 인수는 알고리듬을 실행하기 위해 사용되는 컴퓨터 유형과 같은 구현 세부 사항에 따라 다르지만, 입력 매개변수 $n$ 과 $k$ 에 의존하지 않습니다.

Test	Developed in	Type	Running time	Notes	References
AKS primality test	2002	deterministic	$O((\log n)^{6+\varepsilon })$		^[130]^[133]
Elliptic curve primality proving	1986	Las Vegas	$O((\log n)^{4+\varepsilon })$ heuristically		^[132]
Baillie–PSW primality test	1980	Monte Carlo	$O((\log n)^{2+\varepsilon })$		^[134]^[135]
Miller–Rabin primality test	1980	Monte Carlo	$O(k(\log n)^{2+\varepsilon })$	error probability $4^{-k}$	^[136]
Solovay–Strassen primality test	1977	Monte Carlo	$O(k(\log n)^{2+\varepsilon })$	error probability $2^{-k}$	^[136]

Special-purpose algorithms and the largest known prime

임의의 자연수에 적용되는 앞서 언급한 테스트 외에도, 특수 형식의 일부 숫자는 소수성에 대해 더 빠르게 테스트될 수 있습니다. 예를 들어, 루카스-레머 소수성 테스트(Lucas–Lehmer primality test)는 메르센 숫자(Mersenne number, 2의 거듭제곱보다 1 작은 숫자)가 결정론적으로 소수인지 여부를 밀러-라빈 테스트의 단일 반복과 동시에 결정할 수 있습니다.^[137] 이것이 1992년 이후(2018년 12월 기준) 가장 큰 알려진 소수가 항상 메르센 소수인 이유입니다.^[138] 무한하게 많은 메르센 소수는 있다고 추측하고 있습니다.^[139]

다음 테이블은 다양한 유형의 가장 큰 알려진 소수를 제공합니다. 이들 소수 중 일부는 분산 컴퓨팅을 사용하여 발견되어 왔습니다. 2009년에, Great Internet Mersenne Prime Search 프로젝트는 최소 1,000만 자릿수를 갖는 소수를 처음 발견한 사람에게 미국 달러 100,000의 상금을 수여했습니다.^[140] Electronic Frontier Foundation은 역시 최소 1억 자릿수와 10억 자릿수를 갖는 소수에 대해 각각 15만 달러와 25만 달러를 제공합니다.^[141]

Type	Prime	Number of decimal digits	Date	Found by
Mersenne prime	2^82,589,933 − 1	24,862,048	December 7, 2018^[1]	Patrick Laroche, Great Internet Mersenne Prime Search
Proth prime	10,223 × 2^31,172,165 + 1	9,383,761	October 31, 2016^[142]	Péter Szabolcs, PrimeGrid^[143]
factorial prime	208,003! − 1	1,015,843	July 2016	Sou Fukui^[144]
primorial prime^[e]	1,098,133# − 1	476,311	March 2012	James P. Burt, PrimeGrid^[146]
twin primes	2,996,863,034,895 × 2^1,290,000 ± 1	388,342	September 2016	Tom Greer, PrimeGrid^[147]

Integer factorization

합성 정수 $n$ 이 주어지면, 하나 (또는 모든) 소수 인수를 제공하는 임무는 $n$ 의 인수분해(factorization)라고 참조됩니다. 그것은 소수성 테스트보다 훨씬 어렵고,^[148] 비록 많은 인수분해 알고리듬이 알려져 있지만, 그것들은 가장 빠른 소수성 테스트 방법보다 느립니다. 시도 나눗셈과 폴라드의 로우 알고리듬(Pollard's rho algorithm)은 $n$ 의 매우 작은 인수를 찾기 위해 사용될 수 있고,^[121] 타원 곡선 인수분해(elliptic curve factorization)는 $n$ 이 적당한 크기의 인수를 가질 때 효과적일 수 있습니다.^[149] 인수의 크기에 의존하지 않는 임의적으로 큰 숫자에 적합한 방법은 이차 체(quadratic sieve)와 일반적인 숫자 필드 체(general number field sieve)를 포함합니다. 소수성 테스트와 마찬가지로, 그것들의 입력을 특수 숫자 필드 체(special number field sieve)를 포함하여 특수 형식을 갖도록 요구하는 인수분해 알고리듬도 있습니다.^[150] 2019년 12월 기준, 일반적인-목적 알고리듬에 의해 인수화된 것으로 알려진 가장 큰 숫자는 RSA-240으로, 240개의 십진 자릿수 (795비트)이고 두 개의 큰 소수의 곱입니다.^[151]

쇼어의 알고리듬(Shor's algorithm)은 양자 컴퓨터에서 단계의 다항식 숫자에서 임의의 정수를 인수화할 수 있습니다.^[152] 어쨌든, 현재 기술은 매우 작은 숫자에 대해서만 이 알고리듬을 실행할 수 있습니다. 2012년 10월 기준, 쇼어의 알고리듬을 실행하는 양자 컴퓨터에 의해 인수화된 가장 큰 숫자는 21입니다.^[153]

Other computational applications

RSA와 디피–헬먼 키 교환(Diffie–Hellman key exchange)과 같은 여러 공개-키 암호화(public-key cryptography) 알고리듬은 큰 소수 (2048-비트 소수가 공통적임)를 기반으로 합니다.^[154] RSA는 곱 $xy$ 만 알려져 있으면 $x$ 와 $y$ (서로소로 가정됨)를 계산하는 것보다 두 개의 (큰) 숫자 $x$ 와 $y$ 의 곱셈을 수행하는 것이 훨씬 더 쉽다 (즉, 더 효율적)는 가정에 의존합니다.^[32] 디피-헬면 키 교환은 모듈러 지수 ( $a^{b}{\bmod {c}}$ 를 계산)를 위한 효율적인 알고리듬이 있다는 사실에 의존하고, 반면에 역 연산 (이산 로그)은 어려운 문제로 생각됩니다.^[155]

소수는 해시 테이블에 자주 사용됩니다. 예를 들어 보편적 해싱(universal hashing)을 위한 Carter와 Wegman의 원래 방법은 무작위 선형 함수(linear functions) 모듈로 큰 소수를 선택함으로써 컴퓨팅 해시 함수(hash functions)를 기반으로 했습니다. Carter와 Wegman은 이 방법을 더 높은 차수의 다항식, 다시 모듈로 큰 소수를 사용함으로써 $k$ -독립적 해싱으로 일반화했습니다.^[156] 해시 함수뿐만 아니라, 조사 수열(probe sequence)가 전체 테이블을 덮음을 보장하기 위해 해시 테이블에 기반을 둔 이차 조사(quadratic probing)에서 해시 테이블 크기에 소수가 사용됩니다.^[157]

일부 체크섬 방법은 소수의 수학을 기반으로 합니다. 예를 들어, 국제 표준 도서 번호에 사용되는 체크섬은 숫자 모듈로 11의 나머지 부분을 소수로 취함으로써 정의됩니다. 11이 소수이기 때문에, 이 방법은 단일-자릿수 오류와 인접한 자릿수의 전치를 모두 감지할 수 있습니다.^[158] 또 다른 체크섬 방법, Adler-32는 $2^{16}$ 보다 작은 가장 큰 소수인 산술 모듈로 65521을 사용합니다.^[159] 소수는 역시 선형 합동 생성기(linear congruential generators)^[160] 및 메르센 트위스트(Mersenne Twister)를 포함한 유사-무작위 숫자 생성기에서 사용됩니다.^[161]

Other applications

소수는 숫자 이론에서 중심적으로 중요하지만 역시 추상 대수학과 기본 기하학을 포함하여 수학 내의 다른 영역에서 많이 응용을 가집니다. 예를 들어, 이-차원 격자에서 점의 소수를 배치하여 한 줄에 3개가 없도록 하거나, 3개의 점으로 구성된 모든 각 삼각형이 큰 넓이를 가지도록 할 수 있습니다.^[162] 또 다른 예제는 아이젠슈타인의 기준(Eisenstein's criterion)으로, 다항식이 소수와 그것의 제곱에 의해 그 계수의 나눔가능성을 기반으로 하는 기약 여부에 대한 테스트입니다.^[163]

소수의 개념은 매우 중요하여 다양한 수학 가지에서 다양한 방법으로 일반화되었습니다. 일반적으로, "소수"는 적절한 의미에서 최소성 또는 비-분해가능성을 나타냅니다. 예를 들어, 주어진 필드의 소수 필드(prime field)는 0과 1을 모두 포함하는 가장 작은 부분필드입니다. 그것은 유리수의 필드이거나 원소의 소수를 갖는 유한 필드(finite field)입니다.^[164] 종종 두 번째, 추가적인 의미는 소수라는 단어를 사용함으로써 의도되며, 즉, 임의의 대상은 본질적으로 고유하게 소수 구성 요소로 분해될 수 있습니다. 예를 들어, 매듭 이론(knot theory)에서, 소수 매듭(prime knot)은 두 개의 비-자명한 매듭의 연결된 합(connected sum)으로 쓸 수 없다는 의미에서 분해할 수 없는 매듭입니다. 임의의 매듭은 소수 매듭의 연결된 합으로 고유하게 표현될 수 있습니다.^[165] 3-매니폴드의 소수 분해는 이러한 유형의 또 다른 예입니다.^[166]

수학과 컴퓨팅을 넘어, 소수는 양자 역학과 잠재적인 연관성을 가지고, 예술과 문학에서 은유적으로 사용되어 왔습니다. 그것들은 역시 진화 생물학(evolutionary biology)에서 매미의 수명 주기를 설명하는 데 사용되어 왔습니다.

Constructible polygons and polygon partitions

Construction of a regular pentagon using straightedge and compass. This is only possible because 5 is a Fermat prime.

페르마 소수(Fermat primes)는 비-음의 정수(nonnegative integer) $k$ 를 갖는 다음 형식의 소수입니다:^[167]

F_{k}=2^{2^{k}}+1,

그것들은 모든 그러한 숫자는 소수라고 추측한 피에르 드 페르마(Pierre de Fermat)의 이름을 따서 지어졌습니다. 이들 숫자 중 처음 다섯 개 – 3, 5, 17, 257, 및 65,537 – 는 소수이지만,^[168] $F_{5}$ 는 합성수이고 따라서 2017년 기준 검증된 모든 다른 페르마 숫자도 마찬가지입니다.^[169] 정규 $n$ -각형은 직선자와 컴퍼스를 사용하여 구성-가능한 것과 $n$ 의 홀수 소수 인수 (어떤 것이라도 있다면)가 서로 다른 페르마 소수인 것은 필요충분 조건입니다.^[168] 마찬가지로, 정규 $n$ -각형은 직선자, 컴퍼스, 및 각도 삼등분선을 사용하여 구성될 수 있는 것과 $n$ 의 소수 인수가 2 또는 3의 사본의 임의의 개수와 함께 (비어 있을 수 있음) 구별되는 피어폰트 소수(Pierpont primes), $2^{a}3^{b}+1$ 형식의 소수의 집합은 필요충분 조건입니다.^[170]

$n$ 이 소수의 거듭제곱일 때 임의의 볼록 다각형을 넓이와 둘레가 같은 $n$ 개의 더 작은 볼록 다각형으로 분할할 수 있지만, 다른 $n$ 의 값에 대해서는 알 수 없습니다.^[171]

Quantum mechanics

1970년대 휴 몽고메리(Hugh Montgomery)와 프리먼 다이슨(Freeman Dyson)의 연구로 시작하여, 수학자와 물리학자들은 리만 제타 함수의 영들이 양자 시스템(quantum systems)의 에너지 수준과 연결되어 있다고 추측했습니다.^[172]^[173] 소수는 역시 양자 정보 과학(quantum information science)에서 중요하며, 서로 불편향된 기저(mutually unbiased bases)와 대칭 정보적으로 완비 양의-연산자-값 측정(symmetric informationally complete positive-operator-valued measures)과 같은 수학적 구조 덕분입니다.^[174]^[175]

Biology

Magicicada 속의 매미에 의해 사용되는 진화 전략은 소수를 사용합니다.^[176] 이들 곤충들은 대부분의 삶을 지하에서 땅벌레로 보냅니다. 그들은 번데기가 된 다음 7, 13, 또는 17년 후에 굴에서 나오며, 그 시점에서 날아다니고 번식하고, 그런-다음 기껏해야 몇 주 후에 죽습니다. 생물학자들은 포식자가 이들 주기와 동기화되는 것을 방지하기 위해 이들 소수 번식 주기 길이가 진화했다고 이론화합니다.^[177]^[178] 대조적으로, 대나무 식물에서 개화 사이의 다년 기간은 그것들의 인수분해에서 작은 소수만 가지는 매끄러운 숫자(smooth numbers)로 가설됩니다.^[179]

Arts and literature

소수는 많은 예술가와 작가에게 영향을 미쳤습니다. 프랑스 작곡가 올리비에 메시앙(Olivier Messiaen)은 소수를 "자연 현상"을 통해 비대칭 음악을 만들기 위해 사용했습니다. La Nativité du Seigneur (1935) 및 Quatre études de rythme (1949–50)과 같은 작품에서, 그는 예측할 수 없는 리듬을 만들기 위해 서로 다른 소수로 길이가 지정된 모티프를 동시에 사용합니다: 소수 41, 43, 47, 및 53은 세 번째 에뛰드, "Neumes rythmiques"에서 나타납니다. 메시앙에 따르면 이러한 작곡 방식은 "자연의 움직임, 자유롭고 불평등한 기간의 움직임에서 영감을 받았습니다".^[180]

그의 SF 소설 Contact에서, 과학자 Carl Sagan은 소수 인수분해가 외계인과의 통신에서 이-차원 이미지 평면을 설정하는 수단으로 사용될 수 있다고 제안했으며, 이는 그가 1975년에 미국 천문학자 Frank Drake와 함께 비공식적으로 처음 개발한 아이디어입니다.^[181] Mark Haddon에 의한 소설 The Curious Incident of the Dog in the Night-Time에서, 내레이터는 아스퍼거 증후군(Asperger syndrome)을 앓고 있는 수학에 재능이 있는 10대 주인공의 정신 상태를 전달하기 위해 연속적인 소수로 이야기의 섹션을 배열합니다.^[182] 소수는 Paolo Giordano 소설 The Solitude of Prime Numbers에서 외로움과 고립에 대한 은유로 사용되며, 이것에서 그것들은 정수 사이에서 "외부인"으로 묘사됩니다.^[183]

Notes

^ A 44-digit prime number found in 1951 by Aimé Ferrier with a mechanical calculator remains the largest prime not to have been found with the aid of electronic computers.^[28]
^ ^a ^b For instance, Beiler writes that number theorist Ernst Kummer loved his ideal numbers, closely related to the primes, "because they had not soiled themselves with any practical applications",^[30] and Katz writes that Edmund Landau, known for his work on the distribution of primes, "loathed practical applications of mathematics", and for this reason avoided subjects such as geometry that had already shown themselves to be useful.^[31]
^ In this test, the $\pm 1$ term is negative if $a$ is a square modulo the given (supposed) prime $p$ , and positive otherwise. More generally, for non-prime values of $p$ , the $\pm 1$ term is the (negated) Jacobi symbol, which can be calculated using quadratic reciprocity.
^ Indeed, much of the analysis of elliptic curve primality proving is based on the assumption that the input to the algorithm has already passed a probabilistic test.^[131]
^ The primorial function of $n$ , denoted by $n\#$ , yields the product of the prime numbers up to $n$ , and a primorial prime is a prime of one of the forms $n\#\pm 1$ .^[145]

References

^ ^a ^b "GIMPS Project Discovers Largest Known Prime Number: 2^82,589,933-1". Mersenne Research, Inc. 21 December 2018. Retrieved 21 December 2018.
^ Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. p. 26. ISBN 978-0-19-850105-3.
^ Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd ed.). Routledge. p. 62. ISBN 978-1-136-63662-2.
^ Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. p. 16. OCLC 6975809.
^ Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. p. 360. ISBN 978-0-7641-0768-9.
^ Dudley, Underwood (1978). "Section 2: Unique factorization". Elementary number theory (2nd ed.). W.H. Freeman and Co. p. 10. ISBN 978-0-7167-0076-0.
^ Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. Vol. 31 (2nd ed.). Elsevier. p. 113. ISBN 978-0-08-096019-7.
^ ^a ^b Ziegler, Günter M. (2004). "The great prime number record races". Notices of the American Mathematical Society. 51 (4): 414–416. MR 2039814.
^ Stillwell, John (1997). Numbers and Geometry. Undergraduate Texts in Mathematics. Springer. p. 9. ISBN 978-0-387-98289-2.
^ Sierpiński, Wacław (1964). A Selection of Problems in the Theory of Numbers. New York: Macmillan. p. 40. MR 0170843.
^ Nathanson, Melvyn B. (2000). "Notations and Conventions". Elementary Methods in Number Theory. Graduate Texts in Mathematics. Vol. 195. Springer. ISBN 978-0-387-22738-2. MR 1732941.
^ Faticoni, Theodore G. (2012). The Mathematics of Infinity: A Guide to Great Ideas. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Vol. 111 (2nd ed.). John Wiley & Sons. p. 44. ISBN 978-1-118-24382-4.
^ Bruins, Evert Marie, review in Mathematical Reviews of Gillings, R.J. (1974). "The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?". Archive for History of Exact Sciences. 12 (4): 291–298. doi:10.1007/BF01307175. MR 0497458. S2CID 121046003.
^ ^a ^b Stillwell, John (2010). Mathematics and Its History. Undergraduate Texts in Mathematics (3rd ed.). Springer. p. 40. ISBN 978-1-4419-6052-8.
^ ^a ^b Pomerance, Carl (December 1982). "The Search for Prime Numbers". Scientific American. 247 (6): 136–147. Bibcode:1982SciAm.247f.136P. doi:10.1038/scientificamerican1282-136. JSTOR 24966751.
^ ^a ^b ^c ^d Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.
^ O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews.
^ Sandifer 2007, 8. Fermat's Little Theorem (November 2003), p. 45
^ Sandifer, C. Edward (2014). How Euler Did Even More. Mathematical Association of America. p. 42. ISBN 978-0-88385-584-3.
^ Koshy, Thomas (2002). Elementary Number Theory with Applications. Academic Press. p. 369. ISBN 978-0-12-421171-1.
^ Yuan, Wang (2002). Goldbach Conjecture. Series In Pure Mathematics. Vol. 4 (2nd ed.). World Scientific. p. 21. ISBN 978-981-4487-52-8.
^ Narkiewicz, Wladyslaw (2000). "1.2 Sum of Reciprocals of Primes". The Development of Prime Number Theory: From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics. Springer. p. 11. ISBN 978-3-540-66289-1.
^ Tchebychev, P. (1852). "Mémoire sur les nombres premiers" (PDF). Journal de mathématiques pures et appliquées. Série 1 (in French): 366–390.. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854
^ Apostol, Tom M. (2000). "A centennial history of the prime number theorem". In Bambah, R.P.; Dumir, V.C.; Hans-Gill, R.J. (eds.). Number Theory. Trends in Mathematics. Basel: Birkhäuser. pp. 1–14. MR 1764793.
^ Apostol, Tom M. (1976). "7. Dirichlet's Theorem on Primes in Arithmetical Progressions". Introduction to Analytic Number Theory. New York; Heidelberg: Springer-Verlag. pp. 146–156. MR 0434929.
^ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer. p. 261. ISBN 978-3-642-18192-4.
^ Rosen, Kenneth H. (2000). "Theorem 9.20. Proth's Primality Test". Elementary Number Theory and Its Applications (4th ed.). Addison-Wesley. p. 342. ISBN 978-0-201-87073-2.
^ Cooper, S. Barry; Hodges, Andrew (2016). The Once and Future Turing. Cambridge University Press. pp. 37–38. ISBN 978-1-107-01083-3.
^ Rosen 2000, p. 245.
^ Beiler, Albert H. (1999) [1966]. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. Dover. p. 2. ISBN 978-0-486-21096-4. OCLC 444171535.
^ Katz, Shaul (2004). "Berlin roots – Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem". Science in Context. 17 (1–2): 199–234. doi:10.1017/S0269889704000092. MR 2089305. S2CID 145575536.
^ ^a ^b ^c Kraft, James S.; Washington, Lawrence C. (2014). Elementary Number Theory. Textbooks in mathematics. CRC Press. p. 7. ISBN 978-1-4987-0269-0.
^ Bauer, Craig P. (2013). Secret History: The Story of Cryptology. Discrete Mathematics and Its Applications. CRC Press. p. 468. ISBN 978-1-4665-6186-1.
^ Klee, Victor; Wagon, Stan (1991). Old and New Unsolved Problems in Plane Geometry and Number Theory. Dolciani mathematical expositions. Vol. 11. Cambridge University Press. p. 224. ISBN 978-0-88385-315-3.
^ ^a ^b Neale 2017, pp. 18, 47.
^ ^a ^b Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). "The history of the primality of one: a selection of sources". Journal of Integer Sequences. 15 (9): Article 12.9.8. MR 3005523. For a selection of quotes from and about the ancient Greek positions on the status of 1 and 2, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.
^ Tarán, Leonardo (1981). Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary. Philosophia Antiqua : A Series of Monographs on Ancient Philosophy. Vol. 39. Brill. pp. 35–38. ISBN 978-90-04-06505-5.
^ Caldwell et al. 2012, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.
^ Caldwell et al. 2012, p. 15.
^ ^a ^b ^c Caldwell, Chris K.; Xiong, Yeng (2012). "What is the smallest prime?" (PDF). Journal of Integer Sequences. 15 (9): Article 12.9.7. MR 3005530.
^ Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (2nd ed.). Basel, Switzerland: Birkhäuser. p. 36. doi:10.1007/978-1-4612-0251-6. ISBN 978-0-8176-3743-9. MR 1292250.
^ ^a ^b Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers. New York: Copernicus. pp. 129–130. doi:10.1007/978-1-4612-4072-3. ISBN 978-0-387-97993-9. MR 1411676.
^ For the totient, see Sierpiński 1988, p. 245. For the sum of divisors, see Sandifer, C. Edward (2007). How Euler Did It. MAA Spectrum. Mathematical Association of America. p. 59. ISBN 978-0-88385-563-8.
^ Smith, Karl J. (2011). The Nature of Mathematics (12th ed.). Cengage Learning. p. 188. ISBN 978-0-538-73758-6.
^ Dudley 1978, Section 2, Theorem 2, p. 16; Neale, Vicky (2017). Closing the Gap: The Quest to Understand Prime Numbers. Oxford University Press. p. 107. ISBN 978-0-19-109243-5.
^ du Sautoy, Marcus (2003). The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. Harper Collins. p. 23. ISBN 978-0-06-093558-0.
^ Dudley 1978, Section 2, Lemma 5, p. 15; Higgins, Peter M. (1998). Mathematics for the Curious. Oxford University Press. pp. 77–78. ISBN 978-0-19-150050-3.
^ Rotman, Joseph J. (2000). A First Course in Abstract Algebra (2nd ed.). Prentice Hall. Problem 1.40, p. 56. ISBN 978-0-13-011584-3.
^ Letter in Latin from Goldbach to Euler, July 1730.
^ Furstenberg, Harry (1955). "On the infinitude of primes". American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.
^ Ribenboim, Paulo (2004). The little book of bigger primes. Berlin; New York: Springer-Verlag. p. 4. ISBN 978-0-387-20169-6.
^ Euclid's Elements, Book IX, Proposition 20. See David Joyce's English translation of Euclid's proof or Williamson, James (1782). The Elements of Euclid, With Dissertations. Oxford: Clarendon Press. p. 63. OCLC 642232959.
^ Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. pp. 82–89. ISBN 978-0-201-52989-0.
^ ^a ^b ^c Matiyasevich, Yuri V. (1999). "Formulas for prime numbers". In Tabachnikov, Serge (ed.). Kvant Selecta: Algebra and Analysis. Vol. II. American Mathematical Society. pp. 13–24. ISBN 978-0-8218-1915-9.
^ Mackinnon, Nick (June 1987). "Prime number formulae". The Mathematical Gazette. 71 (456): 113–114. doi:10.2307/3616496. JSTOR 3616496. S2CID 171537609.
^ Wright, E.M. (1951). "A prime-representing function". American Mathematical Monthly. 58 (9): 616–618. doi:10.2307/2306356. JSTOR 2306356.
^ Guy 2013, p. vii.
^ Guy 2013, C1 Goldbach's conjecture, pp. 105–107.
^ Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014). "Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$ ". Mathematics of Computation. 83 (288): 2033–2060. doi:10.1090/S0025-5718-2013-02787-1. MR 3194140.
^ Tao 2009, 3.1 Structure and randomness in the prime numbers, pp. 239–247. See especially p. 239.
^ Guy 2013, p. 159.
^ Ramaré, Olivier (1995). "On Šnirel'man's constant". Annali della Scuola Normale Superiore di Pisa. 22 (4): 645–706. MR 1375315.
^ Rassias, Michael Th. (2017). Goldbach's Problem: Selected Topics. Cham: Springer. p. vii. doi:10.1007/978-3-319-57914-6. ISBN 978-3-319-57912-2. MR 3674356.
^ Koshy 2002, Theorem 2.14, p. 109. Riesel 1994 gives a similar argument using the primorial in place of the factorial.
^ ^a ^b Riesel 1994, "Large gaps between consecutive primes", pp. 78–79.
^ Sloane, N. J. A. (ed.). "Sequence A100964 (Smallest prime number that begins a prime gap of at least 2n)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ ^a ^b ^c Ribenboim 2004, Gaps between primes, pp. 186–192.
^ ^a ^b Ribenboim 2004, p. 183.
^ Chan, Joel (February 1996). "Prime time!". Math Horizons. 3 (3): 23–25. doi:10.1080/10724117.1996.11974965. JSTOR 25678057. Note that Chan lists Legendre's conjecture as "Sierpinski's Postulate".
^ Ribenboim 2004, Prime $k$ -tuples conjecture, pp. 201–202.
^ Sandifer 2007, Chapter 35, Estimating the Basel problem, pp. 205–208.
^ Ogilvy, C.S.; Anderson, J.T. (1988). Excursions in Number Theory. Dover Publications Inc. pp. 29–35. ISBN 978-0-486-25778-5.
^ Apostol 1976, Section 1.6, Theorem 1.13
^ Apostol 1976, Section 4.8, Theorem 4.12
^ ^a ^b Miller, Steven J.; Takloo-Bighash, Ramin (2006). An Invitation to Modern Number Theory. Princeton University Press. pp. 43–44. ISBN 978-0-691-12060-7.
^ Crandall & Pomerance 2005, p. 6.
^ Crandall & Pomerance 2005, Section 3.7, Counting primes, pp. 152–162.
^ ^a ^b Crandall & Pomerance 2005, p. 10.
^ du Sautoy, Marcus (2011). "What are the odds that your telephone number is prime?". The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. pp. 50–52. ISBN 978-0-230-12028-0.
^ Apostol 1976, Section 4.6, Theorem 4.7
^ Gelfand, I.M.; Shen, Alexander (2003). Algebra. Springer. p. 37. ISBN 978-0-8176-3677-7.
^ Mollin, Richard A. (1997). Fundamental Number Theory with Applications. Discrete Mathematics and Its Applications. CRC Press. p. 76. ISBN 978-0-8493-3987-5.
^ Crandall & Pomerance 2005, Theorem 1.1.5, p. 12.
^ Green, Ben; Tao, Terence (2008). "The primes contain arbitrarily long arithmetic progressions". Annals of Mathematics. 167 (2): 481–547. arXiv:math.NT/0404188. doi:10.4007/annals.2008.167.481. S2CID 1883951.
^ Hua, L.K. (2009) [1965]. Additive Theory of Prime Numbers. Translations of Mathematical Monographs. Vol. 13. Providence, RI: American Mathematical Society. pp. 176–177. ISBN 978-0-8218-4942-2. MR 0194404. OCLC 824812353.
^ The sequence of these primes, starting at $n=1$ rather than $n=0$ , is listed by Lava, Paolo Pietro; Balzarotti, Giorgio (2010). "Chapter 33. Formule fortunate". 103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (in Italian). Ulrico Hoepli Editore S.p.A. p. 133. ISBN 978-88-203-5804-4.
^ Chamberland, Marc (2015). "The Heegner numbers". Single Digits: In Praise of Small Numbers. Princeton University Press. pp. 213–215. ISBN 978-1-4008-6569-7.
^ ^a ^b Guy, Richard (2013). "A1 Prime values of quadratic functions". Unsolved Problems in Number Theory. Problem Books in Mathematics (3rd ed.). Springer. pp. 7–10. ISBN 978-0-387-26677-0.
^ Patterson, S.J. (1988). An introduction to the theory of the Riemann zeta-function. Cambridge Studies in Advanced Mathematics. Vol. 14. Cambridge University Press, Cambridge. p. 1. doi:10.1017/CBO9780511623707. ISBN 978-0-521-33535-5. MR 0933558.
^ Borwein, Peter; Choi, Stephen; Rooney, Brendan; Weirathmueller, Andrea (2008). The Riemann hypothesis: A resource for the afficionado and virtuoso alike. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. New York: Springer. pp. 10–11. doi:10.1007/978-0-387-72126-2. ISBN 978-0-387-72125-5. MR 2463715.
^ Sandifer 2007, pp. 191–193.
^ Borwein et al. 2008, Conjecture 2.7 (the Riemann hypothesis), p. 15.
^ Patterson 1988, p. 7.
^ ^a ^b Borwein et al. 2008, p. 18.
^ Nathanson 2000, Chapter 9, The prime number theorem, pp. 289–324.
^ Zagier, Don (1977). "The first 50 million prime numbers". The Mathematical Intelligencer. 1 (S2): 7–19. doi:10.1007/bf03351556. S2CID 37866599. See especially pp. 14–16.
^ Kraft & Washington (2014), Proposition 5.3, p. 96.
^ Shahriari, Shahriar (2017). Algebra in Action: A Course in Groups, Rings, and Fields. Pure and Applied Undergraduate Texts. Vol. 27. American Mathematical Society. pp. 20–21. ISBN 978-1-4704-2849-5.
^ Dudley 1978, Theorem 3, p. 28.
^ Shahriari 2017, pp. 27–28.
^ Ribenboim 2004, Fermat's little theorem and primitive roots modulo a prime, pp. 17–21.
^ Ribenboim 2004, The property of Giuga, pp. 21–22.
^ Ribenboim 2004, The theorem of Wilson, p. 21.
^ ^a ^b ^c Childress, Nancy (2009). Class Field Theory. Universitext. Springer, New York. pp. 8–11. doi:10.1007/978-0-387-72490-4. ISBN 978-0-387-72489-8. MR 2462595. See also p. 64.
^ Erickson, Marty; Vazzana, Anthony; Garth, David (2016). Introduction to Number Theory. Textbooks in Mathematics (2nd ed.). Boca Raton, FL: CRC Press. p. 200. ISBN 978-1-4987-1749-6. MR 3468748.
^ Weil, André (1995). Basic Number Theory. Classics in Mathematics. Berlin: Springer-Verlag. p. 43. ISBN 978-3-540-58655-5. MR 1344916. Note however that some authors such as Childress (2009) instead use "place" to mean an equivalence class of norms.
^ Koch, H. (1997). Algebraic Number Theory. Berlin: Springer-Verlag. p. 136. CiteSeerX 10.1.1.309.8812. doi:10.1007/978-3-642-58095-6. ISBN 978-3-540-63003-6. MR 1474965.
^ Lauritzen, Niels (2003). Concrete Abstract Algebra: From numbers to Gröbner bases. Cambridge: Cambridge University Press. p. 127. doi:10.1017/CBO9780511804229. ISBN 978-0-521-53410-9. MR 2014325.
^ Lauritzen 2003, Corollary 3.5.14, p. 133; Lemma 3.5.18, p. 136.
^ Kraft & Washington 2014, Section 12.1, Sums of two squares, pp. 297–301.
^ Eisenbud, David (1995). Commutative Algebra. Graduate Texts in Mathematics. Vol. 150. Berlin; New York: Springer-Verlag. Section 3.3. doi:10.1007/978-1-4612-5350-1. ISBN 978-0-387-94268-1. MR 1322960.
^ Shafarevich, Igor R. (2013). "Definition of $\operatorname {Spec} A$ ". Basic Algebraic Geometry 2: Schemes and Complex Manifolds (3rd ed.). Springer, Heidelberg. p. 5. doi:10.1007/978-3-642-38010-5. ISBN 978-3-642-38009-9. MR 3100288.
^ Neukirch, Jürgen (1999). Algebraic Number Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 322. Berlin: Springer-Verlag. Section I.8, p. 50. doi:10.1007/978-3-662-03983-0. ISBN 978-3-540-65399-8. MR 1697859.
^ Neukirch 1999, Section I.7, p. 38
^ Stevenhagen, P.; Lenstra, H.W. Jr. (1996). "Chebotarëv and his density theorem". The Mathematical Intelligencer. 18 (2): 26–37. CiteSeerX 10.1.1.116.9409. doi:10.1007/BF03027290. MR 1395088. S2CID 14089091.
^ Hall, Marshall (2018). The Theory of Groups. Dover Books on Mathematics. Courier Dover Publications. ISBN 978-0-486-81690-6. For the Sylow theorems see p. 43; for Lagrange's theorem, see p. 12; for Burnside's theorem see p. 143.
^ Bryant, John; Sangwin, Christopher J. (2008). How Round is Your Circle?: Where Engineering and Mathematics Meet. Princeton University Press. p. 178. ISBN 978-0-691-13118-4.
^ Hardy, Godfrey Harold (2012) [1940]. A Mathematician's Apology. Cambridge University Press. p. 140. ISBN 978-0-521-42706-7. OCLC 922010634. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.
^ Giblin, Peter (1993). Primes and Programming. Cambridge University Press. p. 39. ISBN 978-0-521-40988-9.
^ Giblin 1993, p. 54
^ ^a ^b Riesel 1994, p. 220.
^ Bullynck, Maarten (2010). "A history of factor tables with notes on the birth of number theory 1657–1817". Revue d'Histoire des Mathématiques. 16 (2): 133–216.
^ Wagstaff, Samuel S. Jr. (2013). The Joy of Factoring. Student mathematical library. Vol. 68. American Mathematical Society. p. 191. ISBN 978-1-4704-1048-3.
^ Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer. p. 121. ISBN 978-0-387-25282-7.
^ Farach-Colton, Martín; Tsai, Meng-Tsung (2015). "On the complexity of computing prime tables". In Elbassioni, Khaled; Makino, Kazuhisa (eds.). Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings. Lecture Notes in Computer Science. Vol. 9472. Springer. pp. 677–688. arXiv:1504.05240. doi:10.1007/978-3-662-48971-0_57.
^ Greaves, George (2013). Sieves in Number Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Vol. 43. Springer. p. 1. ISBN 978-3-662-04658-6.
^ ^a ^b Hromkovič, Juraj (2001). "5.5 Bibliographic Remarks". Algorithmics for Hard Problems. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin. pp. 383–385. doi:10.1007/978-3-662-04616-6. ISBN 978-3-540-66860-2. MR 1843669. S2CID 31159492.
^ ^a ^b Koblitz, Neal (1987). "Chapter V. Primality and Factoring". A Course in Number Theory and Cryptography. Graduate Texts in Mathematics. Vol. 114. Springer-Verlag, New York. pp. 112–149. doi:10.1007/978-1-4684-0310-7_5. ISBN 978-0-387-96576-5. MR 0910297.
^ Pieprzyk, Josef; Hardjono, Thomas; Seberry, Jennifer (2013). "2.3.9 Probabilistic Computations". Fundamentals of Computer Security. Springer. pp. 51–52. ISBN 978-3-662-07324-7.
^ ^a ^b Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
^ ^a ^b Atkin, A O.L.; Morain, F. (1993). "Elliptic curves and primality proving" (PDF). Mathematics of Computation. 61 (203): 29–68. Bibcode:1993MaCom..61...29A. doi:10.1090/s0025-5718-1993-1199989-x. JSTOR 2152935. MR 1199989.
^ ^a ^b Morain, F. (2007). "Implementing the asymptotically fast version of the elliptic curve primality proving algorithm". Mathematics of Computation. 76 (257): 493–505. arXiv:math/0502097. Bibcode:2007MaCom..76..493M. doi:10.1090/S0025-5718-06-01890-4. MR 2261033. S2CID 133193.
^ Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.
^ Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.
^ Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518.
^ ^a ^b Monier, Louis (1980). "Evaluation and comparison of two efficient probabilistic primality testing algorithms". Theoretical Computer Science. 12 (1): 97–108. doi:10.1016/0304-3975(80)90007-9. MR 0582244.
^ Tao, Terence (2009). "1.7 The Lucas–Lehmer test for Mersenne primes". Poincaré's legacies, pages from year two of a mathematical blog. Part I. Providence, RI: American Mathematical Society. pp. 36–41. ISBN 978-0-8218-4883-8. MR 2523047.
^ Kraft & Washington 2014, p. 41.
^ For instance see Guy 2013, A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape $k\cdot 2^{n}+1$ . pp. 13–21.
^ "Record 12-Million-Digit Prime Number Nets $100,000 Prize". Electronic Frontier Foundation. October 14, 2009. Retrieved 2010-01-04.
^ "EFF Cooperative Computing Awards". Electronic Frontier Foundation. 2008-02-29. Retrieved 2010-01-04.
^ "PrimeGrid's Seventeen or Bust Subproject" (PDF). Retrieved 2017-01-03.
^ Caldwell, Chris K. "The Top Twenty: Largest Known Primes". The Prime Pages. Retrieved 2017-01-03.
^ Caldwell, Chris K. "The Top Twenty: Factorial". The Prime Pages. Retrieved 2017-01-03.
^ Ribenboim 2004, p. 4.
^ Caldwell, Chris K. "The Top Twenty: Primorial". The Prime Pages. Retrieved 2017-01-03.
^ Caldwell, Chris K. "The Top Twenty: Twin Primes". The Prime Pages. Retrieved 2017-01-03.
^ Kraft & Washington 2014, p. 275.
^ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (2014). An Introduction to Mathematical Cryptography. Undergraduate Texts in Mathematics (2nd ed.). Springer. p. 329. ISBN 978-1-4939-1711-2.
^ Pomerance, Carl (1996). "A tale of two sieves". Notices of the American Mathematical Society. 43 (12): 1473–1485. MR 1416721.
^ Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.
^ Rieffel, Eleanor G.; Polak, Wolfgang H. (2011). "Chapter 8. Shor's Algorithm". Quantum Computing: A Gentle Introduction. MIT Press. pp. 163–176. ISBN 978-0-262-01506-6.
^ Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.
^ Chirgwin, Richard (October 9, 2016). "Crypto needs more transparency, researchers warn". The Register.
^ Hoffstein, Pipher & Silverman 2014, Section 2.3, Diffie–Hellman key exchange, pp. 65–67.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "11.3 Universal hashing". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 232–236. ISBN 0-262-03293-7. For $k$ -independent hashing see problem 11–4, p. 251. For the credit to Carter and Wegman, see the chapter notes, p. 252.
^ Goodrich, Michael T.; Tamassia, Roberto (2006). Data Structures & Algorithms in Java (4th ed.). John Wiley & Sons. ISBN 978-0-471-73884-8. See "Quadratic probing", p. 382, and exercise C–9.9, p. 415.
^ Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Classroom Resource Materials. Vol. 18. Mathematical Association of America. pp. 43–44. ISBN 978-0-88385-720-5.
^ Deutsch, P. (1996). ZLIB Compressed Data Format Specification version 3.3. Request for Comments. Vol. 1950. Network Working Group.
^ Knuth, Donald E. (1998). "3.2.1 The linear congruential model". The Art of Computer Programming, Vol. 2: Seminumerical algorithms (3rd ed.). Addison-Wesley. pp. 10–26. ISBN 978-0-201-89684-8.
^ Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator". ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995. S2CID 3332028.
^ Roth, K.F. (1951). "On a problem of Heilbronn". Journal of the London Mathematical Society. Second Series. 26 (3): 198–204. doi:10.1112/jlms/s1-26.3.198. MR 0041889.
^ Cox, David A. (2011). "Why Eisenstein proved the Eisenstein criterion and why Schönemann discovered it first" (PDF). American Mathematical Monthly. 118 (1): 3–31. CiteSeerX 10.1.1.398.3440. doi:10.4169/amer.math.monthly.118.01.003. S2CID 15978494.
^ Lang, Serge (2002). Algebra. Graduate Texts in Mathematics. Vol. 211. Berlin; New York: Springer-Verlag. doi:10.1007/978-1-4613-0041-0. ISBN 978-0-387-95385-4. MR 1878556., Section II.1, p. 90
^ Schubert, Horst (1949). "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (3): 57–104. MR 0031733.
^ Milnor, J. (1962). "A unique decomposition theorem for 3-manifolds". American Journal of Mathematics. 84 (1): 1–7. doi:10.2307/2372800. JSTOR 2372800. MR 0142125.
^ Boklan & Conway (2017) also include $2^{0}+1=2$ , which is not of this form.
^ ^a ^b Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics. Vol. 9. New York: Springer-Verlag. pp. 1–2. doi:10.1007/978-0-387-21850-2. ISBN 978-0-387-95332-8. MR 1866957.
^ Boklan, Kent D.; Conway, John H. (January 2017). "Expect at most one billionth of a new Fermat prime!". The Mathematical Intelligencer. 39 (1): 3–5. arXiv:1605.01371. doi:10.1007/s00283-016-9644-3. S2CID 119165671.
^ Gleason, Andrew M. (1988). "Angle trisection, the heptagon, and the triskaidecagon". American Mathematical Monthly. 95 (3): 185–194. doi:10.2307/2323624. JSTOR 2323624. MR 0935432.
^ Ziegler, Günter M. (2015). "Cannons at sparrows". European Mathematical Society Newsletter (95): 25–31. MR 3330472.
^ Peterson, Ivars (June 28, 1999). "The Return of Zeta". MAA Online. Archived from the original on October 20, 2007. Retrieved 2008-03-14.
^ Hayes, Brian (2003). "Computing science: The spectrum of Riemannium". American Scientist. 91 (4): 296–300. doi:10.1511/2003.26.3349. JSTOR 27858239. S2CID 16785858.
^ Bengtsson, Ingemar; Życzkowski, Karol (2017). Geometry of quantum states : an introduction to quantum entanglement (Second ed.). Cambridge: Cambridge University Press. pp. 313–354. ISBN 978-1-107-02625-4. OCLC 967938939.
^ Zhu, Huangjun (2010). "SIC POVMs and Clifford groups in prime dimensions". Journal of Physics A: Mathematical and Theoretical. 43 (30): 305305. arXiv:1003.3591. Bibcode:2010JPhA...43D5305Z. doi:10.1088/1751-8113/43/30/305305. S2CID 118363843.
^ Goles, E.; Schulz, O.; Markus, M. (2001). "Prime number selection of cycles in a predator-prey model". Complexity. 6 (4): 33–38. Bibcode:2001Cmplx...6d..33G. doi:10.1002/cplx.1040.
^ Campos, Paulo R.A.; de Oliveira, Viviane M.; Giro, Ronaldo; Galvão, Douglas S. (2004). "Emergence of prime numbers as the result of evolutionary strategy". Physical Review Letters. 93 (9): 098107. arXiv:q-bio/0406017. Bibcode:2004PhRvL..93i8107C. doi:10.1103/PhysRevLett.93.098107. PMID 15447148. S2CID 88332.
^ "Invasion of the Brood". The Economist. May 6, 2004. Retrieved 2006-11-26.
^ Zimmer, Carl (May 15, 2015). "Bamboo Mathematicians". Phenomena: The Loom. National Geographic. Retrieved February 22, 2018.
^ Hill, Peter Jensen, ed. (1995). The Messiaen companion. Portland, OR: Amadeus Press. Ex. 13.2 Messe de la Pentecôte 1 'Entrée'. ISBN 978-0-931340-95-6.
^ Pomerance, Carl (2004). "Prime Numbers and the Search for Extraterrestrial Intelligence" (PDF). In Hayes, David F.; Ross, Peter (eds.). Mathematical Adventures for Students and Amateurs. MAA Spectrum. Washington, DC: Mathematical Association of America. pp. 3–6. ISBN 978-0-88385-548-5. MR 2085842.
^ GrrlScientist (September 16, 2010). "The Curious Incident of the Dog in the Night-Time". Science. The Guardian. Retrieved February 22, 2010.
^ Schillinger, Liesl (April 9, 2010). "Counting on Each Other". Sunday Book Review. The New York Times.

External links

"Prime number". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
Caldwell, Chris, The Prime Pages at primes.utm.edu.
Prime Numbers on In Our Time at the BBC
Plus teacher and student package: prime numbers from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.

Generators and calculators

Prime factors calculator can factorize any positive integer up to 20 digits.
Fast Online primality test with factorization makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
Huge database of prime numbers
Prime Numbers up to 1 trillion

[29] A 44-digit prime number found in 1951 by Aimé Ferrier with a mechanical calculator remains the largest prime not to have been found with the aid of electronic computers.^[28]

[pure-33] For instance, Beiler writes that number theorist Ernst Kummer loved his ideal numbers, closely related to the primes, "because they had not soiled themselves with any practical applications",^[30] and Katz writes that Edmund Landau, known for his work on the distribution of primes, "loathed practical applications of mathematics", and for this reason avoided subjects such as geometry that had already shown themselves to be useful.^[31]

[130] In this test, the $\pm 1$ term is negative if $a$ is a square modulo the given (supposed) prime $p$ , and positive otherwise. More generally, for non-prime values of $p$ , the $\pm 1$ term is the (negated) Jacobi symbol, which can be calculated using quadratic reciprocity.

[136] Indeed, much of the analysis of elliptic curve primality proving is based on the assumption that the input to the algorithm has already passed a probabilistic test.^[131]

[150] The primorial function of $n$ , denoted by $n\#$ , yields the product of the prime numbers up to $n$ , and a primorial prime is a prime of one of the forms $n\#\pm 1$ .^[145]

[GIMPS-2018-1] "GIMPS Project Discovers Largest Known Prime Number: 2^82,589,933-1". Mersenne Research, Inc. 21 December 2018. Retrieved 21 December 2018.

[2] Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. p. 26. ISBN 978-0-19-850105-3.

[3] Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd ed.). Routledge. p. 62. ISBN 978-1-136-63662-2.

[4] Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. p. 16. OCLC 6975809.

[5] Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. p. 360. ISBN 978-0-7641-0768-9.

[6] Dudley, Underwood (1978). "Section 2: Unique factorization". Elementary number theory (2nd ed.). W.H. Freeman and Co. p. 10. ISBN 978-0-7167-0076-0.

[7] Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. Vol. 31 (2nd ed.). Elsevier. p. 113. ISBN 978-0-08-096019-7.

[ziegler-8] Ziegler, Günter M. (2004). "The great prime number record races". Notices of the American Mathematical Society. 51 (4): 414–416. MR 2039814.

[9] Stillwell, John (1997). Numbers and Geometry. Undergraduate Texts in Mathematics. Springer. p. 9. ISBN 978-0-387-98289-2.

[10] Sierpiński, Wacław (1964). A Selection of Problems in the Theory of Numbers. New York: Macmillan. p. 40. MR 0170843.

[11] Nathanson, Melvyn B. (2000). "Notations and Conventions". Elementary Methods in Number Theory. Graduate Texts in Mathematics. Vol. 195. Springer. ISBN 978-0-387-22738-2. MR 1732941.

[12] Faticoni, Theodore G. (2012). The Mathematics of Infinity: A Guide to Great Ideas. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Vol. 111 (2nd ed.). John Wiley & Sons. p. 44. ISBN 978-1-118-24382-4.

[13] Bruins, Evert Marie, review in Mathematical Reviews of Gillings, R.J. (1974). "The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?". Archive for History of Exact Sciences. 12 (4): 291–298. doi:10.1007/BF01307175. MR 0497458. S2CID 121046003.

[stillwell-2010-p40-14] Stillwell, John (2010). Mathematics and Its History. Undergraduate Texts in Mathematics (3rd ed.). Springer. p. 40. ISBN 978-1-4419-6052-8.

[pomerance-sciam-15] Pomerance, Carl (December 1982). "The Search for Prime Numbers". Scientific American. 247 (6): 136–147. Bibcode:1982SciAm.247f.136P. doi:10.1038/scientificamerican1282-136. JSTOR 24966751.

[mollin-16] Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.

[17] O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews.

[18] Sandifer 2007, 8. Fermat's Little Theorem (November 2003), p. 45

[19] Sandifer, C. Edward (2014). How Euler Did Even More. Mathematical Association of America. p. 42. ISBN 978-0-88385-584-3.

[20] Koshy, Thomas (2002). Elementary Number Theory with Applications. Academic Press. p. 369. ISBN 978-0-12-421171-1.

[21] Yuan, Wang (2002). Goldbach Conjecture. Series In Pure Mathematics. Vol. 4 (2nd ed.). World Scientific. p. 21. ISBN 978-981-4487-52-8.

[22] Narkiewicz, Wladyslaw (2000). "1.2 Sum of Reciprocals of Primes". The Development of Prime Number Theory: From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics. Springer. p. 11. ISBN 978-3-540-66289-1.

[23] Tchebychev, P. (1852). "Mémoire sur les nombres premiers" (PDF). Journal de mathématiques pures et appliquées. Série 1 (in French): 366–390.. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854

[24] Apostol, Tom M. (2000). "A centennial history of the prime number theorem". In Bambah, R.P.; Dumir, V.C.; Hans-Gill, R.J. (eds.). Number Theory. Trends in Mathematics. Basel: Birkhäuser. pp. 1–14. MR 1764793.

[25] Apostol, Tom M. (1976). "7. Dirichlet's Theorem on Primes in Arithmetical Progressions". Introduction to Analytic Number Theory. New York; Heidelberg: Springer-Verlag. pp. 146–156. MR 0434929.

[26] Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer. p. 261. ISBN 978-3-642-18192-4.

[27] Rosen, Kenneth H. (2000). "Theorem 9.20. Proth's Primality Test". Elementary Number Theory and Its Applications (4th ed.). Addison-Wesley. p. 342. ISBN 978-0-201-87073-2.

[28] Cooper, S. Barry; Hodges, Andrew (2016). The Once and Future Turing. Cambridge University Press. pp. 37–38. ISBN 978-1-107-01083-3.

[30] Rosen 2000, p. 245.

[31] Beiler, Albert H. (1999) [1966]. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. Dover. p. 2. ISBN 978-0-486-21096-4. OCLC 444171535.

[32] Katz, Shaul (2004). "Berlin roots – Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem". Science in Context. 17 (1–2): 199–234. doi:10.1017/S0269889704000092. MR 2089305. S2CID 145575536.

[ent-7-34] Kraft, James S.; Washington, Lawrence C. (2014). Elementary Number Theory. Textbooks in mathematics. CRC Press. p. 7. ISBN 978-1-4987-0269-0.

[35] Bauer, Craig P. (2013). Secret History: The Story of Cryptology. Discrete Mathematics and Its Applications. CRC Press. p. 468. ISBN 978-1-4665-6186-1.

[36] Klee, Victor; Wagon, Stan (1991). Old and New Unsolved Problems in Plane Geometry and Number Theory. Dolciani mathematical expositions. Vol. 11. Cambridge University Press. p. 224. ISBN 978-0-88385-315-3.

[neale-18-47-37] Neale 2017, pp. 18, 47.

[crxk-34-38] Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). "The history of the primality of one: a selection of sources". Journal of Integer Sequences. 15 (9): Article 12.9.8. MR 3005523. For a selection of quotes from and about the ancient Greek positions on the status of 1 and 2, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.

[39] Tarán, Leonardo (1981). Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary. Philosophia Antiqua : A Series of Monographs on Ancient Philosophy. Vol. 39. Brill. pp. 35–38. ISBN 978-90-04-06505-5.

[40] Caldwell et al. 2012, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.

[41] Caldwell et al. 2012, p. 15.

[cx-42] Caldwell, Chris K.; Xiong, Yeng (2012). "What is the smallest prime?" (PDF). Journal of Integer Sequences. 15 (9): Article 12.9.7. MR 3005530.

[43] Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (2nd ed.). Basel, Switzerland: Birkhäuser. p. 36. doi:10.1007/978-1-4612-0251-6. ISBN 978-0-8176-3743-9. MR 1292250.

[cg-bon-129-130-44] Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers. New York: Copernicus. pp. 129–130. doi:10.1007/978-1-4612-4072-3. ISBN 978-0-387-97993-9. MR 1411676.

[45] For the totient, see Sierpiński 1988, p. 245. For the sum of divisors, see Sandifer, C. Edward (2007). How Euler Did It. MAA Spectrum. Mathematical Association of America. p. 59. ISBN 978-0-88385-563-8.

[46] Smith, Karl J. (2011). The Nature of Mathematics (12th ed.). Cengage Learning. p. 188. ISBN 978-0-538-73758-6.

[47] Dudley 1978, Section 2, Theorem 2, p. 16; Neale, Vicky (2017). Closing the Gap: The Quest to Understand Prime Numbers. Oxford University Press. p. 107. ISBN 978-0-19-109243-5.

[48] u Sautoy, Marcus (2003). The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. Harper Collins. p. 23. ISBN 978-0-06-093558-0.

[49] Dudley 1978, Section 2, Lemma 5, p. 15; Higgins, Peter M. (1998). Mathematics for the Curious. Oxford University Press. pp. 77–78. ISBN 978-0-19-150050-3.

[50] Rotman, Joseph J. (2000). A First Course in Abstract Algebra (2nd ed.). Prentice Hall. Problem 1.40, p. 56. ISBN 978-0-13-011584-3.

[51] Letter in Latin from Goldbach to Euler, July 1730.

[52] Furstenberg, Harry (1955). "On the infinitude of primes". American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.

[53] Ribenboim, Paulo (2004). The little book of bigger primes. Berlin; New York: Springer-Verlag. p. 4. ISBN 978-0-387-20169-6.

[54] Euclid's Elements, Book IX, Proposition 20. See David Joyce's English translation of Euclid's proof or Williamson, James (1782). The Elements of Euclid, With Dissertations. Oxford: Clarendon Press. p. 63. OCLC 642232959.

[55] Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. pp. 82–89. ISBN 978-0-201-52989-0.

[matiyasevich-56] Matiyasevich, Yuri V. (1999). "Formulas for prime numbers". In Tabachnikov, Serge (ed.). Kvant Selecta: Algebra and Analysis. Vol. II. American Mathematical Society. pp. 13–24. ISBN 978-0-8218-1915-9.

[57] Mackinnon, Nick (June 1987). "Prime number formulae". The Mathematical Gazette. 71 (456): 113–114. doi:10.2307/3616496. JSTOR 3616496. S2CID 171537609.

[58] Wright, E.M. (1951). "A prime-representing function". American Mathematical Monthly. 58 (9): 616–618. doi:10.2307/2306356. JSTOR 2306356.

[59] Guy 2013, p. vii.

[60] Guy 2013, C1 Goldbach's conjecture, pp. 105–107.

[61] Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014). "Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$ ". Mathematics of Computation. 83 (288): 2033–2060. doi:10.1090/S0025-5718-2013-02787-1. MR 3194140.

[62] Tao 2009, 3.1 Structure and randomness in the prime numbers, pp. 239–247. See especially p. 239.

[63] Guy 2013, p. 159.

[64] Ramaré, Olivier (1995). "On Šnirel'man's constant". Annali della Scuola Normale Superiore di Pisa. 22 (4): 645–706. MR 1375315.

[65] Rassias, Michael Th. (2017). Goldbach's Problem: Selected Topics. Cham: Springer. p. vii. doi:10.1007/978-3-319-57914-6. ISBN 978-3-319-57912-2. MR 3674356.

[66] Koshy 2002, Theorem 2.14, p. 109. Riesel 1994 gives a similar argument using the primorial in place of the factorial.

[riesel-gaps-67] Riesel 1994, "Large gaps between consecutive primes", pp. 78–79.

[68] Sloane, N. J. A. (ed.). "Sequence A100964 (Smallest prime number that begins a prime gap of at least 2n)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[rib-gaps-69] Ribenboim 2004, Gaps between primes, pp. 186–192.

[rib-183-70] Ribenboim 2004, p. 183.

[chan-71] Chan, Joel (February 1996). "Prime time!". Math Horizons. 3 (3): 23–25. doi:10.1080/10724117.1996.11974965. JSTOR 25678057. Note that Chan lists Legendre's conjecture as "Sierpinski's Postulate".

[72] Ribenboim 2004, Prime $k$ -tuples conjecture, pp. 201–202.

[73] Sandifer 2007, Chapter 35, Estimating the Basel problem, pp. 205–208.

[74] Ogilvy, C.S.; Anderson, J.T. (1988). Excursions in Number Theory. Dover Publications Inc. pp. 29–35. ISBN 978-0-486-25778-5.

[75] Apostol 1976, Section 1.6, Theorem 1.13

[76] Apostol 1976, Section 4.8, Theorem 4.12

[mtb-invitation-77] Miller, Steven J.; Takloo-Bighash, Ramin (2006). An Invitation to Modern Number Theory. Princeton University Press. pp. 43–44. ISBN 978-0-691-12060-7.

[78] Crandall & Pomerance 2005, p. 6.

[79] Crandall & Pomerance 2005, Section 3.7, Counting primes, pp. 152–162.

[cranpom10-80] Crandall & Pomerance 2005, p. 10.

[81] u Sautoy, Marcus (2011). "What are the odds that your telephone number is prime?". The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. pp. 50–52. ISBN 978-0-230-12028-0.

[82] Apostol 1976, Section 4.6, Theorem 4.7

[83] Gelfand, I.M.; Shen, Alexander (2003). Algebra. Springer. p. 37. ISBN 978-0-8176-3677-7.

[84] Mollin, Richard A. (1997). Fundamental Number Theory with Applications. Discrete Mathematics and Its Applications. CRC Press. p. 76. ISBN 978-0-8493-3987-5.

[85] Crandall & Pomerance 2005, Theorem 1.1.5, p. 12.

[86] Green, Ben; Tao, Terence (2008). "The primes contain arbitrarily long arithmetic progressions". Annals of Mathematics. 167 (2): 481–547. arXiv:math.NT/0404188. doi:10.4007/annals.2008.167.481. S2CID 1883951.

[87] Hua, L.K. (2009) [1965]. Additive Theory of Prime Numbers. Translations of Mathematical Monographs. Vol. 13. Providence, RI: American Mathematical Society. pp. 176–177. ISBN 978-0-8218-4942-2. MR 0194404. OCLC 824812353.

[88] The sequence of these primes, starting at $n=1$ rather than $n=0$ , is listed by Lava, Paolo Pietro; Balzarotti, Giorgio (2010). "Chapter 33. Formule fortunate". 103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (in Italian). Ulrico Hoepli Editore S.p.A. p. 133. ISBN 978-88-203-5804-4.

[89] Chamberland, Marc (2015). "The Heegner numbers". Single Digits: In Praise of Small Numbers. Princeton University Press. pp. 213–215. ISBN 978-1-4008-6569-7.

[guy-a1-90] Guy, Richard (2013). "A1 Prime values of quadratic functions". Unsolved Problems in Number Theory. Problem Books in Mathematics (3rd ed.). Springer. pp. 7–10. ISBN 978-0-387-26677-0.

[91] Patterson, S.J. (1988). An introduction to the theory of the Riemann zeta-function. Cambridge Studies in Advanced Mathematics. Vol. 14. Cambridge University Press, Cambridge. p. 1. doi:10.1017/CBO9780511623707. ISBN 978-0-521-33535-5. MR 0933558.

[92] Borwein, Peter; Choi, Stephen; Rooney, Brendan; Weirathmueller, Andrea (2008). The Riemann hypothesis: A resource for the afficionado and virtuoso alike. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. New York: Springer. pp. 10–11. doi:10.1007/978-0-387-72126-2. ISBN 978-0-387-72125-5. MR 2463715.

[93] Sandifer 2007, pp. 191–193.

[94] Borwein et al. 2008, Conjecture 2.7 (the Riemann hypothesis), p. 15.

[95] Patterson 1988, p. 7.

[bcrw18-96] Borwein et al. 2008, p. 18.

[97] Nathanson 2000, Chapter 9, The prime number theorem, pp. 289–324.

[98] Zagier, Don (1977). "The first 50 million prime numbers". The Mathematical Intelligencer. 1 (S2): 7–19. doi:10.1007/bf03351556. S2CID 37866599. See especially pp. 14–16.

[99] Kraft & Washington (2014), Proposition 5.3, p. 96.

[100] Shahriari, Shahriar (2017). Algebra in Action: A Course in Groups, Rings, and Fields. Pure and Applied Undergraduate Texts. Vol. 27. American Mathematical Society. pp. 20–21. ISBN 978-1-4704-2849-5.

[101] Dudley 1978, Theorem 3, p. 28.

[102] Shahriari 2017, pp. 27–28.

[103] Ribenboim 2004, Fermat's little theorem and primitive roots modulo a prime, pp. 17–21.

[104] Ribenboim 2004, The property of Giuga, pp. 21–22.

[105] Ribenboim 2004, The theorem of Wilson, p. 21.

[childress-106] Childress, Nancy (2009). Class Field Theory. Universitext. Springer, New York. pp. 8–11. doi:10.1007/978-0-387-72490-4. ISBN 978-0-387-72489-8. MR 2462595. See also p. 64.

[107] Erickson, Marty; Vazzana, Anthony; Garth, David (2016). Introduction to Number Theory. Textbooks in Mathematics (2nd ed.). Boca Raton, FL: CRC Press. p. 200. ISBN 978-1-4987-1749-6. MR 3468748.

[108] Weil, André (1995). Basic Number Theory. Classics in Mathematics. Berlin: Springer-Verlag. p. 43. ISBN 978-3-540-58655-5. MR 1344916. Note however that some authors such as Childress (2009) instead use "place" to mean an equivalence class of norms.

[109] Koch, H. (1997). Algebraic Number Theory. Berlin: Springer-Verlag. p. 136. CiteSeerX 10.1.1.309.8812. doi:10.1007/978-3-642-58095-6. ISBN 978-3-540-63003-6. MR 1474965.

[110] Lauritzen, Niels (2003). Concrete Abstract Algebra: From numbers to Gröbner bases. Cambridge: Cambridge University Press. p. 127. doi:10.1017/CBO9780511804229. ISBN 978-0-521-53410-9. MR 2014325.

[111] Lauritzen 2003, Corollary 3.5.14, p. 133; Lemma 3.5.18, p. 136.

[112] Kraft & Washington 2014, Section 12.1, Sums of two squares, pp. 297–301.

[113] Eisenbud, David (1995). Commutative Algebra. Graduate Texts in Mathematics. Vol. 150. Berlin; New York: Springer-Verlag. Section 3.3. doi:10.1007/978-1-4612-5350-1. ISBN 978-0-387-94268-1. MR 1322960.

[114] Shafarevich, Igor R. (2013). "Definition of $\operatorname {Spec} A$ ". Basic Algebraic Geometry 2: Schemes and Complex Manifolds (3rd ed.). Springer, Heidelberg. p. 5. doi:10.1007/978-3-642-38010-5. ISBN 978-3-642-38009-9. MR 3100288.

[115] Neukirch, Jürgen (1999). Algebraic Number Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 322. Berlin: Springer-Verlag. Section I.8, p. 50. doi:10.1007/978-3-662-03983-0. ISBN 978-3-540-65399-8. MR 1697859.

[116] Neukirch 1999, Section I.7, p. 38

[117] Stevenhagen, P.; Lenstra, H.W. Jr. (1996). "Chebotarëv and his density theorem". The Mathematical Intelligencer. 18 (2): 26–37. CiteSeerX 10.1.1.116.9409. doi:10.1007/BF03027290. MR 1395088. S2CID 14089091.

[118] Hall, Marshall (2018). The Theory of Groups. Dover Books on Mathematics. Courier Dover Publications. ISBN 978-0-486-81690-6. For the Sylow theorems see p. 43; for Lagrange's theorem, see p. 12; for Burnside's theorem see p. 143.

[119] Bryant, John; Sangwin, Christopher J. (2008). How Round is Your Circle?: Where Engineering and Mathematics Meet. Princeton University Press. p. 178. ISBN 978-0-691-13118-4.

[120] Hardy, Godfrey Harold (2012) [1940]. A Mathematician's Apology. Cambridge University Press. p. 140. ISBN 978-0-521-42706-7. OCLC 922010634. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.

[121] Giblin, Peter (1993). Primes and Programming. Cambridge University Press. p. 39. ISBN 978-0-521-40988-9.

[122] Giblin 1993, p. 54

[p._220-123] Riesel 1994, p. 220.

[124] Bullynck, Maarten (2010). "A history of factor tables with notes on the birth of number theory 1657–1817". Revue d'Histoire des Mathématiques. 16 (2): 133–216.

[125] Wagstaff, Samuel S. Jr. (2013). The Joy of Factoring. Student mathematical library. Vol. 68. American Mathematical Society. p. 191. ISBN 978-1-4704-1048-3.

[126] Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer. p. 121. ISBN 978-0-387-25282-7.

[127] Farach-Colton, Martín; Tsai, Meng-Tsung (2015). "On the complexity of computing prime tables". In Elbassioni, Khaled; Makino, Kazuhisa (eds.). Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings. Lecture Notes in Computer Science. Vol. 9472. Springer. pp. 677–688. arXiv:1504.05240. doi:10.1007/978-3-662-48971-0_57.

[128] Greaves, George (2013). Sieves in Number Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Vol. 43. Springer. p. 1. ISBN 978-3-662-04658-6.

[hromkovic-129] Hromkovič, Juraj (2001). "5.5 Bibliographic Remarks". Algorithmics for Hard Problems. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin. pp. 383–385. doi:10.1007/978-3-662-04616-6. ISBN 978-3-540-66860-2. MR 1843669. S2CID 31159492.

[koblitz-131] Koblitz, Neal (1987). "Chapter V. Primality and Factoring". A Course in Number Theory and Cryptography. Graduate Texts in Mathematics. Vol. 114. Springer-Verlag, New York. pp. 112–149. doi:10.1007/978-1-4684-0310-7_5. ISBN 978-0-387-96576-5. MR 0910297.

[132] Pieprzyk, Josef; Hardjono, Thomas; Seberry, Jennifer (2013). "2.3.9 Probabilistic Computations". Fundamentals of Computer Security. Springer. pp. 51–52. ISBN 978-3-662-07324-7.

[tao-aks-133] Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.

[atkin-morain-134] Atkin, A O.L.; Morain, F. (1993). "Elliptic curves and primality proving" (PDF). Mathematics of Computation. 61 (203): 29–68. Bibcode:1993MaCom..61...29A. doi:10.1090/s0025-5718-1993-1199989-x. JSTOR 2152935. MR 1199989.

[morain-135] Morain, F. (2007). "Implementing the asymptotically fast version of the elliptic curve primality proving algorithm". Mathematics of Computation. 76 (257): 493–505. arXiv:math/0502097. Bibcode:2007MaCom..76..493M. doi:10.1090/S0025-5718-06-01890-4. MR 2261033. S2CID 133193.

[137] Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.

[PSW-138] Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.

[lpsp-139] Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518.

[monier-140] Monier, Louis (1980). "Evaluation and comparison of two efficient probabilistic primality testing algorithms". Theoretical Computer Science. 12 (1): 97–108. doi:10.1016/0304-3975(80)90007-9. MR 0582244.

[141] Tao, Terence (2009). "1.7 The Lucas–Lehmer test for Mersenne primes". Poincaré's legacies, pages from year two of a mathematical blog. Part I. Providence, RI: American Mathematical Society. pp. 36–41. ISBN 978-0-8218-4883-8. MR 2523047.

[142] Kraft & Washington 2014, p. 41.

[143] For instance see Guy 2013, A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape $k\cdot 2^{n}+1$ . pp. 13–21.

[144] "Record 12-Million-Digit Prime Number Nets $100,000 Prize". Electronic Frontier Foundation. October 14, 2009. Retrieved 2010-01-04.

[145] "EFF Cooperative Computing Awards". Electronic Frontier Foundation. 2008-02-29. Retrieved 2010-01-04.

[146] "PrimeGrid's Seventeen or Bust Subproject" (PDF). Retrieved 2017-01-03.

[147] Caldwell, Chris K. "The Top Twenty: Largest Known Primes". The Prime Pages. Retrieved 2017-01-03.

[148] Caldwell, Chris K. "The Top Twenty: Factorial". The Prime Pages. Retrieved 2017-01-03.

[149] Ribenboim 2004, p. 4.

[151] Caldwell, Chris K. "The Top Twenty: Primorial". The Prime Pages. Retrieved 2017-01-03.

[152] Caldwell, Chris K. "The Top Twenty: Twin Primes". The Prime Pages. Retrieved 2017-01-03.

[153] Kraft & Washington 2014, p. 275.

[154] Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (2014). An Introduction to Mathematical Cryptography. Undergraduate Texts in Mathematics (2nd ed.). Springer. p. 329. ISBN 978-1-4939-1711-2.

[155] Pomerance, Carl (1996). "A tale of two sieves". Notices of the American Mathematical Society. 43 (12): 1473–1485. MR 1416721.

[156] Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.

[157] Rieffel, Eleanor G.; Polak, Wolfgang H. (2011). "Chapter 8. Shor's Algorithm". Quantum Computing: A Gentle Introduction. MIT Press. pp. 163–176. ISBN 978-0-262-01506-6.

[158] Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.

[159] Chirgwin, Richard (October 9, 2016). "Crypto needs more transparency, researchers warn". The Register.

[160] Hoffstein, Pipher & Silverman 2014, Section 2.3, Diffie–Hellman key exchange, pp. 65–67.

[161] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "11.3 Universal hashing". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 232–236. ISBN 0-262-03293-7. For $k$ -independent hashing see problem 11–4, p. 251. For the credit to Carter and Wegman, see the chapter notes, p. 252.

[162] Goodrich, Michael T.; Tamassia, Roberto (2006). Data Structures & Algorithms in Java (4th ed.). John Wiley & Sons. ISBN 978-0-471-73884-8. See "Quadratic probing", p. 382, and exercise C–9.9, p. 415.

[163] Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Classroom Resource Materials. Vol. 18. Mathematical Association of America. pp. 43–44. ISBN 978-0-88385-720-5.

[164] Deutsch, P. (1996). ZLIB Compressed Data Format Specification version 3.3. Request for Comments. Vol. 1950. Network Working Group.

[165] Knuth, Donald E. (1998). "3.2.1 The linear congruential model". The Art of Computer Programming, Vol. 2: Seminumerical algorithms (3rd ed.). Addison-Wesley. pp. 10–26. ISBN 978-0-201-89684-8.

[166] Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator". ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995. S2CID 3332028.

[167] Roth, K.F. (1951). "On a problem of Heilbronn". Journal of the London Mathematical Society. Second Series. 26 (3): 198–204. doi:10.1112/jlms/s1-26.3.198. MR 0041889.

[168] Cox, David A. (2011). "Why Eisenstein proved the Eisenstein criterion and why Schönemann discovered it first" (PDF). American Mathematical Monthly. 118 (1): 3–31. CiteSeerX 10.1.1.398.3440. doi:10.4169/amer.math.monthly.118.01.003. S2CID 15978494.

[169] Lang, Serge (2002). Algebra. Graduate Texts in Mathematics. Vol. 211. Berlin; New York: Springer-Verlag. doi:10.1007/978-1-4613-0041-0. ISBN 978-0-387-95385-4. MR 1878556., Section II.1, p. 90

[170] Schubert, Horst (1949). "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (3): 57–104. MR 0031733.

[171] Milnor, J. (1962). "A unique decomposition theorem for 3-manifolds". American Journal of Mathematics. 84 (1): 1–7. doi:10.2307/2372800. JSTOR 2372800. MR 0142125.

[172] Boklan & Conway (2017) also include $2^{0}+1=2$ , which is not of this form.

[kls-173] Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics. Vol. 9. New York: Springer-Verlag. pp. 1–2. doi:10.1007/978-0-387-21850-2. ISBN 978-0-387-95332-8. MR 1866957.

[174] Boklan, Kent D.; Conway, John H. (January 2017). "Expect at most one billionth of a new Fermat prime!". The Mathematical Intelligencer. 39 (1): 3–5. arXiv:1605.01371. doi:10.1007/s00283-016-9644-3. S2CID 119165671.

[175] Gleason, Andrew M. (1988). "Angle trisection, the heptagon, and the triskaidecagon". American Mathematical Monthly. 95 (3): 185–194. doi:10.2307/2323624. JSTOR 2323624. MR 0935432.

[176] Ziegler, Günter M. (2015). "Cannons at sparrows". European Mathematical Society Newsletter (95): 25–31. MR 3330472.

[177] Peterson, Ivars (June 28, 1999). "The Return of Zeta". MAA Online. Archived from the original on October 20, 2007. Retrieved 2008-03-14.

[178] Hayes, Brian (2003). "Computing science: The spectrum of Riemannium". American Scientist. 91 (4): 296–300. doi:10.1511/2003.26.3349. JSTOR 27858239. S2CID 16785858.

[179] Bengtsson, Ingemar; Życzkowski, Karol (2017). Geometry of quantum states : an introduction to quantum entanglement (Second ed.). Cambridge: Cambridge University Press. pp. 313–354. ISBN 978-1-107-02625-4. OCLC 967938939.

[180] Zhu, Huangjun (2010). "SIC POVMs and Clifford groups in prime dimensions". Journal of Physics A: Mathematical and Theoretical. 43 (30): 305305. arXiv:1003.3591. Bibcode:2010JPhA...43D5305Z. doi:10.1088/1751-8113/43/30/305305. S2CID 118363843.

[181] Goles, E.; Schulz, O.; Markus, M. (2001). "Prime number selection of cycles in a predator-prey model". Complexity. 6 (4): 33–38. Bibcode:2001Cmplx...6d..33G. doi:10.1002/cplx.1040.

[182] Campos, Paulo R.A.; de Oliveira, Viviane M.; Giro, Ronaldo; Galvão, Douglas S. (2004). "Emergence of prime numbers as the result of evolutionary strategy". Physical Review Letters. 93 (9): 098107. arXiv:q-bio/0406017. Bibcode:2004PhRvL..93i8107C. doi:10.1103/PhysRevLett.93.098107. PMID 15447148. S2CID 88332.

[183] "Invasion of the Brood". The Economist. May 6, 2004. Retrieved 2006-11-26.

[184] Zimmer, Carl (May 15, 2015). "Bamboo Mathematicians". Phenomena: The Loom. National Geographic. Retrieved February 22, 2018.

[185] Hill, Peter Jensen, ed. (1995). The Messiaen companion. Portland, OR: Amadeus Press. Ex. 13.2 Messe de la Pentecôte 1 'Entrée'. ISBN 978-0-931340-95-6.

[186] Pomerance, Carl (2004). "Prime Numbers and the Search for Extraterrestrial Intelligence" (PDF). In Hayes, David F.; Ross, Peter (eds.). Mathematical Adventures for Students and Amateurs. MAA Spectrum. Washington, DC: Mathematical Association of America. pp. 3–6. ISBN 978-0-88385-548-5. MR 2085842.

[187] GrrlScientist (September 16, 2010). "The Curious Incident of the Dog in the Night-Time". Science. The Guardian. Retrieved February 22, 2010.

[188] Schillinger, Liesl (April 9, 2010). "Counting on Each Other". Sunday Book Review. The New York Times.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[a]

[29]

[b]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]

[75]

[76]

[77]

[78]

[79]

[80]

[81]

[82]

[83]

[84]

[85]

[86]

[87]

[88]

[89]

[90]

[91]

[92]

[93]

[94]

[95]

[96]

[97]

[98]

[99]

[100]

[101]