Sophie Germain prime number
A prime number p is called a Sophie-Germain prime number or also Germain prime number , even if 2 p + 1 is a prime number (2 p + 1 is then a safe prime number (from the English safe prime )). These prime numbers are named after the mathematician Sophie Germain (1776–1831), who dealt with Fermat's conjecture and proved that the first case of the conjecture applies to all Sophie Germain prime numbers.
Examples
p = 2 is a Sophie Germain prime, because 2p + 1 = 5 is prime. The same goes for 3, 5, and 11.
p = 7 is not a Sophie Germain prime because 2p + 1 = 15 is not prime.
Between 1 and 10,000 there are the following 190 Sophie Germain primes:
2 | 3 | 5 | 11 | 23 | 29 | 41 | 53 | 83 | 89 | 113 | 131 | 173 | 179 | 191 | 233 | 239 | 251 | 281 | 293 |
359 | 419 | 431 | 443 | 491 | 509 | 593 | 641 | 653 | 659 | 683 | 719 | 743 | 761 | 809 | 911 | 953 | 1013 | 1019 | 1031 |
1049 | 1103 | 1223 | 1229 | 1289 | 1409 | 1439 | 1451 | 1481 | 1499 | 1511 | 1559 | 1583 | 1601 | 1733 | 1811 | 1889 | 1901 | 1931 | 1973 |
2003 | 2039 | 2063 | 2069 | 2129 | 2141 | 2273 | 2339 | 2351 | 2393 | 2399 | 2459 | 2543 | 2549 | 2693 | 2699 | 2741 | 2753 | 2819 | 2903 |
2939 | 2963 | 2969 | 3023 | 3299 | 3329 | 3359 | 3389 | 3413 | 3449 | 3491 | 3539 | 3593 | 3623 | 3761 | 3779 | 3803 | 3821 | 3851 | 3863 |
3911 | 4019 | 4073 | 4211 | 4271 | 4349 | 4373 | 4391 | 4409 | 4481 | 4733 | 4793 | 4871 | 4919 | 4943 | 5003 | 5039 | 5051 | 5081 | 5171 |
5231 | 5279 | 5303 | 5333 | 5399 | 5441 | 5501 | 5639 | 5711 | 5741 | 5849 | 5903 | 6053 | 6101 | 6113 | 6131 | 6173 | 6263 | 6269 | 6323 |
6329 | 6449 | 6491 | 6521 | 6551 | 6563 | 6581 | 6761 | 6899 | 6983 | 7043 | 7079 | 7103 | 7121 | 7151 | 7193 | 7211 | 7349 | 7433 | 7541 |
7643 | 7649 | 7691 | 7823 | 7841 | 7883 | 7901 | 8069 | 8093 | 8111 | 8243 | 8273 | 8513 | 8663 | 8693 | 8741 | 8951 | 8969 | 9029 | 9059 |
9221 | 9293 | 9371 | 9419 | 9473 | 9479 | 9539 | 9629 | 9689 | 9791 |
The first Sophie Germain prime numbers can also be found in the following OEIS link:
The associated safe prime numbers are the following:
The following list shows the 10 largest known Sophie Germain prime numbers. All discoverers of these prime numbers are participants in the PrimeGrid project.
rank | Rank in list of prime numbers a |
Prime number | Decimal places of |
Discovery date | Explorer | source |
---|---|---|---|---|---|---|
1 | 1609. | February 29, 2016 | Scott Brown ( USA ) | |||
2 | 1678. | April 4th or 9th 2012 | Lee Blyth ( AUS ) | |||
3 | 1697. | March 22, 2010 | Tom Wu | |||
4th | 1703. | November 18, 2009 | Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai | |||
5 | 1704. | November 2, 2009 | Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai | |||
6th | 1722. | 17th May 2020 | Michael Kwok | |||
7th | 1729. | April 1, 2016 | S. Urushihata | |||
8th | 1743. | September 18, 2009 | Tom Wu | |||
9 | 1748. | January 25, 2007 | David Underbakke | |||
10 | 1752. | May 3, 2006 | Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai |
importance
characteristics
- A Sophie Germain prime can never end with 7 in the decimal system.
-
Proof:
- Let p be a prime number with a final digit of 7. Then p can be represented as p = 10k + 7. Then: 2p + 1 = 20k + 14 + 1 = 20k + 15 = 5 · (4k + 3).
- This means that 2p + 1 is divisible by 5, but greater than 14, i.e. not prime.
-
Proof:
- All Sophie-Germain primes belong to the remainder class , so they have the form with an integer .
-
Proof:
- All numbers of the remainder classes r ≡ 0 (mod 6), r ≡ 2 (mod 6) and r ≡ 4 (mod 6) are even and therefore divisible by 2.
- All numbers of the remainder classes r ≡ 0 (mod 6) and r ≡ 3 (mod 6) are divisible by 3.
- Although there are prime numbers in the remainder class r ≡ 1 (mod 6), 2 · (6n + 1) +1 = 12n + 3 = 3 · (4n + 1) - and 3 · (4n + 1) is divisible by 3 .
- The only remaining class of six for the Sophie-Germain primes is the residual class r ≡ 5 (mod 6). Only in this case does the certain prime number belonging to a Sophie-Germain prime number have the form 2 · (6n + 5) +1 = 12n + 11 ≡ 5 (mod 6) and can be prime.
-
Proof:
Connection with the Mersenne numbers
The following property was proven by Leonhard Euler and Joseph-Louis Lagrange :
- If p> 3 is a Sophie-Germain prime with p ≡ 3 (mod 4), then 2p + 1 is a divisor of the p-th Mersenne number M (p).
-
Example:
- p = 11 is a Sophie-Germain prime, because 2p + 1 = 23 is prime. Then 11 ≡ 3 (mod 4), because 11 divided by 4 gives the remainder 3.
- The 11th Mersenne number M (11) = 2 11 -1 = 2047 is therefore not prime, but divisible by 2p + 1 = 23; concretely, M (11) = 23 · 89.
-
Example:
Frequency of Sophie Germain primes
In 1922 Godfrey Harold Hardy and John Edensor Littlewood published their conjecture regarding the frequency of Sophie Germain primes:
The number of all Sophie-Germain primes below a limit N is approximately
with C 2 = 0.6601618158 (see prime number twin constant ). This formula can be confirmed quite well with the well-known Sophie Germain prime numbers. For N = 10 4 the prediction yields 156 Sophie-Germain primes, which means an error of 18% to the exact number of 190. For N = 10 7 , the prediction delivers 50822, which is already only 9% away from the exact value 56032. A numerical approximation of the integral delivers even better results, about 195 for N = 10 4 (error only 2.6%) and 56128 for N = 10 7 (error almost negligible at 0.17%).
The density of the Sophie-Germain prime numbers falls in the order of magnitude by ln (N) times more strongly than that of the prime numbers themselves. It is used for a more precise runtime estimate for the AKS prime number test , which can determine the prime property in polynomial time.
Cunningham chain
A Cunningham chain of the first kind, with the exception of the last number, is a sequence of Sophie Germain primes. An example of such a chain is the sequence: 2, 5, 11, 23, 47.
Open questions
It is believed that there are an infinite number of Sophie Germain primes, but evidence of this has not yet been found.
Individual evidence
- ↑ A distinction is made between possible solutions of Fermat's equation in two cases: the first case means that the exponent p is not a divisor of a · b · c .
- ↑ Chris K. Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, accessed June 4, 2020 .
- ↑ List of the largest known prime numbers. Retrieved June 4, 2020 .
- ↑ 2618163402417 · 2 1290000 - 1 on primegrid.com (PDF)
- ↑ 2618163402417 · 2 1290000 - 1 on Prime Pages
- ↑ 18543637900515 · 2 666667 - 1 on primegrid.com (PDF)
- ↑ 18543637900515 · 2 666667 - 1 on Prime Pages
- ↑ 183027 · 2 265440-1 on Prime Pages
- ↑ 648621027630345 · 2 253824-1 on Prime Pages
- ↑ 620366307356565 · 2 253824-1 on Prime Pages
- ↑ 1068669447 · 2 211088-1 on Prime Pages
- ↑ 99064503957 · 2 200008 - 1 on Prime Pages
- ↑ 607095 · 2 176311-1 on Prime Pages
- ↑ 48047305725 · 2 172403-1 on Prime Pages
- ↑ 137211941292195 · 2 171960-1 on Prime Pages
Web links
- Eric W. Weisstein : Sophie Germain Prime . In: MathWorld (English).
- Sophie Germain Prime . In: PlanetMath . (English)
- The largest known Sophie Germain primes (English)