Riesel Sieve (beendet)/Beweis
Hier seht ihr den Beweis dafür, dass 509203*2^n-1 für jedes beliebige n zusammengesetzt ist. Zum Verständnis braucht man nur Kongruenzen, also das Rechnen mit Rest. Ein recht analoger Beweis für die Sierpinksi Zahl 78557 findet sich auf teamprimerib.com.
Beweis
Fall A
- Für n gerade, also n = 0 mod 2 gilt immer 3|509203*2^n-1 (3 teilt 509203*2^n-1)
- 509203*2^n-1 = 509203 * 2^(2*k) - 1 = 1*4^k-1 = 1*1^k-1 = 0 mod 3, da gilt 509203 = 1 mod 3 und 4 = 1 mod 3. Es entsteht also kein Rest bei Divison durch 3. 3 teilt also 509203*2^n-1.
Fall B
- Für n=1 mod 4 (also n=1,5,9,...) folgt 5|509203*2^n-1
- 509203 * 2^(4*k+1) - 1 = 509203 * 2^1 * (2^4)^k - 1 = 3*2*1^k-1 = 5 = 0 mod 5, da 509203 = 2 mod 5 und 2^4=16=1 mod 5
Fall C
- Für n=7 mod 12 (n=7,19,31,...) folgt 13|509203*2^n-1
- 509203 * 2^(12*k+7) - 1 =509203 * 2^7 *(2^12)^k - 1 = 6*11*1^k-1 = 65 = 0 mod 13
Fall D
- Für n=11 mod 12 (n=11,23,35,...) folgt 7|509203*2^n-1
- 509203 * 2^(12*k+11) -1 = 509203 * 2^11 *(2^12)^k - 1 = 2*4*1^k-1 = 7 = 0 mod 7
Fall E
- Aus n=3 mod 36 folgt n=3 mod 72 oder n=39 mod 72. Aus ersterem folgt der Teiler 241 aus letzterem der Teiler 17.
- 509203 * 2^(72*k+3) -1 = 509203 * 2^3 * (2^72)^k - 1 = 211*8*1^k-1 = 1687 = 0 mod 241
- 509203 * 2^(72*k+39) -1 = 509203 * 2^39 * (2^72)^k - 1 = 2*9*1^k-1 = 17 = 0 mod 17
Fall F
- Aus n=15 mod 36 folgt n=15 mod 72 oder n=51 mod 72. Aus ersterem folgt der Teiler 17 aus letzterem der Teiler 241.
- 509203 * 2^(72*k+15) -1 = 509203 * 2^15 * (2^72)^k - 1 = 2*9*1^k-1 = 17 = 0 mod 17
- 509203 * 2^(72*k+51) -1 = 509203 * 2^51 * (2^72)^k - 1 = 211*8*1^k-1 = 1687 = 0 mod 241
Fall G
- Aus n=27 mod 36 folgt n=27 mod 72 oder n=63 mod 72. Aus ersterem folgt der Teiler 241 aus letzterem der Teiler 17.
- 509203 * 2^(72*k+27) - 1 = 509203 * 2^27 * (2^72)^k - 1 = 211*8*1^k-1 = 1687 = 0 mod 241
- 509203 * 2^(72*k+63) - 1 = 509203 * 2^63 * (2^72)^k - 1 = 2*9*1^k-1 = 17 = 0 mod 17
Diese Fälle reichen aus um alle natürlichen Zahlen n abzudecken.
Für n mod 36 gibt es nur 36 verschiedene Werte. Diese decken alle natürlichen Zahlen n ab. Hier nochmal eine Auflistung:
| n mod 36 | Teiler | Fall |
|---|---|---|
| 0 | 3 | A |
| 1 | 5 | B |
| 2 | 3 | A |
| 3 | 241 bzw 17 | E |
| 4 | 3 | A |
| 5 | 5 | B |
| 6 | 3 | A |
| 7 | 13 | C |
| 8 | 3 | A |
| 9 | 5 | B |
| 10 | 3 | A |
| 11 | 7 | D |
| 12 | 3 | A |
| 13 | 5 | B |
| 14 | 3 | A |
| 15 | 17 bzw 241 | F |
| 16 | 3 | A |
| 17 | 5 | B |
| 18 | 3 | A |
| 19 | 13 | C |
| 20 | 3 | A |
| 21 | 5 | B |
| 22 | 3 | A |
| 23 | 7 | D |
| 24 | 3 | A |
| 25 | 5 | B |
| 26 | 3 | A |
| 27 | 241 bzw 17 | G |
| 28 | 3 | A |
| 29 | 5 | B |
| 30 | 3 | A |
| 31 | 13 | C |
| 32 | 3 | A |
| 33 | 5 | B |
| 34 | 3 | A |
| 35 | 7 | D |
Bemerkung
Eine berechtigte Frage wäre jetzt, warum man nicht einfach einen Beweis dieser Art für eine oder alle der verbleibenden k-Werte zusammenbaut. Das würde das aufwendige Testen der ganzen Zahlen überflüssig machen, da man dann auch ohne eine Primzahl zu finden zeigen kann, dass ein k-Werte eine Riesel Zahl ist. Man hat natürlich sowas versucht, aber falls es einen solchen Beweis geben sollte, ist er ungleich schwerer. Für jedes beliebige n hat man hier bei Probedivision bis 241 einen Faktor gefunden. Bei den übrigen k-Werten ist das nicht so einfach. Es ist allerdings nicht ausgeschlossen, dass in Zukunft plötzlich so ein Beweis entwickelt wird.
