| Autor |
Beitrag |
    
Felix Yu (Felyu)
| | Veröffentlicht am Freitag, den 11. Mai, 2001 - 15:08: | 
|
Hallo,
ist es möglich mit Induktion möglich, zu beweisen, dass 2^(2^n)+1 immer eine Primzahl ist??
Ich weiss nicht, wie man das anstellen soll.
Felix |
Hans (Birdsong)
| | Veröffentlicht am Freitag, den 11. Mai, 2001 - 16:44: |
|
Nein, denn die Aussage ist falsch. Euler wusste schon 1732 :
2^(2^5) + 1 = 641*6700417
Hans |
Felix Yu (Felyu)
| | Veröffentlicht am Freitag, den 11. Mai, 2001 - 22:02: |
|
Hallo!
Ich glaube ich habe die Formel nicht ganz richtig aufgeschrieben. Hier noch mal die Aufgabenstellung: Wir brtrachten Zahlen der Formel 2^m+1 m Element n. Berechnen Sie diese Zahlen für m=1..10 und stellen Sie eine Vermutung auf, welche Bedingung m erfüllen muss, falls 2^m+1 eine Primzahl ist. Beweisen Sie Ihre Vermutung.
Also, habe ich eingesetzt. Für m=1,2,4,8,16 sind das Primzahlen. Tja, nun weiss ich nicht weiter. Für mich schien das Beweis genug zu sein. Bei den anderen zwischen m=16..32 gibt es ebenfalls keine Primzahlen. Du hast mir die Vermutung zerstört- Aber nochmal, ist es möglich, dass man mit einer Induktion beweisen kann, dass eine Formel immer eine Primzahl ergibt? Habs irgendwie mit der Eulerschen Funktion versucht zu lösen. Hat nicht hingehauen, weil die Vorraussetzung nicht stimmt, aber ist das ein Lösungsweg. Denn bei einer Induktion arbeitet man ja mit einer Gleichung. Bei dieser Aufgabe habe ich Probleme eine Gleichung aufzustellen. So würde die Behauptung so aussehen(Beispiel, dass nat. nicht stimm): 2^m ist eine Primzahl p. Wie könnte man das als eine Gleichung umbauen? Mit der o.g. Behauprung kann ich nicht arbeiten, weil 2^m und p keine gemeinsames Element haben(wie denn auch), aber bei einer normalen Induktion stehen auf beiden Seiten der Gleichung eine gemeinsame Variable. Tja, ich muss erst mal eine neue Vermutung aufstellen.
Felix |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 11. Mai, 2001 - 22:40: |
|
Nein, denn es gibt keine einzige bekannte Formel, die immer nur Primzahlen liefert.
Nicht daß es alles erklärt, aber immerhin ein Link zum Thema: Matheplanet.de
Gruß
Matroid |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Samstag, den 12. Mai, 2001 - 00:20: |
|
Hallo felix
Du hast die Ausage falsch rum gelesen. Die Frage ist nicht, ob man aus einer Bedingung aus dem Exponenten m schließen kann, dass 2m+1 eine Primzahl ist. Es muss genau andersrum heißen: Was muss für m erfüllt sein, damit überhaupt (potentiell) die Möglichkeit besteht, dass 2m+1 eine Primzahl SEIN KANN. Mit mathematisch typischen Folgerungen heißt dass: Ist 2m eine Primzahl, was folgt daraus?
Wenn man sich nun die Werte anschaut, so kommt man auf die Idee, dass wenn 2m+1 prim ist, m eine Zweierpotenz ist. Schauen wir uns die Werte 2m+1, so kommen wir zu der Vermutung, dass wenn m keine Zweierpotenz, 3 ein Teiler von 2m+1 ist. Nun benutzen wir ein elementares Ergebnis der Logik: (aus A folgt B) ist äquivalent zu (aus nicht B folgt nicht A).
Also beweisen wir statt (2m+1 prim => m Zweierpotenz): m keine Zweierpotenz => 2m+1 keine Primzahl, aufgrund unserer bisherigen Überlegungen zeigen wir, dass 2m+1>3 und 3 ein Teiler von 2m+1 ist.
Der erste Teil ist klar, denn ist m keine zweierpotenz, so ist m>2 => 2^m+1>4+1=5
Für den zweiten überlegen wir uns folgendes: Ist m keine Zweierpotenz, so hat m einen ungeraden teiler, d.h. m=(2n+1)k für k,n natürliche Zahlen, k>1.
Dazu berechnen wir:
(2m+1)mod 3=(2k(2n+1)+1)mod 3=((2²)n*2+1)mod 3=(1n*2+1)mod 3=(2+1)mod 3=0
Also ist (2m+1) durch 3 teilbar, also insgesamt keine Primzahl.
Ich habe mir gerade auch nen Beweis über die Binärdarstellung von 2m+1 überlegt. Wenn Du dran interessiert bist, sag bescheid.
viele Grüße
SpockGeiger |
Felix Yu (Felyu)
| | Veröffentlicht am Samstag, den 12. Mai, 2001 - 13:17: |
|
Hallo Spock Geiger,
ich konnte Deine Argumentation nicht ganz nschvollziehen. Konkret was ich
verstanden habe. Ich soll beweisen, dass für alle Zahlen 2^m+1 mit ungeraden
Exponenten m(>1) keine Primzahlen sein können(da bei ). Daraus folgt: Wenn
2^m+1 eine Primzahl, dann ist m eine Zweierpotenz(Umkehrung gilt nicht, da
für m=2^5 keine Primzahl rauskommt). Ist das so richtig?
Gruss
Felix |
Felix Yu (Felyu)
| | Veröffentlicht am Samstag, den 12. Mai, 2001 - 13:19: |
|
Sorry, habe bei meinem letzten Beitrag was vergessen. "(da bei m="ungerade Zahl", die 3 die 2^m+1 teil)" |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Samstag, den 12. Mai, 2001 - 16:26: |
|
Hallo Felix
Nicht ganz. Wir zeigen nicht nur, dass m nicht ungerade sein kann (dann wäre die Umkehrung nur, dass m gerade sein muss), sondern, dass m keinen ungeraden Teiler besitzen darf.
Ansonsten hast Du den Rest richtig verstande.
viele Grüße
SpockGeiger |
|
