Zahlentheoretische Beweise

Neue Frage »

vektorraum Auf diesen Beitrag antworten »
Zahlentheoretische Beweise
Hi!

In den letzen Zügen noch ein paar Aufgaben zu Beweisen der Elementaren Zahlentheorie, die ich nicht vollständig lösen kann. Da die Beweise extrem kurz sind (vermutlich), stelle ich hier in einem Post alle rein mit meinen bisherigen, etwas dünnen Ansätzen:

1. Z.z.: ist für alle Primzahlen mit p>5 durch 240 teilbar.
Mein Ansatz: Wir müssen also zeigen, dass gilt



Nun kann man aber schreiben:



Ferner: .

Gut, wie bringe ich das nun zusammen?

2. Z.z.: 121 teilt nicht für alle .

Als Hinweis ist gegeben: zeigen sie zunächst: . Das ist einfach zu beweisen: Wie bring ich das mit dem eigentlichen Beweis zusammen, bzw. was bringt der Hinweis?

3. Z.z.: Bestimmen Sie alle Primzahlen, die sowohl als Summe, als auch als Differenz zweier Prinmzahlen dargestellt werden können:

Meine Lösung: 5. Wie kann man aber zeigen, dass es keine weiteren gibt?

Danke euch Wink
Leopold Auf diesen Beitrag antworten »

Bei 1. könnte man so anfangen:

a) Von den drei benachbarten Zahlen ist genau eine durch teilbar, und ist es wegen nicht.

b) Eine Primzahl endet im Dezimalsystem auf oder . Endet auf oder , so endet auf , also auf . Endet dagegen auf oder , so endet bzw. auf .

c) Und jetzt noch die Teilbarkeit durch ...
AD Auf diesen Beitrag antworten »

Oder so für die Teilbarkeit durch 5.
Mystic Auf diesen Beitrag antworten »

ad 2. Zunächste einmal gilt offenbar



Wäre also durch 121 teilbar, so wäre und damit weiter auch durch 11 teilbar. Das ist aber ein klarer Widerspruch.

ad 3.

Sowohl bei der Summenbildung, als auch bei der Differenzbildung muss eine der beiden involvierten Primzahlen 2 sein, wie man sofort sieht. Für die gesuchten Primzahlen p muss daher gelten, dass alle 3 Zahlen p-2,p,p+2 prim sind. Der Rest sollte klar sein.
Leopold Auf diesen Beitrag antworten »

Es soll wohl an zwei Stellen heißen.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Leopold
Es soll wohl an zwei Stellen heißen.


Ja, sorry, das sollte es in der Tat. Hammer
 
 
Leopold Auf diesen Beitrag antworten »

Jetzt liegen die beiden noch näher beieinander, daß sie also nicht beide durch 11 teilbar sind, ist "noch wahrer" geworden. Big Laugh
vektorraum Auf diesen Beitrag antworten »

Ich danke euch für die vielen Antworten! Aufgabe 2 ist mir jetzt klar, bei 1. und 3. muss ich nochmal drüber nachdenken und meld mich dann vielleicht nochmal!
Bjoern1982 Auf diesen Beitrag antworten »

Eine Frage zu 1)

Folgt die Behauptung nicht wegen direkt aus den Eigenschaften des Jacobi-Symbols, sprich insbesondere aufgrund der Multiplikativität im Nenner ?



Damit könnte man doch die Fälle p=2,3,5 direkt auschließen und für alle p>5 gilt offensichtlich die Behauptung verwirrt
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Bjoern1982
Eine Frage zu 1)

Folgt die Behauptung nicht wegen direkt aus den Eigenschaften des Jacobi-Symbols, sprich insbesondere aufgrund der Multiplikativität im Nenner ?



Damit könnte man doch die Fälle p=2,3,5 direkt auschließen und für alle p>5 gilt offensichtlich die Behauptung verwirrt


Jacobisymbole dürfen per definitionem keine geraden Nenner haben.

Im übrigen ist hier gerade der Fall p=2,3,5 trivial und der Fall p>5 nichttrivial (zumindestens vergleichsweise), nämlich deshalb, weil für p=2,3,5 laut Angabe nichts zu zeigen ist.
AD Auf diesen Beitrag antworten »

Das ist es auch, was ich nicht verstehe: Was hat die Tatsache, dass quadratischer Rest modulo irgendwas ist damit zu tun, dass oder durch dieses irgendwas teilbar ist??? Eigentlich nichts.
Bjoern1982 Auf diesen Beitrag antworten »

Ihr habt Recht, das war totaler Unsinn.
Mystic Auf diesen Beitrag antworten »

Für "Algebraiker" hier noch ein Alternativbeweis dafür, dass für Primzahlen p > 5 durch 240 teilbar ist. Man benötigt dazu die sog. Carmichaelfunktion , welche für die prime Restklassengruppe mod n den sogenannten Exponenten angibt, d.h., ist minimal bezüglich der Eigenschaft, dass für alle zu n teilerfremden ganzen Zahlen a gilt



(Bekanntermaßen hat auch diese Eigenschaft, aber eben ohne den Zusatz der Minimalität! Trotzdem wird diese Funktion statt traditionell z.B. für RSA verwendet, und das nicht nur von Laien, wohl eine der seltsamsten Dinge in der Mathematikgeschichte!)

Für die Berechnung von gilt nachfolgendesn einfaches Kochrezept: Ist für eine Primzahlpotenz, so ist einfach



mit der Ausnahme von für wo dann abweichend davon gilt



d.h. obige Formel muss dann um den Faktor 2 nach unten korrigiert werden. Für alle anderen n nimmt man einfach die Primfaktorzerlegung



und definert als das kgV der , i=1,2,..,r. Speziell für n=240 ergibt sich



was dann mehr oder weniger die Lösung der Aufgabe darstellt.
AD Auf diesen Beitrag antworten »

Es ist also für alle , sowie genau dann, wenn es eine primitive Wurzel modulo gibt, d.h. für mit ungerader Primzahl .
heinzelotto Auf diesen Beitrag antworten »

Zu 1:

Es gilt für a mit a teilerfremd zu 3, 5, 16 (leicht nachzuprüfen, z.B. einfach die Restklassen durchgehen):


, und das kgV der drei Moduli ist 240. Dies gilt also für alle Zahlen, die teilerfremd zu 3, 5 und 16 sind, also insbesondere für alle Primzahlen > 5.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Es ist also für alle , sowie genau dann, wenn es eine primitive Wurzel modulo gibt, d.h. für mit ungerader Primzahl .


Ja, stimmt genau, wenn man nur der Vollständigkeit halber den Fall n =1 noch dazunimmt. Insbesondere sieht man, dass für RSA-Moduln n stets gilt , wenngleich sich die beiden Zahlen zugegebenermaßen meist nur um den Faktor 2 unterscheiden.

@heinzelotto

Wenn man in meinem Beweis oben alles, was irgendwie nach höherer Algebra riecht, wegläßt und rein ad hoc argumentiert, kommt am Ende exakt dein Beweis dabei heraus... Ich erwähne das hier nur, da ich mir nicht ganz sicher bin, ob sich das eher zufällig so ergeben hat, oder ob das nicht ohnehin deine Intention war...
heinzelotto Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Wenn man in meinem Beweis oben alles, was irgendwie nach höherer Algebra riecht, wegläßt und rein ad hoc argumentiert, kommt am Ende exakt dein Beweis dabei heraus... Ich erwähne das hier nur, da ich mir nicht ganz sicher bin, ob sich das eher zufällig so ergeben hat, oder ob das nicht ohnehin deine Intention war...


Sorry, ich muss gestehen, mir deinen Beweis nicht durchgelesen zu haben unglücklich
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von heinzelotto
Sorry, ich muss gestehen, mir deinen Beweis nicht durchgelesen zu haben unglücklich


Kein Problem, ad hoc Lösungen haben durchaus ihren Wert, indem sie oft auf geradestem Weg zum Ziel führen für jemanden, der nur an der Lösung selbst interessiert ist... Allerdings hat man dann meist auch nicht viel mehr als gerade die Lösung dieser speziellen Aufgabe, wie man gerade hier sehr schön sieht. Wenn man sich nämlich meine obige Lösung genauer ansieht, so habe ich genau genommen bewiesen den viel allgemeineren

Satz: Für jede positive ganze Zahl n gilt, dass



für alle Primzahlen p, die n nicht teilen.

Der Fall n=240 mit ist dann nur ein winziger Spezialfall davon.
heinzelotto Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Allerdings hat man dann meist auch nicht viel mehr als gerade die Lösung dieser speziellen Aufgabe, wie man gerade hier sehr schön sieht. Wenn man sich nämlich meine obige Lösung genauer ansieht, so habe ich genau genommen bewiesen den viel allgemeineren

Satz: Für jede positive ganze Zahl n gilt [...]


und nicht nur das, durch deinen Beweis bin ich außerdem auf die Carmichael-Funktion aufmerksam geworden und habe noch was dazugelernt smile
Mystic Auf diesen Beitrag antworten »

Ja, es ist unglaublich, was diese unscheinbare Aufgabe so hergiebt... Z.B. könnte man das Ganze noch weiterspinnen und fragen, was denn gerade an n=240 so besonders ist, dass so rekordverdächtig klein ist in Relation zu n. Wenn man weiter nachforscht, wird man sehen, dass dies allgemeiner für Zahlen n der Form



so ist, wobei eine Fermatzahl bezeichnet, von der man hier noch außerdem fordern muss, dass sie und sämtliche Vorgänger prim sind... n=240 wird dann speziell für erhalten...
Mystic Auf diesen Beitrag antworten »

Hier ein kleiner Nachtrag, da ich meinen letzten Beitrag leider nicht mehr editieren kann. In der angegebenen Formel für n braucht selbst nicht prim zu sein, wohl aber müssen es alle Vorgänger sein. Des weiteren sollte auch sein, sodass letztendlich genau die Werte m=2,3,4,5 in Frage kommen...
Mystic Auf diesen Beitrag antworten »

Okay, nun die hoffentlich letzte Korrektur. Obige Formel für Werte von n, für welche relativ klein ist, sollte eigentlich lauten



und der sich ergebende Wert für ist dann gerade



Interessante Werte sind also

mit

mit

mit

usw.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »