An die Mathefreaks: Kennt ihr schwierige Rätsel aus der Zahlentheorie usw. die man beweisen muss?
Ich suche ein paar schwierige Rätsel, die mir helfen das beweisen von mathematischen Aussagen zu üben. Am besten solche Aufgaben aus dem Studium direkt, also was in so einer Klausur dran kommt.
Ich studiere zwar kein Mathe, aber interessiere mich sehr dafür.
8 Antworten
Aufgabe 1: Wenn a und b teilerfremde ganze Zahlen sind, dann gibt es ganze Zahlen x und y, sodass
ax + by = 1 ist.
Aufgabe 2: Mit "a mod b" bezeichne ich mal den Rest der Division von a durch b. Sei p eine Primzahl. Dann ist
a^p mod p = a mod p.
Da du dich ja anscheinend auch für die Anwendungen interessierst: diese Aussagen sind grundlegend für das Verständnis von Verschlüsslungsverfahren wie RSA.
Wenn du etwas bei Amazon bestellen willst, musst du ihnen irgendwie deine Kreditkartennummer übermitteln. Es hat aber natürlich niemand extra ein Kabel von dir zu Amazon gelegt, wo sonst niemand dranhängt. Du schickst also alle Infos an Amazon über das "öffentliche Kabel". Das bedeutet aber, dass dein Nachbar, der am gleichen Kabel hängt, auch deine Kreditkartennummer kennen kann. Deswegen braucht man Verschlüsselung. Aber da du und Amazon euch nie persönlich getroffen habt um einen Schlüssel zu vereinbaren, müsst ihr jetzt irgendwie einen Schlüssel vereinbaren, während der Nachbar mithört, ohne dass der Nachbar den Schlüssel kennt. Das klingt unmöglich, aber das ist das, was dein Computer andauernd macht.
Damit das funktionieren kann, benutzen wir heutzutage hauptsächlich die unbewiesene Annahme, dass es unmöglich ist eine Zahl "schnell" in Primfaktoren zu zerlegen. Deswegen interessiert man sich auch so brennend für alle Fragen über Primzahlen: man könnte damit zeigen, dass unsere Verschlüsselung wirklich sicher ist, oder, falls die Vermutungen der Mathematiker nicht stimmen (das ist aber echt unwahrscheinlich) die Verschlüsselungen knacken und alles mithören können. Letzteres wäre ein riesiges Problem, aber das ist wie gesagt echt unwahrscheinlich.
Wenn du möchtest, kann ich dir ein paar heranführende Aufgaben für die Aufgaben oben stellen, die da oben auf anhieb zu lösen ist nämlich garnicht so einfach :)
Beweis mal:
- Jede gerade Zahl, die größer als 2 ist, ist als Summer zweier Primzahlen darstellbar.
- Jede ungerade Zahl, die größer als 5 ist, ist als Summer dreier Primzahlen darstellbar.
Wenn Du die Lösung hast, lass es uns wissen (schnapp Dir vorher aber das Preisgeld für den Beweis der Goldbachschen Vermutungen).
Ich bin jetzt nicht so der Zahlentheoretiker, aber es würde wohl für die Verschlüsselungstechniken helfen sowie für das allgemeine Zahlenverständnis.
Da kann man ja alles behaupten und Mathematiker Jarhunderte beschäftigen ;)
Diese erste Behauptung ist nachgewiesen für alle Zahlen bis 4*10^18, aber eben nicht formal für alle
Wenn sie nicht fûr alle nachgewiesen ist ist es immer noch eine Behauptung ;)
Pi ist nicht periodisch ist auch eine Behauptung . Nachgewiesen bis , stand heute, zur wievielsten stelle. ..... sagt aber nichts aus das es doch noch so sein könnte :)
Dass pi nicht periodisch ist, ist meines Wissens bereits formal bewiesen, wohl über den Widerspruch als Bruch
Ich fand Aufgaben zu dem Legendre Symbol ganz cool (falls es dich interessiert, solltest du am besten in Wikipedia drüber lesen)
Beispiel:
Sei p>= 11 eine Primzahl, man soll zeigen, dass es immer eine ganze Zahl 1 <= a <= 9 gibt, sodass
(a/p)=((a+1)/p)=1
gilt.
Wichtig: (a/p) ist kein Bruch sonders das Legendre Symbol, welches entweder 1, -1 oder 0 ist.
Oder eine Aufgabe zu Teilbarkeit:
Sei p eine Primzahl ungleich 2 und 5,
Zu zeigen:
Es gibt unendlich viele natürliche Zahlen der Form
1; 11; 111; usw (also Zahlen die nur aus Einsen bestehen) die durch diese Primzahl Teilbar sind. (Hier ist der kleine Fermat sinnvoll)
Sehr einfach:
Es gibt nur einen Primzahldrilling.
Hat eine natürliche Zahl n keinen primen Teiler, der kleiner oder gleich die Wurzel von n ist, dann ist n prim.
Zur Information:
2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 509 × 59 ist nicht prim
Eine einfache Aufgabe, die ich mir mal selbst als 14-jähriger gestellt habe:
Das Produkt der hintereinander folgenden Primzahlen plus 1 ist keine Quadratzahl.
oder ganz entsprechend
Das Produkt der hintereinander folgenden Primzahlen minus 1 ist keine Quadratzahl.
oder etwas schwerer
Das Produkt der hintereinander folgenden Primzahlen plus 1 ist kein Produkt zweier Primzahlzwillinge x und (x+2) .
Letzthin von einem Studenten als Frage gestellt:
Für welche Primzahlen p und q gilt, dass pq + qp = PZ ebenfalls eine Primzahl ist ?
Etwas anspruchsvoller:
a p mod p = a mod p . ( Kleiner Fermatscher Satz )
Es se Z die Menge der ganzen Zahlen und a, b e Z teilerfremd, dann gibt es Zahlen x, y e Z so, dass a x + b y = 1 ist.
Falls die Lösungen gewünscht werden, kann ich sie hier einstellen. Aber wir sollten damit ein paar Tage warten.
Warum wird eigentlich auf dem Gebiet der Primzahlen so sehr geforscht?
Weil die Primzahlen quasi die Atome der Zahlen sind und die entsprechenden Fragen zwar einfach zu stellen und zu verstehen aber die wesentlichste Frage nach der Folge der Primzahlen immer noch nicht beantwortet ist. Die beiden wichtigsten Aussagen sind über 100 Jahre alt und stammen von C.F. Gauß und dem Gauß-Schüler B. Riemann.
Ein wichtiges Anwendungsgebiet der Zahlentheorie ist die Kryptographie, ein Beispiel ist das RSA Verfahren, wo Primzahlen eine wichtige Rolle spielen
Für welche Primzahlen p und q gilt, dass pq + qp = PZ ebenfalls eine Primzahl ist ?
Antwort: 1, 1 oder 1, 2 .
Im ersten Momment eingafallen
Na, der Klassiker ist doch der Beweis zur Aussage "Es gibt unendlich viele Primzahlen."
Aber den kennst du wahrscheinlich schon, oder?
Oder wie wäre es hiermit: Hat eine natürliche Zahl n keinen primen Teiler, der kleiner oder gleich die Wurzel von n ist, dann ist n prim.
Was würde das eigentlich für den Alltag bedeuten?