Die Mathe-Redaktion - 15.11.2018 05:59 - 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!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
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. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Primitivwurzeln und Primzahlpotenzen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Primitivwurzeln und Primzahlpotenzen
kindi880
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.07.2018
Mitteilungen: 11
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-07-23

\(\begingroup\)
Liebes Forum,
ich sitze momentan an einer Ausarbeitung zum Thema Miller-Rabin-Primzahltest und versuche die Fehlerwahrscheinlichkeit zu beweisen, komme jedoch in einem Punkt nicht mehr weiter. Und zwar versuche ich zu bestimmen, wie viele Elemente a in der Menge  \(B_{p^{e}}\) mit:

\(B_{p^{e}}=\{a \in (Z/p^{e})^{*} | a^{p^{e}-1} \equiv 1 mod p^{e}\}\)

wobei \(p^{e}\) mit e>1 und p>2 eine Primzahlpotenz ist, enthalten sind.

Beweis Idee: Wegen $p^{e}$ ist die Gruppe (Z/p^e)* zyklisch und es existiert eine Primitivwurzel
\(g \in (Z/p^{e})^{*}\). Für jedes a in (Z/p^{e})^* und damit zu jedem \(a \in B_{p^{e}}\) existiert folglich ein \(q_{a} \in N\) mit: \[g^{q_{a}}\equiv a \, \text{mod} \, p^{e}\].

Statt also die Anzahl a herauszufinden, für die gilt  \(a^{p^{e}-1}\equiv 1\) mod p^{e}, könnte man jetzt die Anzahl der Lösungen der Kongruenz
\[(g^{q})^{p^{e}-1}\equiv 1 \, \text{mod} \, p^{e}\] untersuchen.
Die Ordnung von \((Z/p^{e})^{*}\) und somit auch von g ist \(\varphi(p^{e})=p^{e-1}(p-1)\), weshalb für q gelten muss fed-Code einblenden
Nun steht im Beweis, dass diese Kongruenz genau \(t=ggT(q\cdot(p^{e}-1), (p-1)p^{e-1})\) hat und t=p-1 sei. Dies folgt aus folgendem Satz (Exkurs Anfang)
Satz: Sei \[G=\{1,g,g^{2},\ldots, g^{m-1}\}\] eine zyklische Gruppe mit der Ordnung m. Für ein k größer gleich 1 hat die Gleichung \[x^{k}=1\]  genau \(t=\mathrm{ggT}(m,k)\) viele Lösungen in G.
Exkurs Ende
Habe ich das mit dem t=p-1 gezeigt, zeige ich, dass die Menge  \(B_{p^{e}}\) p-1 Elemente hat.

Die Argumentation im Buch, aus dem ich den Beweis erarbeitet ist die folgende:
Wegen der oben zuletzt gezeigten Kongruenz, gilt, dass die Ordnung von g die Potenz teilt, es gilt also:
\[(p-1)p^{e-1} | q\cdot(p^{e}-1) \qquad (GL1)\] Ohne zu zeigen gilt:
\[(p-1) | p^{e}-1) \qquad (GL2)\] Daraus folgt, dass:
\[p^{e-1} | q\cdot\frac{(p^{e}-1)}{(p-1)} \qquad (GL3)\] Da
\[p^{e-1} \nmid p^{e}-1 \qquad (GL4)\] folgt, dass
\[p^{e-1}|q \qquad(GL5)\].
Dies bedeutet, es gibt ein k mit \[q=k \cdot p^{e-1} \qquad (GL6)\].

Bis hierhin habe ich den Beweis vollkommen verstanden. Im Buch wird jetzt folgender Schritt gemacht: Aus (4) und (5) und (6) folgt, dass:
\[t=ggT(k\cdot(p^{e}-1), (p-1)) \] Es wurde also aus dem ggT der Faktor p^(e-1) gekürzt. Hieraus folgt, dann dass t=p-1 ist.
Mein Problem: Müsste man nachdem man den Faktor gekürzt hat, den aber nicht vor dem ggT schreiben? Wieso kann man denn so kürzen?

Es tut mir sehr leid, dass der Anfang optisch grässlich aussieht, aber ich kam mit dem Editor einfach nicht klar. Der hat immer Absätze eingebaut -.-

Liebe Grüße
Kindi

P.S. Der Beweis ist aus dem Buch von Witt, Kurt-Ulrich: Algebraische und zahlentheoretische Grundlagen für die Informatik, S. 156 f.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
qwertzusername
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.06.2015
Mitteilungen: 1216
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-07-23


Hallo,

du suchst die Anzahl der q, die deine Gleichung lösen.
Wie kommt diese Unbekannte q in die Formel für die Anzahl der Lösungen?
Das macht keinen Sinn.

Die Rechnung die du danach machst ist durchaus sinnvoll.
Aus Gleichung 6 und der Bedingung fed-Code einblenden folgt, dass es höchstens (und damit sogar genau) p-1 mögliche Werte für k gibt, also auch für q.



  Profil  Quote  Link auf diesen Beitrag Link
kindi880
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.07.2018
Mitteilungen: 11
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-07-23


2018-07-23 11:49 - qwertzusername in Beitrag No. 1 schreibt:

du suchst die Anzahl der q, die deine Gleichung lösen.
Wie kommt diese Unbekannte q in die Formel für die Anzahl der Lösungen?
Das macht keinen Sinn.
Da mein g die Primitivwurzel ist, kann ich ja durch einen Beliebigen Exponenten, in diesem Fall q, jedes Element aus (Z/p^{e})^* erhalten. Ohne den Exponenten q wäre es ja nicht möglich.




Die Rechnung die du danach machst ist durchaus sinnvoll.
Aus Gleichung 6 und der Bedingung fed-Code einblenden folgt, dass es höchstens (und damit sogar genau) p-1 mögliche Werte für k gibt, also auch für q.

Zu dem letzten: Genau das verstehe ich nicht. In dem Punkt hätte ich noch eine kleine Erleuchtung :)



  Profil  Quote  Link auf diesen Beitrag Link
qwertzusername
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.06.2015
Mitteilungen: 1216
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-07-23

\(\begingroup\)
Zum Ersten:
Ich versteh deine Erwiederung nicht.
Das Problem ist, dass es keine Sinn macht, die Variable, nach der man lösen will, in der Lösung zu haben.
Die Anzahl der Lösungen würde sich je nachdem was man für q einsetzt ändern.
D.h. die Anzahl der möglichen Werte für q hinge von den Werten von q ab.
Da beißt sich die Katze in den Schwanz.


Zum zweiten:
Wie viele mögliche Belegungen für k gibt es , so dass
$1\leq k p^{e-1} \leq p^{e-1}(e-1)$ erfüllt wird (höchstens Fall), und dass dies alles unterschiedliche Elemente im Ring ergibt (genau)
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
kindi880
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.07.2018
Mitteilungen: 11
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-07-23

\(\begingroup\)
Ok also du meinst, dass es keinen Sinn macht, dass die Variable q in der Gleichung
\[t=ggT(q\cdot (p^{e}-1),(p-1)\cdot p^{e-1}\] auftaucht?

Nun ja, ich habe auch bei dem ganzen Beweis so meine offene Fragen, so wie ich es oben geschrieben habe, habe ich es aus dem Buch.
Also ich meine der Knackpunkt liegt ja auch irgendwie in dem Satz, den ich oben beim ersten Eintrag zitiert habe.  Müsste man dann eigentlich, folgende Gleichung betrachten?
\[t=ggT(p^{e}-1),(p-1)\cdot p^{e-1})\].

In dem Fall wäre ja dann, \(g^q\) mein  x und der Exponenten k wäre dann \(p^{e}-1)\) betrachten, wenn man das jetzt eins zu eins mit dem Satz übersetzen würde...

In dem Fall würede ja nach obiger Argumentation folgen, dass t=p-1 ist.
LG
Kindi
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
qwertzusername
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.06.2015
Mitteilungen: 1216
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-07-23


Die Argumentation so wie du sie im Eröffnungspost schreibst ist mindestens lückenhaft und umständlich, wenn nicht gar komplett falsch.
Die Gleichung, die du im letzten Post geschrieben hast ist richtig.
Wenn man mit der arbeiten will, kann man das machen (imho brauchst die nicht). Dann folgt t=p-1 aus den Relationen (es sind keine Gleichungen) 1,2 und 4.



  Profil  Quote  Link auf diesen Beitrag Link
kindi880
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.07.2018
Mitteilungen: 11
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-07-23


Danke sehr für die hilfreiche Antwort. Ich bin auch der Meinung, dass die Argumentation im Buch lückenhaft ist.
Wieso bist du denn der Meinung, dass ich sie nicht brauche? Verstehe ich nicht, gibt es eine andere Möglichkeit dies zu zeigen?
Lg
Kindi



  Profil  Quote  Link auf diesen Beitrag Link
qwertzusername
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.06.2015
Mitteilungen: 1216
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-07-23


Ja, so wie ich es hier gemacht hab.



  Profil  Quote  Link auf diesen Beitrag Link
kindi880
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.07.2018
Mitteilungen: 11
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-07-24


Alles klar, vielen Dank nochmals :-)

LG
Kindi880



  Profil  Quote  Link auf diesen Beitrag Link
kindi880 hat die Antworten auf ihre/seine Frage gesehen.
kindi880 hatte hier bereits selbst das Ok-Häkchen gesetzt.
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-2018 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]