Matroids Matheplanet Forum Index
Forumbereich moderiert von: Wauzi
Teilbarkeit » Kongruenzen » Primitivwurzeln mod 2 * 23^k
Druckversion
Druckversion
Antworten
Antworten
Universität/Hochschule Primitivwurzeln mod 2 * 23^k
NffN1 Aktiv Letzter Besuch: im letzten Quartal
Mitglied seit: 28.04.2020, Mitteilungen: 50
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-09-19

Guten Tag,

die Primitivwurzeln mod 23 sind folgende:

5,7,10,11,14,15,17,19,20, 21


Wie bestimmt man nun eine, die auch Primitivwurzel mod $2\cdot 23^k$ für alle k in N ist?

MfG,

Noah



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2414
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-09-19
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

zuerst solltest du eine Primitivwurzel modulo $23^2$ finden. Dazu musst unter den schon berechneten Primitivwurzeln $g$ modulo $23$ eine finden, für die $g^{22}\not\equiv 1\pmod{23^2} $ oder $(g+23)^{22}\not\equiv 1 \pmod{23^2}$ gilt. Siehe hier.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
NffN1 Aktiv Letzter Besuch: im letzten Quartal
Mitglied seit: 28.04.2020, Mitteilungen: 50
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-20

Guten Tag,

ich hab gefunden, dass wenn g=5, dann $g^{22} \neq 1mod23^2$.
Somit ist 5 also eine Primitivwurzel mod $23^2$. Und da 5 ungerade ist, ist 5 also auch eine Primitivwurzel mod $2\cdot 23^2$. Aber was ich noch nicht ganz verstanden habe ist, wie man es machen soll für auf $2\cdot23^k$ zu kommen.

MfG,
Noah



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2414
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, eingetragen 2020-09-20
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Wenn $g$ eine Primitivwurzel modulo einer ungeraden Primzahl $p$ ist, für die $g^{p-1}\not\equiv 1 \pmod{p^2}$ gilt, dann ist $g$ auch Primitivwurzel modulo $p^k$ für alle $k\geq 1$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 02.08.2003, Mitteilungen: 46235, aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-09-20
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
2020-09-20 18:49 - Nuramon in Beitrag No. 3 schreibt:
Wenn $g$ eine Primitivwurzel modulo einer ungeraden Primzahl $p$ ist, für die $g^{p-1}\not\equiv 1 \pmod{p^2}$ gilt, dann ist $g$ auch Primitivwurzel modulo $p^k$ für alle $k\geq 1$.
Hi Nuramon,
und wie beweist man das?
Gilt das auch modulo 2pk?
Gruß Buri
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 23.01.2008, Mitteilungen: 2414
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, eingetragen 2020-09-20
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Ich skizziere den Beweis aus dem Buch "Zahlentheorie" von Leutbecher:

Sei $p$ eine ungerade Primzahl und $g$ Primitivwurzel mod $p$ mit der Eigenschaft $g^{p-1}\not\equiv 1 \pmod{p^2}$ (*).
(So ein $g$ existiert: Ist nämlich $g$ eine Primitivwurzel mit $g^{p-1}\equiv 1\pmod{p^2}$, dann ist $g':= g+p$ eine Primitivwurzel mit der gewünschten Eigenschaft.)

Wir wollen zeigen, dass dann $g$ ein Erzeuger von $(\IZ/p^k)^\times$ ist, mit $k\geq 1$ beliebig.
Dazu genügt es zu zeigen, dass $h:=g^{p-1}$ in $(\IZ/p^k)^\times$ die Ordnung $p^{k-1}$ hat. (**)

Wegen (*) hat $h$ die Form $h=1+pt$ mit $t\not\equiv 0 \pmod p$.
Per Induktion lässt sich jetzt zeigen, dass
$$h^{p^m} \equiv 1 + p^{m+1}t \pmod {p^{m+2}}$$ für alle $m\geq 0$ gilt, woraus (**) folgt.


(2020-09-20 20:06 - Buri in Beitrag No. 4
Gilt das auch modulo 2pk?
Wenn $g$ ungerade ist, ja.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
NffN1 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-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]