Hallo,
diese Aufgabe lässt mich nun schon seit einer Woche stark knobeln.
Vielleicht könnt ihr mir weiter helfen?
Hier nochmal die Aufgabe:
Ist 545^4 + 4^545 prim?
THX
Ansätze
Natürlich habe ich auch schon einige Ansätze durchüberlegt.
545^4 endet sehr sicher auf eine 5
4^545 wird auf alle Fälle Gerade sein.
Somit endet die Zahl auf eine Ungerade Zahl
==> Keine Aussage
Durch Primfaktorzerlegung und Umformung erhält man:
(109*5)^4+2^(2*109*5)
Es gibt keinen gemeinsamen Teiler, der beiden Zahlen.
==> Keine Aussage
Eine Primzahl > 2 ist immer in der Form 4k+1 oder 4k+3.
545^4 + 4^545 = 4k+1
545^4 - 1 + 4^545 = 4k
(545^2 - 1)(545^2 + 1) + 4^545 = 4k Da beide Zahlen links gerade sind, kann man zweimal eine 2 ausklammern, …
Dann kann man 4 kürzen und k ist eine natürliche Zahl.
==> Keine Aussage
Nein
Hallo,
diese Aufgabe lässt mich nun schon seit einer Woche stark
knobeln.
Vielleicht könnt ihr mir weiter helfen?Hier nochmal die Aufgabe:
Ist 545^4 + 4^545 prim?
Wenn du nur ein Ergebnis willst: nein, ist nicht prim.
In Mathematica:
In[1]= PrimeQ[545^4 + 4^545]
Out[1]= False
Mein Rechner arbeitet gerade noch an einer Primfaktorzerlegung.
Grüße,
Moritz
Hallo,
Mein Rechner arbeitet gerade noch an einer
Primfaktorzerlegung.
Ist zwar keine Vollständige Zerlegung, sollte aber stimmen:
13264634072747908684349135042570964634799744598942817868637887399685674733928143053911515706257383390916580334915866585424842505413315361299956590178516238986216565917389053058381703265785821026139489414576389820813279722433720660696636021515823320684351327863593944321381722660223746213949363159606624666472133934520391498014849 = 73 * 181707316065039844991084041679054310065749926012915313269012156160077736081207439094678297345991553300227127875559816238696472676894730976711734112034469027208446108457384288470982236517613986659445060473649175627579174279913981653378575637203059187456867504980738963306598940551010222108895385748035954335234711431786184904313
= 9677 * 1370738252841573698909696707923009676015267603486908945813566952535462925899363754666892188308089634278865385441342005314130671221795531807373833851246898727520571036208437848339537384084511834880592065162383984790046473331995521411246876254606109402123729240838477247223491026167587704241951344384274534098598112485314818437
Ich weiß, dass das keine „schöne“ Antwort ist, aber sie beantwortet deine Frage 
Grüße,
Moritz
Nun,
eine plausible Erklärung würde mir schon mehr gefallen,
ist aber zumindest eine Antwort.
THX André
etwas OT: Ansätze zur Primzahlensuche
Moin,
Eine Primzahl > 2 ist immer in der Form 4k+1 oder 4k+3.
Ich bin zwar ein Fan der Experimentalmathematik und die sagt mir, daß das stimmt. Aber wie beweise ich diese Aussage? Oder wie kam / kommt man drauf?
Neugierig,
Ingo
Hallo,
Eine Primzahl > 2 ist immer in der Form 4k+1 oder 4k+3.
zunächst: Diese Aussage ist wahr, aber die eigentlich gemeinte (und etwas schärfere) ist „Jede Primzahl ist von der Form 6 k + 1 oder 6 k + 5“.
Ich bin zwar ein Fan der Experimentalmathematik und die sagt
mir, daß das stimmt. Aber wie beweise ich diese Aussage? Oder
wie kam / kommt man drauf?
also bitte…
6 k (mit k ∈ N ) kann niemals prim sein, weil stets durch 6 teilbar;
6 k + 2 kann niemals prim sein, weil stets durch 2 teilbar,
6 k + 3 kann niemals prim sein, weil stets durch 3 teilbar,
6 k + 4 kann niemals prim sein, weil stets durch 2 teilbar,
Also bleiben nur 6k + 1 und 6k + 5 übrig für potentielle Primzahlen. „Potentiell“ heißt, dass die Bedingung notwendig, aber nicht hinreichend ist (es gibt haufenweise Zahlen der Form 6k + 1 und 6k + 5, die nicht prim sind).
Gruß
Martin
PS: Wie lautet denn der „nächsthöhere“ Satz?
1 Like
Moin, Martin,
danke, diese Regel hatte ich längst vergessen. Weißt Du zufällig, ob sie einen Namen hat?
Gruß Ralf
Weißt Du zufällig, ob sie einen Namen hat?
Hallo Ralf,
ein solcher ist mir nicht bekannt. Aber diese „Regel“ ist ja auch nur die zweite in einer unendlichen Liste von immer umfangreicher werdenden Regeln – je eine für jedes Produkt der kleinsten Primzahlen (6 = 2 · 3; 30 = 2 · 3 · 5; 210 = 2 · 3 · 5 · 7 usw.):
(1) Jede Primzahl > 2 ist von der Form 2k + 1 (mit k ∈ N ).
(2) Jede Primzahl > 6 ist von der Form 6k + 1 oder 6k + 5.
(3) Jede Primzahl > 30 ist von der Form 30k + 1 oder 30k + 7 oder 30k + 11 oder 30k + 13 oder 30k + 17 oder 30k + 19 oder 30k + 23 oder 30k + 29.
(4) Jede Primzahl > 210 ist von der Form 210k + … oder 210k + … oder 210k + … usw. (sehr lange Liste)
(5) Jede Primzahl > 2310 ist von der Form 2310k + … oder 2310k + … oder 2310k + … usw. (äußerst lange Liste)
Das Prinzip, das diesen Regeln zugrundeliegt, ist nichts anderes als das Sieb des Eratosthenes, einem Algorithmus zum Finden aller Primzahlen unterhalb einer vorgegebenen Schranke. Nähere Infoes dazu unter http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes.
Gruß
Martin
2 Like
Merci!
Moin,
(1) Jede Primzahl > 2 ist von der Form 2k + 1 (mit k
∈ N ).
[…]
Das Prinzip, das diesen Regeln zugrundeliegt, ist nichts
anderes als das Sieb des Eratosthenes, einem
Das leuchtet ein und ist doch so trivial 
. Danke.
Hallo allerseits,
Nun,
eine plausible Erklärung würde mir schon mehr gefallen,
THX André
Oh ja, bin auch etwas enttäuscht. Hätte gedacht, dass jemand einen knackigen mathematischen Beweis hinlegt, wenigstens einen Ansatz dazu. Aber so, schnödes Ausrechnen, welcher Mathematiker rechnet schon
Hat nicht vielleicht doch noch jemand eine Idee für einen mathematischen Beweis???
Mit freundlichen Grüssen
Klaus Bernstein
Besternten Dank! (owT)
Hallo,
Eine Primzahl > 2 ist immer in der Form 4k+1 oder 4k+3.
Ich bin zwar ein Fan der Experimentalmathematik und die sagt
mir, daß das stimmt. Aber wie beweise ich diese Aussage? Oder
wie kam / kommt man drauf?
Naja, jede Primzahl > 2 muss eine ungerade Zahl sein, und jede ungerade Zahl kann man nun mal als 4k+1 oder 4k+3 darstellen.
Grüße,
Moritz