Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Primitivwurzeln mod 2 * 23^k
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Primitivwurzeln mod 2 * 23^k
NffN1
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.04.2020
Mitteilungen: 50
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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
Dabei seit: 28.04.2020
Mitteilungen: 50
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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
Dabei seit: 02.08.2003
Mitteilungen: 46222
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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
Dabei seit: 23.01.2008
Mitteilungen: 2373
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem 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]