Die Mathe-Redaktion - 17.01.2018 10:13 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 746 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Zahlentheorie » Primzahlen - sonstiges » Exponenten von Mersenne-Primzahlen finden
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Exponenten von Mersenne-Primzahlen finden
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2016-08-08


Hallo,

ich habe eine Vermutung die ich euch gerne vorstellen würde...

Es geht darum, dass die Exponenten von Mersenne Primzahlen (2,3,5,7,13,17,19,31,61... OEIS: A000043)in einer bestimmten Zahlenreihe (1,2,4,3,6,10,12,4,8... OEIS: A002326) nur genau einmal auftreten während alle anderen natürlichen Zahlen mehrfach auftreten...

Hierzu der Paricode:

a(n)=if(n<0, 0, znorder(Mod(2, 2*n+1)))

Bestätigen und dann folgendes eingeben:

n=1

Bestätigen und folgendes eingeben:

while(a(n) != 31, n++)

Bestätigen und nun sucht er sich ein Wolf... In diesem Fall sucht er also solange in der Reihe A002326 bis die 31 das erste Mal auftritt...

Nun nur noch einmal

n

eingeben und bestätigen. Er gibt die Stelle aus an der die 31 das erste Mal auftritt...

Wenn ihr die Reihe A002326 aufgelistet haben wollt dann könnt ihr folgendes schreiben:

a(n)=if(n<0, 0, znorder(Mod(2, 2*n+1)))

und dann

for(i=1,100,printf("a(%2d)=%2d\n",i,a(i)))

z.B. für die ersten 100 n.

Was ist mir aufgefallen:

Gerade Zahlen treten am häufigsten auf. Dann kommen die ungeraden Nichtprimzahlen. Dann kommen die Primzahlen die keine Exponenten von Mersenne Primzahlen darstellen. Und als letztes die nur scheinbar einmal auftreten sind die bekannten Mersenne Primzahl Exponenten: 2,3,5,7,13,17,19,31,61...

Das Problem an der ganzen Sache: Grundsätzlich ist es so, dass jede Zahl n an der Stelle <math>k=\frac{2^n}{2}-1</math> auftritt. Der Unterschied von Mersenne Primzahl Exponenten und allen anderen Zahlen ist nun, dass alle Zahlen ausser den Mersenne Primzahl Exponenten schon vorher auftreten.

Als Beispiel:

Die Stelle <math>k</math> an der die Zahl <math>n=7</math> das erste Mal auftritt ist <math>k=\frac{2^7}{2}-1</math>. Die Zahl <math>n=11</math> allerdings tritt schon an Stelle <math>k=11</math> auf.

Das bedeutet, dass z.B. für den Mersenne Primzahl Exponent <math>n=61</math> der Rechner genau <math>\frac{2^{61}}{2}-1</math> Zahlen prüfen muss... Somit kann man mit einem Heim-PC gerade noch so die Zahl 31 überprüfen... Andere Zahlen lassen sich allerdings schneller finden weil sie mehrfach und somit auch eher auftreten...

Vielleicht hat jemand von euch noch eine Idee für einen schnelleren Algorithmus...

Gruß

blindmessenger



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2016-08-08


Deine zweite Folge beschreibt die Ordnung von 2 modulo ungerader Zahlen 2n+1, d.h., für jedes solche ungerade 2n+1 ist also die kleinste positive Zahl o gesucht, sodass <math>2^o-1</math> durch 2n+1 teilbar ist.

Deine Vermutung lautet also: Genau die Exponenten p von Mersenne-Primzahlen <math>2^p-1</math> sind Ordnung von zwei modulo nur je einer ungeraden Zahl 2n+1, während alle anderen natürlichen Zahlen ( > 0 ) Ordnung von 2 modulo verschiedener ungerader Zahlen <math>2n_1+1</math> und <math>2n_2+1</math> sind.


Zuerst die "Hinrichtung": Der Exponent p einer Mersenne-Primzahl ist bekanntlich erst einmal selbst prim (da <math>2^{ab}-1=2^{ab}-1^{ab}</math> durch <math>2^a-1^a=2^a-1</math> teilbar ist). Dieses p ist also genau dann Ordnung von 2 modulo einer ungeraden Zahl 2n+1, wenn <math>2^p-1</math> durch 2n+1 teilbar ist. (Die zusätzliche Forderung, dass dies der kleinste Exponent ist, sodass diese Teilbarkeit gilt, ist automatisch erfüllt, da die Ordnung Teiler des Exponenten und größer als 1 sein muss, was bei einer Primzahl p nur diese selbst zulässt.) Da aber <math>2^p-1</math> eine Primzahl ist, muss also <math>2n+1=2^p-1</math> gelten, für welches die Aussage aber trivial ist. Es gibt also, wie behauptet, genau eine ungerade Zahl 2n+1, für die der Exponent p einer Mersenne-Primzahl Ordnung von 2 modulo 2n+1 ist.

Nun die Rückrichtung: Hier sollen wir für jedes o, welches nicht Exponent einer Mersenne-Primzahl ist, je zwei verschiedene ungerade Zahlen angeben, modulo derer die Ordnung von 2 beidesmale o ist. Eine solche Zahl ist immer trivialerweise <math>2^o-1</math> selbst. Es genügt also jweils eine weitere, kleinere anzugeben.

Sei zuerst dafür o eine Primzahl. Da o nicht Exponent einer Mersenne-Primzahl ist, ist <math>2^o-1</math> keine Primzahl, also Produkt zweier ungerader Zahlen <math>2n_1+1</math> und <math>2n_2+1</math>, die beide größer als 1 sind. Für beide gilt nun, dass <math>2^o-1</math> durch sie teilbar ist, d.h., die Ordnung von 2 modulo dieser beider jeweils Teiler von o sein muss. Da o aber prim ist, stehen als Teiler nur 1 und o zur Verfügung wobei wegen <math>2n_i+1>1</math> die 1 nicht in Frage kommt, also in beiden Fällen die Ordnung von 2 nun o lauten muss.

Als nächstes sei o eine Primzahlpotenz, aber keine Primzahl, d.h., wir können o schreiben als <math>o=p^k \cdot p</math> für eine Primzahl p und eine ganze Zahl k > 0. Dann ist <math>2^o-1=2^{p^k \cdot p}-1=\left(2^{p^k}-1\right)\left(2^{(p-1)p^k}+2^{(p-2)p^k}+\dots+2^{(p-p)p^k}\right)</math>. Dabei ist jeder Summand des zweiten Faktors kongruent 1 modulo <math>2^{p^k}-1</math> und also der gesamte zweite Summand kongruent p modulo <math>2^{p^k}-1</math>. Für p=2 stellen wir direkt fest, dass p kein Teiler von <math>2^{p^k}-1</math> sein kann. Ansonsten ist die Ordnung von 2 modulo p Teiler von p-1 und > 1, also keinesfalls Teiler von <math>p^k</math>. Damit ist also p auch in diesem Fall nicht Teiler vom ersten Faktor und deshalb sind für alle p die beiden Faktoren teilerfremd. Dies bedeutet, dass die Ordnung von 2 modulo jedem von Eins verschiedenem Teiler des zweiten Faktors zwar Teiler von <math>o=p^{k+1}</math> sein muss, aber nicht von <math>p^k</math> sein kann (weil es sonst auch den ersten Faktor teilen müsste, was ein Widerspruch zur Teilerfremdheit der beiden Faktoren wäre), also genau gleich o ist. Also ist insbesondere der zweite Faktor selbst ein solcher, modulo dem die 2 die Ordnung o hat; und es ist dieser kleiner als <math>2^o-1</math>.

Ähnlich läuft auch der Fall, dass o das Produkt zweier verschiedener Exponenten von Mersenne-Primzahlen ist: Sei o=pq mit <math>p < q</math> und Primzahlen <math>2^p-1</math> und <math>2^q-1</math>. Dann ist wieder <math>2^o-1=\left(2^q-1\right)\left(2^{(p-1)q} + 2^{(p-2)q} + \dots +  2^{(p-p)q}\right)</math> und der zweite Faktor analog kongruent p modulo <math>2^q-1</math>. Da dies aber verschiedene Primzahlen sind, sind wieder beide Faktoren teilerfremd, d.h. auch wieder, dass die Ordnung von 2 modulo des zweiten Faktors ein Teiler von o, aber nicht von q ist, und also o selbst sein muss. Auch hier haben wir also einen zweiten Wert gefunden, modulo dem 2 die Ordnung o besitzt.


Abschließend sei o nun das Produkt zweier teilerfremder Faktoren > 1, d.h. o=ab mit a, b > 1 und ggT(ab)=1. Ist die Ordnung von 2 modulo n gleich a und modulo m gleich b, so rechnet man schnell nach, dass die Ordnung von 2 modulo nm gleich ab ist. Gibt es also oBdA zwei verschiedene Werte <math>n_1\neq n_2</math>, modulo derer die Ordnung von 2 gleich a ist, erhält man daraus auch sofort zwei verschiedene Werte <math>n_1m</math> und <math>n_2m</math>, modulo derer dann die Ordnung von 2 gleich o ist.


Da sich alle natürlichen Zahlen, die nicht Exponent einer Mersenne-Primzahl sind, so darstellen lassen, ist die Behauptung damit bewiesen.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 773
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2016-08-08


Hallo blindmessenger... ich versuche das mal für mich zu übersetzen (da ich mir zumindest bis jetzt unter der Folge A0023226 nichts vorstellen konnte)


A002326 gibt an: <math>2^{(a_k)} \mod (2k+1) = 1</math>
Also es gibt an der k-ten Stelle den kleinsten Exponenten an, so dass die entsprechende 2er-Potenz bei Division durch 2k+1 den Rest 1 lässt...
etwa (beginnend bei k = 0):
<math>2^1 \mod 1 = 1 \rightarrow a_0 = 1\\
2^2 \mod 3 = 1 \rightarrow a_1 = 2\\
2^4 \mod 5 = 1 \rightarrow a_2 = 4\\
2^3 \mod 7 = 1 \rightarrow a_3 = 3\\
...</math>

A000043 gibt an: <math>2^{(a_l)} - 1 \in prim</math>
Also es gibt alle Exponenten an, so dass <math>2^x-1</math> eine Primzahl (entsprechend dann eine Mersenne-Primzahl) ist.


Da diese Exponenten laut deiner Theorie nur einmalig in A002326 vorkommen sollen, so kann man die Theorie auch so formulieren?

Wenn <math>2^n - 1 \in prim, n \in \IN</math>, so existiert genau ein <math>k \in \IN</math>, so dass <math>2^n \mod (2k+1) = 1</math>. Für alle anderen k ist dies ungleich 1.

Subtrahiert man von der Schlussfolgerung die 1, so ergibt sich:
<math>(2^n-1) \mod (2k+1) = 0</math>

Da laut Bedingung <math>2^n - 1 \in prim</math>, so kann es auch nur zwei <math>2k+1</math> geben, welches diese Primzahl teilt - da Primzahlen außer 1 und sich selbst keinen Teiler haben.
Oder anders ausgedrückt für alle Primzahlen p gilt:
fed-Code einblenden

Beweis:
Sei k kein Teiler von p, so lässt p bei Division durch k einen Rest > 0. Da p eine Primzahl ist, besitzt es nur die Teiler 1 und p. Insbesondere gilt immer: z mod k = z, wenn k > z.

Somit müsste dieses <math>n</math>, so dass <math>p = 2^n-1 \in prim</math> an der Stelle <math>2k+1 = p = 2^n-1 \rightarrow k = 2^{n-1}-1</math> oder an der Stelle <math>2k+1 = 1 \rightarrow k = 0</math> in der Folge A002326 vorkommen.
An anderen Stellen kann dieses <math>n</math> nicht vorkommen, da <math>p</math> sonst keine Primzahl wäre, sondern noch andere <math>2k+1</math> als Teiler besäße.


Betrachten wir also diese möglichen Stellen:
(1) <math>k = 0</math>
Hier gilt schon <math>a_0 = 1</math> (siehe oben) und dies ist keine Potenz für eine Mersenne-Primzahl, da <math>2^1-1 = 1</math> nicht prim ist. Somit auch nicht in A000043 enthalten.

Somit können diese Potenzen -wenn sie denn in der Folge A002326 vorkommen- nur an einer einzigen Stelle vorkommen:
(2) <math>k = 2^{n-1}-1</math>
<math>2^{(a_k)} \mod (2k+1) = 1\\
2^n \mod (2^n-1) = 1</math>
Diese Aussage ist ziemlich trivial. Damit dies auch das erste <math>a_k</math> ist, welche die Bedingung erfüllt, noch der Beweis:
Sei <math>m < n</math> und <math>n > 1</math>, so ergibt sich: <math>2^m \leq 2^{n-1} < 2^n - 1</math>
Damit ergibt sich:
<math>2^m \mod (2^n-1) = 2^m</math>, denn: z mod k = z, wenn k > z.

Damit ist dieser Rest für alle <math>m < n</math> ungleich 1 (wenn man den Exponenten <math>m=0</math> für die Folge A002326 nicht zulässt, denn dann wäre die Folge trivial). Und erstmalig für den Exponenten <math>n</math> wird der Rest 1.



Damit ist gezeigt, dass alle Exponenten von Mersenne-Primzahlen genau einmal in der Folge A002326 vorkommen müssen.

Man müsste jetzt noch zeigen, dass alle anderen Zahlen in dieser Folge häufiger vorkommen. [vielleicht morgen dann]

[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2016-08-08


@cyrix

Meine Güte... Ich bin beeindruckt... Was soll ich dazu sagen...

Wie lange hast Du dafür gebraucht?

Bis ich das verstanden habe, wird noch viel Wasser den Rhein hinunterfliessen... Ich rechne ja schon eine ganze Zeit und habe mich auch schon mit einigen mathematischen Themen auseinandergesetzt, aber ich habe mich erst wenig mit Beweistechniken befasst...

Fällt mir glaube ich auch unheimlich schwer...

@MartinN

Hier bin ich genauso beeindruckt...




[Die Antwort wurde nach Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2016-08-08


Und was glaubt ihr: Kann man damit den Lucas-Lehmer Test verbessern? Ich glaube ja eher nicht... Ist wohl eher so ein theoretischer aber nicht praxistauglicher Test...



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2016-08-08


2016-08-08 02:59 - blindmessenger in Beitrag No. 4 schreibt:
Und was glaubt ihr: Kann man damit den Lucas-Lehmer Test verbessern? Ich glaube ja eher nicht... Ist wohl eher so ein theoretischer aber nicht praxistauglicher Test...

Nicht praxistauglich? Immerhin ist es der schnellste Primzahltest, der bekannt ist. Und genau deshalb gibt es auch kaum Chancen, dieses schon äußerst effektive Verfahren noch deutlich zu verbessern.


Diese Überlegungen haben damit allerdings gar nichts zu tun.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2016-08-08


Du hast mich falsch verstanden: Ich meinte doch meine "ehemalige" Vermutung als nicht praxistauglich... Nicht den Lucas-Lehmer Test...



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 773
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2016-08-08


Ich verstehe nicht ganz, wie du deine Erkenntnis mit dem Lucas-Lehmer-Test verknüpfen möchtest. Der basiert ja auf etwas anderem (der Lucas-Folge).

Aus deiner Erkenntnis könnte man basteln: Ich durchsuche die Folge A002326 nach allen Einträgen/Werten, die einmalig vorkommen. Oder ich habe eine Mersenne-Zahl und überprüfe ob deren Wert in dieser Folge einmalig vorkommt.
Aber um erstmalig auf den Wert der Mersenne-Zahl in dieser Folge zu stoßen, müsstest du (p-1)/2 Werte überprüfen... denn an dieser Stelle kommt der Eintrag n = log_2 (p+1) einmalig vor. Und dann müsstest du weiter überprüfen, um zu schauen, ob dieser Wert auch einmalig in A002326 vorkommt - das Stelle ich mir ziemlich aufwendig vor.

Du bräuchtest denke ich dazu noch ein anderes Kriterium:
Wenn n in der Folge A002326 mehrmalig vorkommt, dann muss es bis zu einer Stelle s(n) aufgetreten sein. Wenn diese Funktion s(n) angebbar ist, dann könnte das ev. ein effektiver Test werden.
Dann hat man den Exponenten einer Mersenne-Zahl (welche für eine Mersenne-Primzahl selbst eine Primzahl sein muss) und schaut, ob bis s(n) in der Folge A002326 dieses n schon vorkam.
Oder allgemeiner: Wähle eine Primzahl p, und schaue ob bis s(p) diese Primzahl p in A002326 enthalten ist.

Die Schwierigkeit wäre natürlich, ob es überhaupt so ein s(n) gibt... aber die Idee finde ich interessant :D (so würde ich zumindest versuchen einen Primzahltest daraus zu basteln)



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2016-08-08


Ich vermute das jede Zahl <math>n</math> in der Liste immer das letzte Mal an der Stelle <math>k=\frac{2^n}{2}-1</math> auftritt. Es gibt somit immer für jede Zahl eine obere Grenze.

Für 2,3,5 und 7 habe ich das z.B. bis zu <math>n=1.000.000</math> getestet.

Das kann man glaube ich auch grafisch mit Hilfe der Matrizen zeigen...

Aber Du hast Recht, so roh wie der Test jetzt ausschaut kann man wenig Mersenne Primzahlexponenten finden...

Man müsste es verbessern... Fühl Dich frei und wir nennen ihn dann blindmessenger-MartinN-cyrix-Primzahltest... wink





  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 773
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2016-08-08


Ja, s(n) = 2^(n-1) - 1 ist eben jene Schranke, wenn n der Exponent einer Mersenne-Primzahl ist...
Alle anderen (ungeraden) n sollten hoffentlich deutlich eher mal Verwendung finden.


Eine alternative Überlegung von mir war noch, es umgedreht zu machen...
Theorie: n ist der Exponent einer Mersenne Primzahl, wann 2^n mod (2k+1) > 1 für alle k <= s(k). Das man solch eine Schranke für k findet. Aber das sieht mir nach einem sehr banalen Primzahltest aus:
fed-Code einblenden
(der so auch für alle möglichen Primzahlen funktionieren würde - und denke nicht, dass es da eine besser Schranke s(k) groß gibt)



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2016-08-08


Um das mal ein bisschen einschätzen zu können...

Wie lange braucht man für so einen Beweis wie ihr ihn mir vorgelegt habt?

Und wie lange braucht man um sowas zu können? confused






  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2016-08-08


Ich hab gestern Abend vielleicht ne Stunde bis anderthalb drangesessen das aufzuschreiben. Dabei war die Idee ja relativ kanonisch.

Wie lang man braucht, um dergleichen zu sehen? Mehr als mit den Begriffen ein wenig zu spielen, war hier gar nicht von Nöten. Will sagen: Beschäftigt man sich etwas intensiver damit, dann kommt das von ganz allein.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2017-03-10


Eventuell eine kleine Algorithmus Verbesserung:

Wenn folgende Gleichung für das kleinste n erfüllt ist

<math>(2^p-1)mod(n\cdot p+1)=0 ,\ \ n=\{2,3,4,5,...\}</math>

und gleichzeitig gilt folgendes:

<math>(2^p-1)=(n\cdot p+1)</math>

dann ist p auch ein Mersenne prime Exponent...

Zur Berechnung eines Mersenne Prime Exponents taugt das nicht viel... Aber vielleicht kann man so Nicht-Mersenne-prime-exponenten schneller ausschließen oder man findet eine Grenze...


-----------------
Gruß blindmessenger



Wahlurne Für blindmessenger bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2017-03-10


Man könnte mit folgender Berechnung Mersenne Primzahlen vorsieben:

GP/Pari:

a(n)=(2^(p)-1)%(n*p+1)
Return
n=2
Return
while(a(n) != 0, n++)
Return
n
Return

Für die Zahl <math>2^{13466807}</math> (also <math>p=13466807</math>) könnte man so z.B. eine Mersenne Primzahl schnell ausschliessen.



-----------------
Gruß blindmessenger



Wahlurne Für blindmessenger bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3633
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2017-03-10


(2017-03-10 02:50 - blindmessenger in <a
Zur Berechnung eines Mersenne Prime Exponents taugt das nicht viel... Aber vielleicht kann man so Nicht-Mersenne-prime-exponenten schneller ausschließen oder man findet eine Grenze...

Ist halt nur leider wieder mal "ein alter Hut", mal abgesehen davon, dass dies nur für ungerade Primzahlexponenten von Mersennezahlen gilt (siehe den zweiten Punkt unter den Teilbarkeitseigenschaften hier). Insbesondere kann man für diese Mersennezahlen auch Teiler ausschließen, welche in den Restklassen 3 und 5 mod 8 liegen.



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2016
Mitteilungen: 718
Aus: NRW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2017-03-10


Alles klar... War ja nur eine Idee...


-----------------
Gruß blindmessenger



Wahlurne Für blindmessenger bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 331
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2018-01-03 21:29


Wegen Mersenneprimzahl.

Es gibt eine neue !

Die 50. bekannte lautet

2^77232917-1 mit 23,249,425 Stellen.



  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1082
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-01-04 03:03


Ein paar Fragen:

2 Zahlen a und b sind teilerfremd, wenn
b=q mod a
also a b nicht teilt mit Rest q und gleichzeitig q a nicht teilt?


Dann ist wieder <math>2^o-1=\left(2^q-1\right)\left(2^{(p-1)q} + 2^{(p-2)q} + \dots +  2^{(p-p)q}\right)</math> und der zweite Faktor analog kongruent p modulo <math>2^q-1</math>. Da dies aber verschiedene Primzahlen sind, sind wieder beide Faktoren teilerfremd, d.h. auch wieder, dass die Ordnung von 2 modulo des zweiten Faktors ein Teiler von o, aber nicht von q ist, und also o selbst sein muss.

Warum kann die Ordnung von 2 nicht p sein?

Und warum genau müssen die Zahlen nochmal teilerfremd sein? Damit der erste Faktor für einen Teiler des zweiten Faktors nicht geteilt werden kann? Was ist denn wenn die Zahlen zwar nicht teilerfremd sind, aber der zweite Faktor den ersten Faktor auch nicht teilt??



Wahlurne Für digerdiga bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1082
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2018-01-04 20:17


Keiner der mir die vielleicht triviale Frage beantworten kann?



Wahlurne Für digerdiga bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 45108
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-01-04 20:36


2018-01-04 03:03 - digerdiga in Beitrag No. 17 schreibt:
2 Zahlen a und b sind teilerfremd, wenn
b=q mod a
also a b nicht teilt mit Rest q und gleichzeitig q a nicht teilt?
Hi digerdiga,
das stimmt nicht. Um die Teilerfremdheit zu prüfen, muss der euklidische Algorithmus bis zu Ende durchgeführt werden.
Was du aber machen willst: nur einen Schritt durchführen, und natürlich genügt das nicht, um daraus einen Schluß über die Teilerfremdheit oder Nicht-Teilerfremdheit zu ziehen.
Gruß Buri



Wahlurne Für Buri bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1082
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2018-01-04 22:17

\(\begingroup\)
Hallo Buri,
Ich orientier mich mal an:

<math>2^o-1=2^{p^k \cdot p}-1=\left(2^{p^k}-1\right)\left(2^{(p-1)p^k}+2^{(p-2)p^k}+\dots+2^{(p-p)p^k}\right)</math>
Zuerst betrachte ich also \(\left(2^{(p-1)p^k}+2^{(p-2)p^k}+\dots+2^{(p-p)p^k}\right) \equiv p \mod \left(2^{p^k}-1\right)\).
Müsste ich nicht dann wie auch gemacht \(\left(2^{p^k}-1\right) \equiv ? \mod p\) betrachten?

Bricht der Algorithmus nicht erst ab, wenn kein Rest mehr übrig bleibt?
\(\endgroup\)


Wahlurne Für digerdiga bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2018-01-04 22:32


Man rechnet schnell nach, dass <math>ggT(2^a-1,2^b-1)=2^{ggT(a,b)}-1</math> ist. Damit folgt wegen <math>ggT(p-1,p^k)=1</math> direkt <math>ggT(2^{p-1}-1,2^{p^k}-1)=1</math>, was wegen des kleinen Fermats für ungerade Primzahlen (<math>p|2^{p-1}-1</math>) direkt die Teilerfremdheit von <math>p</math> und <math>2^{p^k}-1</math>, und damit auch die gewünschte zwischen <math>2^{p^k}-1</math> und dem zweiten Faktor zeigt.

Cyrix



Wahlurne Für cyrix bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1082
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-01-04 23:27


Der letzte Schritt ist mir irgendwie nicht ganz klar.
Wieso folgt aus ggT(p,2^p^k-1)=1 auch die Teilerfremdheit des 2. Faktors?



Wahlurne Für digerdiga bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-01-04 23:33

\(\begingroup\)
Oben ist aufgeführt, dass der zweite Faktor kongruent p mod dem ersten Faktor $2^{p^k}-1$ ist. Also existiert eine ganze Zahl $q$, sodass der zweite Faktor gleich $q \cdot (2^{p^k}-1) + p$ ist. Jeder gemeinsame Teiler der beiden Faktoren muss also auch ein gemeinsamer Teiler von $2^{p^k}-1$ und $p$ sein. Da gibt es aber nur die 1, wie nachgerechnet.

Cyrix
\(\endgroup\)


Wahlurne Für cyrix bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1082
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2018-01-05 00:28


Im Fall o=pq:
Ist die Forderung p<q eigentlich wichtig?



Wahlurne Für digerdiga bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2671
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-01-05 01:24


Nein, man braucht nur <math>p\neq q</math>.

Cyrix



Wahlurne Für cyrix bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
blindmessenger hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]