Die Mathe-Redaktion - 22.11.2017 02:46 - Registrieren/Login
Auswahl
Schwarzes Brett
Wartet darauf, dass Fragensteller die Antwort(en) liest2017-11-22 00:56 bb <
Matheformeln mit MathML
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 293 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 Buri Gockel
Strukturen und Algebra » Gruppen » Die Mächtigkeiten von Potenz-Untergruppen
Druckversion
Druckversion
Antworten
Antworten
Autor
Beruf Die Mächtigkeiten von Potenz-Untergruppen
ruach
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2006
Mitteilungen: 72
Aus: Bamberg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-11-11 12:55


Hallo Allerseits,
Kann man ganz allgemein zu einer primen Restklassengruppe modulo m die Mächtigkeit der Potenzuntergruppen bestimmen?
<math>G : \{a|ggT(m;a)=1;a,m \in \N\} </math> oder <math> G = (\mathbb{Z}/m\mathbb{Z})^* </math>

<math>U^k : \{u|u \equiv a^k;a \in G;a,k \in \N\} </math>
<math>|G| = \phi(m) </math>
Da <math>U^k</math> eine Untergruppe von G ist, weiß man nur,
dass die Mächtigkeit von <math>U^k</math> ein Teiler von <math>\phi(m)</math> ist.
<math>|U^k| = \phi(m) / x </math>

Mein Ansatz, um dieses unbekannte x zu bestimmen, ist eine Faktorgruppe <math>(G/U_b)</math> zu bilden und die Reduktion an Nebenklassen
oder innerhalb einer Nebenklasse abhängig von der Potenz k zu bestimmen.
(Die Reduktion des Index <math>(G : U_b)</math> und stellvertretend der Mächtigkeiten von <math>U_b</math> )

Sei b ein primes Element von G und <math><b></math> die daraus erzeugte Untergruppe <math>U_b</math> mit
<math>|<b>| = \lambda(m)</math>
<math>\lambda(m)</math> ist der Gruppenexponent und kann durch die Carmichelfunktion berechnet werden. (de.wikipedia.org/wiki/Carmichael-Funktion)
<math>\lambda(m)</math> besitzt dieselben Faktoren wie <math>\phi(m)</math>, nur in geringerer Anzahl,
da die Berechnung das kgV der Faktoren von <math>\phi(m)</math> beinhaltet.
<math>ggT(\phi(m);\lambda(m)) = \lambda(m)</math>

Wie wird nun durch die Potenz k die Untergruppe <math><b></math> und damit auch alle Nebenklassen reduziert?
Enthält k Teiler von <math>\lambda(m)</math>, dann ist die Mächtigkeit von <math><b^k></math>
<math>|<b^k>| = \lambda(m)/ggT(k;\lambda(m))</math>

Daraus ergibt sich der Reduktionsfaktor innerhalb der Nebenklassen
<math>x = r_i * y = ggT(k;\lambda(m)) * y </math>
und als Mächtigkeit der Potenzuntergruppen

<math>|U^k| = \phi(m) / (ggT(k;\lambda(m)) *y) </math>

y bezeichnet hier die Reduktion der Anzahl der Nebenklassen.
Diese ist etwas schwerer zu bestimmen!
Zuerst muss die Anzahl an Nebenklassen an sich geklärt werden.
Diese ist einfach der Index <math>(G : U_b)</math>

<math>(G : U_b) = |G|/|U_b| = \phi(m) / \lambda(m) = I_b </math>

Gesucht ist jetzt der Index <math>I_b^k </math>:
<math>I_b^k =  \phi(m) / (\lambda(m) *y) </math>

Wieder gilt, ist eine Potenz k teilerfremd zu <math>I_b</math> und damit auch zu <math>\phi(m)</math> und <math>\lambda(m)</math>,
dann reduziert sich der Index <math>I_b^k</math> nicht.

Bis wohin muss und kann sich dieser Index <math>I_b^k</math> reduzieren und in welchen Schritten?
Es gilt:
<math>I_b^{\phi(m)} \equiv I_b^{\lambda(m)} \equiv 1 </math>
Da aber die aus k zum Index <math>I_b</math> teilerfremden Faktoren von <math>\lambda(m)</math> keine Reduktion bewirken,
wird der Wert 1 bereits früher als mit <math>\lambda(m)</math> erreicht.
Entscheidend ist hier der GGT zwischen Index und Gruppenexponent!
<math>I_b^{ggT(\phi(m)/\lambda(m);\lambda(m))} \equiv 1 </math>

Mit dem Erreichen dieses ggTs muss <math>I_b</math> bis zur 1 reduziert sein.
Ein besonderer Schritt ist hier der Faktor 2.
Hier wird die Mächtigkeit von <math>G^{2k'}</math> um <math>2^i</math> und damit der Index um <math>2^{i-1}</math> reduziert (vgl. Jacobi-Symbol).
Man kann daher mit folgendem Vorgehen aus der Potenz k die Reduktion ermitteln:
1. Ersetze alle zu <math>I_b</math> teilerfremden Faktoren von k durch die 1.
2. Reduziere die Potenzen der Faktoren von k auf die entsprechenden Potenzen von <math>GGT(\phi(m)/\lambda(m);\lambda(m))</math>
3. Ist k gerade, ersetze einen Faktor 2 durch <math>2^{i-1}</math>, wobei i die Anzahl der ungeraden Primfaktoren von m ist.

Ich bin mir jetzt noch nicht sicher, ob das so ausreicht und in allen Fällen zutrifft.
Es ist auch relativ kompliziert, die Zusammenhänge hier an Beispielen zu prüfen.
Aber vielleicht hat jemand hier eine Idee oder sieht einen Fehler oder ein Problem.

Ich werde auf jeden Fall länger brauchen, um hier weiter zu kommen.

Viele Grüße
ruach

PS Eine Problem kenne ich bereits:
Es scheint die 1 beim Index gelegentlich vor dem GGT erreicht zu werden.
Dann müßte ein weitere Faktor 2 durch eine 1 ersetzt werden???!

PPS Jetzt muss ich auch diese Formel verbessern:
Zitat: "Seien a und b teilerfremd zu m und alle drei natürliche Zahlen
und sei b ein primitives Element in der primen Restklassengruppe  <math>(\mathbb{Z}/m\mathbb{Z})^* </math>,
dann ist folgende Potenz von a in dieser primen Restklassengruppe
ein Element der durch die Potenzen von b gebildeten Untergruppe.

<math>a^{GGT( \phi(m) / \lambda(m);\lambda(m))} \equiv b^z \mod m  </math>

<math> \phi(m) </math> bezeichnet dabei die PHI-Funktion.
<math> \lambda(m) </math> bezeichnet die Carmichael-Funktion.
<math>a,b,m,z \in \mathbb N </math>
<math>GGT(a*b;m) = 1 </math> "

Die Untergruppe von G zur Potenz <math>z = GGT( \phi(m) / \lambda(m);\lambda(m)) </math>
ist eine gemeinsame Untergruppe aller primen Elemente.
Das drückt diese Formel noch nicht aus.
<math> a^z \equiv b_i^{l*z} \equiv b_j^{m*z} </math>

Und weiter gilt dies für alle "PotenzEbenen" (siehe "teilerfremd in 3D")
oder Potenzuntergruppen: Teilmengen dieser Potenzuntergruppen haben gemeinsame, "verbindende" Untergruppen aus Potenzreihen einzelner Elemente.
(Wie genau, verstehe ich noch nicht ...)

PPPS: Man könnte m noch einschränken auf quadratfrei oder ungerade.



  Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 3049
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-11-15 01:01


Ich habe mir lediglich die Problemstellung durchgelesen. Die prime Restklassengruppe hat eine bekannte Produkt-Zerlegung in zyklische Gruppen; siehe z.B. en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
 
Es reicht daher, die Potenz-Untergruppe für zyklische Gruppen zu bestimmen. Das ist aber relativ einfach: Ist <math>G=\langle g \rangle</math> eine endliche zyklische Gruppe der Ordnung <math>d</math>, so ist die Potenz-Untergruppe <math>\langle g^k \rangle</math>, und <math>g^k</math> hat als Ordnung <math>d/\mathrm{ggT}(d,k)</math>.



  Profil  Quote  Link auf diesen Beitrag Link
ruach
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2006
Mitteilungen: 72
Aus: Bamberg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-11-16 07:21


Hallo Triceratops,
vielen Dank für Deinen für mich neuen und sehr eleganten Ansatz.
Solche Formeln und Zusammenhänge suche ich!
Es wird m in seine Primfaktorpotenzen zerlegt, und dann das Produkt der Mächtigkeiten
der von diesen Faktoren gebildeten zyklischen Gruppen gebildet.
Für ein quadratfreies m würde das dann so aussehen - wenn ich das so richtig verstehe:

<math>m = m_1 * m_2 * ... * m_i </math>

<math>|U^k| = (\phi(m_1) / ggT(\phi(m_1), k)) * (\phi(m_2) / ggT(\phi(m_2), k)) * ... * (\phi(m_i) / ggT(\phi(m_i), k))</math>

<math>|U^k| = [(m_1-1) / ggT((m_1-1), k)] * [(m_2-1) / ggT((m_2-1), k)] * ... * [(m_i-1) / ggT((m_i-1), k)]</math>

Das einzige, hier wird nicht in Nebenklassenspalten und Elementreihen unterschieden
und damit kann ich diese Formel nicht räumlich anschaulich machen.
Aber sie könnte mir helfen, die Reduktion der Nebenklassenspalten auf die 1 besser zu erfassen.
Viele Grüße
ruach


PS: Das mit der Anzahl der Nebenklassen ist ja ganz einfach auch mit dieser Formel zu bestimmen! Die Anzahl der Elemente je Klasse ist ja bekannt. Dann hilft mir diese Formel enorm!



  Profil  Quote  Link auf diesen Beitrag Link
ruach
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2006
Mitteilungen: 72
Aus: Bamberg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2017-11-21 21:27


Hallo Allerseits,
ich will versuchen, das bisherige zusammenzufassen und weiterzutreiben.
Eine natürliche Zahl m läßt sich in n Primzahlpotenzen zerlegen:

<math>m = m_1 * m_2 * ... * m_n </math> mit
<math>m_i =p_i^{a_i} </math>

Die Gruppe G der zu m teilerfremden Restklassen hat die Mächtigkeit <math>\phi(m)</math>.
G läßt sich in eine Untergruppe <math>U_e</math> und die zugehörigen Nebenklassen unterteilen.
Ist die Mächtigkeit von <math>U_e=\lambda(m)</math> und damit in G maximal (Gruppenexponent), so gibt es folgende Anzahl an Nebenklassen:

<math>N_e = \phi(m) / \lambda(m)</math> oder <math>\phi(m) = N_e *  \lambda(m)</math>

Ich suche nach der Mächtigkeit der Untergruppe <math>U^k</math> mit konstantem k,
die die k-ten Potenzen aller Elemente von G umfasst.
Nach dem Hinweis von Triceratops müsste diese Mächtigkeit so aussehen:

<math>|U^k| = (\phi(m) / ggT(\phi(m_1), k) * (\phi(m_2) / ggT(\phi(m_2), k) * ... * (\phi(m_n) / ggT(\phi(m_i), k) = \phi(m) / [ \prod_{i=1}^n ggT(\phi(m_i), k) ]</math>

teilt man dies wieder in Reihen und Zeilen auf und nimmt als Zeilenanzahl:

<math>|U_e^k| = \lambda(m)/ggT(k;\lambda(m))</math>

Dann ergibt sich:

<math>|U^k| = [\lambda(m)/ggT(k;\lambda(m))] * [\phi(m) / \lambda(m)] * [ggT(k;\lambda(m)) / [\prod_{i=1}^n ggT(\phi(m_i), k)]]</math>

<math>[\lambda(m)/ggT(k;\lambda(m))]</math> beschreibt dabei die Entwicklung der Zeilenanzahl,
die mit <math>k=\lambda(m)</math> auf die 1 reduziert wird.

<math>[\phi(m) / \lambda(m)] * [ggT(k;\lambda(m)) / [\prod_{i=1}^n ggT(\phi(m_i), k)]]</math> beschreibt die Entwicklung der Anzahl an Nebenklassen.
<math>[ggT(k;\lambda(m)) / [\prod_{i=1}^n ggT(\phi(m_i), k)]]</math> ist der die Anzahl der Nebenklassen reduzierende Faktor.

Die Anzahl 1 wird an folgendem Punkt z erreicht:

<math>z= GGT( \phi(m) / \lambda(m);\lambda(m))</math>

Also:

<math>[\phi(m) / \lambda(m)] * [ggT(z;\lambda(m)) / [\prod_{i=1}^n ggT(\phi(m_i), z)]] = 1</math>

Den letzten Schritt etwas genauer:
Es gilt: <math>ggT(z;\lambda(m)) = z </math> und ich vermute, es gilt auch:

<math>\lambda(m) = z * t </math> mit <math>ggT(z;t) = 1 </math>

<math>\lambda(m)</math> enthält alle Primfaktoren von <math>\phi(m)</math> aufgeteilt in die von z und die von t.
Dann müßte auch gelten:

<math>[\prod_{i=1}^n ggT(\phi(m_i), z)] = \phi(m) / t</math>

(Es werden alle Faktoren aus <math>phi(m)</math> gesammelt, die teilerfremd zu t sind.)
Alles zusammen:

<math>[\phi(m) / \lambda(m)] * [ggT(z;\lambda(m)) / [\prod_{i=1}^n ggT(\phi(m_i), z)]] =  [\phi(m) / z*t] * [z / (\phi(m) / t)] = 1</math>

Das ist jetzt nur eine Beweisskizze, aber der Weg ist anders als der oben beschriebene.
Ich vermute, dass man nicht verstehen kann, was ich hier will, aber ich habe so ein Bild im Kopf:
Da ist die Grundebene mit allen Elementen und dann leuchten mit steigendem k immer nur diejenige Elemente der Grundebene,
die auf der jeweiligen Potenzebene vorkommen. Am Punkt z ist dies immer nur noch eine Spalte und dort jedes t-te Element,
egal, nach welchem primen Element die Grundebene strukturiert ist.

Viele Grüße
ruach



  Profil  Quote  Link auf diesen Beitrag Link
ruach hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 

 AQA

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]