Sophie-Germain-Primzahlen

Eine Primzahl p bezeichnet man nach der französischen Mathematikerin Sophie Germain als Sophie-Germain-Primzahl oder Germainsche Primzahl, wenn auch 2p+1 eine Primzahl ist.

Die folgende Liste enthält die 190 Sophie-Germain-Primzahlen unterhalb von 10.000.

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

Die größten zur Zeit bekannten Sophie-Germain-Primzahlen sind

Platz 1: 7.068.555 2^121.301 -1, eine Zahl mit 36.523 Stellen, entdeckt 2005
Platz 5: 109.433.307 2^66.452 - 1, eine Zahl mit 20.013 Stellen, welche 2001 von Underbakke (und anderen) gefunden wurde.

Primzahlen, die keine Germainschen Primzahlen sind

Sei q=2k+1 eine Primzahl und p>q ebenfalls prim mit p=k mod q, d.h. p-k=n*q. Dann hat 2p+1=2(n*q+k)+1=2nq+2k+1=(2n+1)q den Primteiler q und folglich ist p keine Germainsche Primzahl.

Ist umgekehrt die Primzahl p keine Germainsche Primzahl, so besitzt die ungerade Zahl 2p+1 einen kleinsten Primteiler q, der ebenfalls ungerade sein muß, also von der Form q=2k+1 ist. Es gilt daher 2p+1 = q(2n+1) = 2nq + 2k+1 = 2(nq+k) + 1, also p=nq+k oder p=k mod q. Natürlich gilt p>q.

Folgerung: Sei p eine Primzahl, deren Dezimaldarstellung mit einer 7 endet. Für k=2, also q=2k+1 = 5, gilt dann p = k mod 5. Daher ist p keine Germainsche Primzahl, im Einklang mit der obigen Tabelle.

Zusammenhang mit den Mersenne-Zahlen

Die folgende Eigenschaft wurde von Euler 1750 behauptet und von Lagrange 1775 bewiesen (Einen Beweis findet man unter http://primes.utm.edu/notes/proofs/MerDiv2.html):

Satz: Sei p > 3 und p = 3 (mod 4) eine Primzahl. Genau dann ist p eine Sophie-Germain-Primzahl, wenn 2p+1 ein Teiler der p-ten Mersenne-Zahl M_p ist.

Beispielsweise ist p=11 eine Sophie-Germain-Primzahl, denn auch 2p+1 = 23 ist prim. Außerdem ist 11 = 3 mod 4. Daher ist die 11. Mersenne-Zahl $M$ ₁₁ = 2¹¹ -1 = 2047 = 89 * 23 teilbar durch 2p+1 = 23.