Beweis über die Menge der Einheiten

05.12.2006, 21:46

timadler

Beweis über die Menge der Einheiten

Hey zusammen,

ich hätte da noch einen.

Sei $\begin{eqnarray*} m \in \mathbb, m \geq 2 \end{eqnarray*}$ . Zeigen Sie, dass für ein $\begin{eqnarray*} x \in \mathbb Z^{+}_{m} \end{eqnarray*}$ genau dann
$\begin{eqnarray*} \{x^k:k\in \mathbb N_{0}\}= \mathbb Z^{+}_{m} \end{eqnarray*}$
gilt wenn $\begin{eqnarray*} x^{\frac{\varphi(m)}{p}} \neq [1]_{m} \end{eqnarray*}$ für alle Primzahlen p gilt, die Teiler von $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ sind.

Ich habe hier bereits Schwierigkeiten über zu verstehen, was gefragt ist (schön verklausulierte Mathe-Welt): Ich hätte ursprünglich vermutet, dass man die Form einer Einheitenmenge nachweisen soll. Allerdings verstehe ich da nicht, wie das x da hereinspielt.

Erklärt sich einer bereit mir das mal in Ruhe zu erklären und vielleicht nen Ansatz zu geben?

Danke und Gruß, Tim

06.12.2006, 11:59

Abakus

Auf diesen Beitrag antworten »

RE: Beweis über die Menge der Einheiten
Schau zunächst einmal hier: Eulersche Phi-Funktion.

Die multiplikative (Einheiten-) Gruppe $\begin{eqnarray*} \mathbb Z^{+}_{m} \end{eqnarray*}$ hat $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ viele Elemente. Ferner weißt du, dass die Ordnung einer Untergruppe die Gruppenordnung teilt.

Damit solltest du etwas anfangen können.

Grüße Abakus smile

06.12.2006, 22:47

timadler

Auf diesen Beitrag antworten »

Mmh, habe ich mir alles angeguckt und auch noch ein bisschen im Buch gelesen.
Aber irgendwie schauts noch nicht so gut aus.

Es scheint ja darum zu gehen, nachzuweisen, dass die Menge der Inversen genau diese $\begin{eqnarray*} x^k \end{eqnarray*}$ sind, wenn die Nebenbedingung gilt, oder?

Bin aber im Moment noch etwas ahnungslos. Würdest Du weiter "tippen" smile

06.12.2006, 22:57

Auf diesen Beitrag antworten »

Ich nehme an, der Satz von Fermat-Euler ist dir bekannt. Was weißt du über primitive Wurzeln? Bzw. überhaupt erstmal über die Ordnung eines Elements $\begin{eqnarray*} x\in\mathbb{Z}_m^+ \end{eqnarray*}$ ?

06.12.2006, 23:24

timadler

Auf diesen Beitrag antworten »

Bis vor wenigen Augenblicken noch nichts.

Zahlen in einem Bereich $\begin{eqnarray*} 1 \leq a \leq n \end{eqnarray*}$ sind primitive Wurzeln, wenn ggT(a,n)=1 und $\begin{eqnarray*} a^d \neq_{n} 1 \end{eqnarray*}$ für $\begin{eqnarray*} 1 \leq d < \varphi(n) \end{eqnarray*}$
Ein n ist genau dann eine primitive Wurzeln, wenn $\begin{eqnarray*} n=\{1,2,4\} \end{eqnarray*}$ oder von der Form $\begin{eqnarray*} p^k \end{eqnarray*}$ oder $\begin{eqnarray*} 2p^k \end{eqnarray*}$ .

Das sieht mir alle schon recht gut aus. Mit dem ggT = 1 hätte man dann ja schon ein Inverses am Wickel, oder? Ginge man davon aus, und man weiss ja, dass $\begin{eqnarray*} \frac{\varphi(m)}{p} \end{eqnarray*}$ auf jeden kleiner ist als $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ dann würde die Bedingung doch zumindest für das x schonmal gelten, oder?

Ich spekuliere da ein wenig wild rum, weil ich da noch nicht wirklich den Durchblick hab.
Tipp mich, vielleicht komm ich mit Hilfe an smile

Satz von Euler/Fermat ist klar.
$\begin{eqnarray*} a^{\varphi(m)} \equiv_{m} 1 \end{eqnarray*}$

07.12.2006, 13:26

Abakus

Auf diesen Beitrag antworten »

Betrachte zum näheren Kennenlernen ein paar Beispiele. Ich schlage dir mal $\begin{eqnarray*} {Z}_{12}^+ \end{eqnarray*}$ und $\begin{eqnarray*} {Z}_{30}^+ \end{eqnarray*}$ vor.

Wie liegen die Verhältnisse bei diesen beiden Einheitengruppen ?

Grüße Abakus smile

07.12.2006, 13:52

andre.86

Auf diesen Beitrag antworten »

Ich sitze an dieser Aufgabe schon ewig.....
also, wenn ich mir die Beispiele anschaue, dann komme ich da auch nicht weiter....

Kannst du nicht bitte etwas konkreter sagen, wie man die Aufgabe am Besten angeht?

Danke

André

07.12.2006, 18:16

meow

Auf diesen Beitrag antworten »

mhm...

geht das irgendwie in die Richtung, dass $\begin{eqnarray*} x^{k} \end{eqnarray*}$ ... als Potenzgruppe $\begin{eqnarray*} <x>_m \end{eqnarray*}$
sich quasi wiederholt ..

und dass die wiederholung bei $\begin{eqnarray*} k=\Phi(m) \end{eqnarray*}$ beginnt ... wäre dann $\begin{eqnarray*} x^k=[1]_m \end{eqnarray*}$ für ein $\begin{eqnarray*} k<\Phi(m) \end{eqnarray*}$ schon gegeben .. würde die wiederholung an einer anderen stelle beginnen .. und nicht alle einheiten werden abgedeckt ..

weil wir ja effektiv um alle einheiten zu erhalten "nur" die $\begin{eqnarray*} k \end{eqnarray*}$ brauchen für die gilt $\begin{eqnarray*} 0 \leq k < \Phi(m) \end{eqnarray*}$ (oder etwa $\begin{eqnarray*} \leq \Phi(m) \end{eqnarray*}$ ? .. bin da unsicher)

.... irgendwie so ... ich vermute mal es ist totaler blödsinn der irgendwie in die richtige richtung geht ... ich steig da einfach noch nicht durch ... hab die dumpfe ahnung, dass uns da wieder irgendwelche grundlagen fehlen

07.12.2006, 19:39

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von andre.86
Ich sitze an dieser Aufgabe schon ewig.....
also, wenn ich mir die Beispiele anschaue, dann komme ich da auch nicht weiter....

Kannst du nicht bitte etwas konkreter sagen, wie man die Aufgabe am Besten angeht?

Es ist völlig normal, an bestimmten Aufgaben länger zu sitzen. Eine Hilfe ist immer, sich ein möglichst einfaches Beispiel genau anzuschauen.

Was ergibt sich bei den Beispielen ? Was ist $\begin{eqnarray*} \varphi(12), ~\varphi(30) \end{eqnarray*}$ ? Aus welchen Elementen besteht die Einheitengruppe jeweils ? Und welche dieser Elemente erzeugen jeweils die gesamte Einheiten-Gruppe ?

Grüße Abakus smile

07.12.2006, 20:19

meow

Auf diesen Beitrag antworten »

so, ich hab mir jetzt doch mal $\begin{eqnarray*} \Phi(12) \end{eqnarray*}$ angeschaut ...

ich weiß jetzt, dass $\begin{eqnarray*} Z_{12}^\times = \{1, 5, 7, 11\} \end{eqnarray*}$ ist

... dass ich wenn ich bei $\begin{eqnarray*} x^k \end{eqnarray*}$ das $\begin{eqnarray*} x \end{eqnarray*}$ aus der Menge wähle auch nichts spannendes lerne ..

und ich bin einigermaßen sicher, dass es kein $\begin{eqnarray*} x \in Z_{12}^\times \end{eqnarray*}$ gibt, für das gilt $\begin{eqnarray*} \{ x^k : k\in N_0 \} = Z_{12}^\times \end{eqnarray*}$

... also irgendwie verzweifel ich allein schon an der aufgabenstellung!
wenn da ein $\begin{eqnarray*} \in \end{eqnarray*}$ statt dem = wäre ........ aber ich versteh es einfach nicht!

07.12.2006, 20:20

suye

Auf diesen Beitrag antworten »

Kann es sein, dass es mit $\begin{eqnarray*} \varphi(12) \end{eqnarray*}$ nicht möglich ist?
Betrachten wir die Einheitengruppe: Zxm = { [1], [5], [7], [11] }.
D.h. $\begin{eqnarray*} \varphi(12) \end{eqnarray*}$ = 5.
5 ist die einzige Primzahl, die 5 teilt.
Also:

1^1 kongruent 1 mod. 12
5^1 kongruent 5 mod. 12
7^1 kongruent 7 mod. 12
11^1 kongruent 11 mod. 12

=> 5, 7 oder 11 müsste das gesuchte Element sein.

11^0 = 1
11^1=11
11^2 = 1
11^3=11
...

Selbes Spiel für 5 (1,5,1,5, ..) und 7 (1,7,1,7, ..).

verwirrt

07.12.2006, 20:22

suye

Auf diesen Beitrag antworten »

Käse, Phi(12) = 4 .. klappt aber trotzdem nicht, was auch klar ist :-)

07.12.2006, 20:25

Auf diesen Beitrag antworten »

Zitat:

Original von suye
=> 5, 7 oder 11 müsste das gesuchte Element sein.

Welches gesuchte Element? So ein $\begin{eqnarray*} x \end{eqnarray*}$ wie in der nachzuweisenden Äquivalenz? Nein, das erfüllen alle vier nicht.

07.12.2006, 20:33

meow

Auf diesen Beitrag antworten »

haben wir damit die angabe widerlegt und können das als lösung betrachten?
(schön wärs!)

07.12.2006, 20:46

timadler

Auf diesen Beitrag antworten »

Wenn das so wäre, wäre der Zettel nen frühes Weihnachtsgeschenk Augenzwinkern

!

Ne, aber mal konkret: Könnte vielleicht ein jemand der Mathe-Bewanderten aus dem Forum vielleicht mal in menschähnlichen Worten zusammenfassen, was wirklich Aufgabe ist hier. Ich hatte ja bereits Eingangs erwähnt, dass das bereits ein Problem ist und auch meow ließ ja sowas andeuten.

Wäre cool!

07.12.2006, 20:58

Auf diesen Beitrag antworten »

Zitat:

Original von timadler
Könnte vielleicht ein jemand der Mathe-Bewanderten aus dem Forum vielleicht mal in menschähnlichen Worten zusammenfassen,

Alles was du nicht zu verstehst, ist nicht menschenähnlich - auch eine Auffassung. Augenzwinkern

Ok, noch eine Hilfestellung: Die Aufgabe kann man in den Nachweis zweier Äquivalenzen splitten: Sei $\begin{eqnarray*} x\in\mathbb Z_m^+ \end{eqnarray*}$ . Dann gelten

$\begin{eqnarray*} (1)\qquad \{x^k:\; k\in \mathbb{N}_0 \} = \mathbb Z_m^+ \quad\Longleftrightarrow\quad \operatorname{ord}(x) = \varphi(m) \end{eqnarray*}$

$\begin{eqnarray*} (2)\qquad \operatorname{ord}(x) = \varphi(m) \quad\Longleftrightarrow\quad x^{\frac{\varphi(m)}{p}} \not\equiv 1 \mod m \end{eqnarray*}$ für alle Primzahlen $\begin{eqnarray*} p|\varphi(m) \end{eqnarray*}$

So, und jetzt denk darüber mal länger nach, wie von Abakus empfohlen. Das nötige Rüstzeug ist alles vorhanden.

07.12.2006, 21:15

suye

Auf diesen Beitrag antworten »

Folgenden Tipp (wenn man es so nennen kann) haben wir von unserem Tutor bekommen:

Beh.: { x^k : k € IN} = Zm^x <=> Für alle Primzahlen p mit p | Phi(m) gilt: x^(Phi(m)/p) nicht kongruent 1 mod. m.

Okay, soweit so gut.
Da <=>, gilt es beide Richtungen zu zeigen:

"=>"
Ann: Es ex. p prim mit x^(Phi(m)/p) kongruent 1 mod. m.
=> => => { x^k : k € IN} ist echte Teilmenge von Zm^x, also Winderspruch

"<="
Ann: { x^k : k € IN} ist echte Teilmenge von Zm^x und x^(Phi(m)/p) nicht kongruent 1 mod. m für alle p prim mit p | Phi(m)
=> => => Widerspruch
Tipp: Evt. teilen mit Rest!

Viel bringen tut mir das im Moment nicht viel .. aber ich bin dran :-)

07.12.2006, 21:48

meow

Auf diesen Beitrag antworten »

eine frage ... wenn mir das jemand sagen könnte schaff ich den rest ...... vielleicht

wie ist x für m=12 zu wählen?

da scheiterts bei mir ja schon, dass ich nicht verstehe wie m zu wählen ist

denn es ist doch für jedes m nur EIN x zu wählen .. oder?
und das funktioniert für alle m .. oder?

07.12.2006, 21:52

Auf diesen Beitrag antworten »

Zitat:

Original von meow
wie ist x für m=12 zu wählen?

Für m=12 gibt es kein solches x. Aber dann eben auf beiden Seiten der Äquivalenz nicht!

07.12.2006, 22:05

suye

Auf diesen Beitrag antworten »

Ich erkläre es dir mal an einem Beispiel ..

Also mit Phi(12) funktioniert das nicht, da es kein p prim gibt mit p | Phi(12) und x^(Phi(12)/p) nicht kongruent 1 mod. 12 gibt.
Einheiten sind 1, 5, 7, 11
Primzahlen, die 12 teilen: 2,3

p = 2

Also muss x^4/2 = x^2 nicht kongruent 1 sein, wobei x irgendeine Einheit aus Z_12 sein kann.
1^2 kongruent 1
5^2 kongruent 1
7^2 kongruent 1
11^2 kongruent 1

Da es für alle Primzahlen gelten muss, braucht man es mit p = 3 nicht mehr durchspielen.
Es ist also mit 12 nicht möglich!

Wählen wir m = 6.

Einheiten sind 1 und 5.
Also Phi(6) = 2
Als Primzahl können wir nur 2 wählen, also muss x^2/2 = x^1 nicht kongruent 1 mod. 6 sein.

1^1 kongruent 1
5^1 kongruent 5
=> 5 ist Erzeuger der Einheitengruppe
Wir prüfen:
5^0 = 1
5^1 = 5
5^2=1
5^3=5
...

Mit m = 5 ist es auch machbar! Erzeuger dort sind 2 und 3.

Also muss bei beiden Beispielen gelten, dass Phi(m) = ord(x) ist (nach Hilfestellung von Arthur Dent) ist.
Wir prüfen:
5^2 kongruent 1 mod. 6
1^2 kongruent 1 mod. 6

Stimmt also.

Beispiel m = 5.
Erzeuger sind 2 und 3 und Phi(5) = 4.
Also muss ord(x) = 4 sein.
2^4 kongruent 1 mod. 5
3^4 kongruent 1 mod. 5

Stimmt also auch.

Ich habe richtig verstanden, dass Phi(m) = ord(x) für alle x € Z_m^x sein muss, korrekt?

Okay, jetzt muss ich nur noch den Zusammenhang verstehen und dann kann mich evt. auch mal an den Beweis trauen :-)

07.12.2006, 22:12

Auf diesen Beitrag antworten »

Zitat:

Original von suye
Ich habe richtig verstanden, dass Phi(m) = ord(x) für alle x € Z_m^x sein muss, korrekt?

Ähmm, meinst du

$\begin{eqnarray*} \varphi(m) = \operatorname{ord}(x) \end{eqnarray*}$ für alle $\begin{eqnarray*} x\in \mathbb{Z}_m^+ \end{eqnarray*}$ ?

Das stimmt nicht, betrachte nur mal $\begin{eqnarray*} 1\in \mathbb{Z}_m^+ \end{eqnarray*}$ , das hat immer die Ordnung 1.

07.12.2006, 22:15

suye

Auf diesen Beitrag antworten »

Oh, das meinte ich eigentlich nicht :-)
Ich meinte das gilt für alle Erzeuger der Einheitengruppe.
Also bei 6 für 5 und bei 5 für 3 und 2 ...

07.12.2006, 22:25

meow

Auf diesen Beitrag antworten »

ahhh... okay ... nun habe sogar ich meinen fehler bei m=12 verstanden geschockt

07.12.2006, 22:33

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von suye
Oh, das meinte ich eigentlich nicht :-)
Ich meinte das gilt für alle Erzeuger der Einheitengruppe.
Also bei 6 für 5 und bei 5 für 3 und 2 ...

Ja, das gilt für alle erzeugenden Elemente. $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ gibt ja die Anzahl der Elemente der Einheitengruppe an.

Grüße Abakus smile

07.12.2006, 23:10

timadler

Auf diesen Beitrag antworten »

Darf ich fragen, was "erzeugende Element" sind?

Um das Beispiel von oben aufzugreifen und nochmal untereinanderzuschreiben:

Die Einheiten in Z12 sind: 1 5 7 11
phi(12) ist also 4
Zueinander invers sind:
1 und 1
5 und 5
7 und 7
11 und 11

Die Einheiten in Z30 sind: 1 7 11 13 17 19 23 29
phi(30) ist also 8
Zueinander invers sind:
1 und 1
7 und 13
11 und 11
13 und 7
17 und 23
19 und 19
23 und 17
29 und 29

Dank IT!

07.12.2006, 23:18

suye

Auf diesen Beitrag antworten »

Mit erzeugenden Elementen/Einheiten sind eben die Einheiten gemeint, für die gilt: {x^k : k € IN } = Z_m^k
Mit anderen Worten die Einheiten der Restklassen, die durch potenzieren mit den natürlichen Zahlen alle anderen Einheiten erzeugen.

07.12.2006, 23:58

suye

Auf diesen Beitrag antworten »

Kriege es nicht bewiesen .. man oh man .. böse

08.12.2006, 00:13

Auf diesen Beitrag antworten »

Ich komm nochmal auf meinen Vorschlag von oben zurück:

Welche Äquivalenz ist dir denn noch unklar: (1), (2) oder gar beide?

08.12.2006, 00:20

suye

Auf diesen Beitrag antworten »

Also (2) leuchtet mir eigentlich ein ..
Wenn Phi(m) = ord(x), dann ist x^(Phi(m)/p) immer kleiner als ord(x).
Laut Def. von ord(x) kann nun x^(Phi(m)/p) nicht kongruent 1 sein, da ord(x) das kleinste Element ist, für das x^ord(x) = 1.
Die andere Richtung bereitet mir aber noch Kopf zerbrechen ..

Und mit (1) kann ich auch nichts anfangen .. ich begreife den Zusammenhang einfach nicht!
Denke ich bin ziemlich nah dran, aber mir fehlt halt der entscheidende Einfall :-/

08.12.2006, 00:26

Auf diesen Beitrag antworten »

(1) ist doch der einfachere Teil: Die Ordnung $\begin{eqnarray*} \operatorname{ord}(x) \end{eqnarray*}$ ist die kleinste positive ganze Zahl $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} x^k\equiv 1\mod m \end{eqnarray*}$ . Jetzt betrachte mal die Sequenz

$\begin{eqnarray*} x^0, x^1, x^2, \ldots, x^{k-1}, x^k, x^{k+1}, \ldots \end{eqnarray*}$

Ab $\begin{eqnarray*} x^k \end{eqnarray*}$ wiederholt sich die Sequenz, also $\begin{eqnarray*} x^k=x^0=1 \end{eqnarray*}$ , $\begin{eqnarray*} x^{k+1}=x^1 \end{eqnarray*}$ , ...

Also hat die Menge $\begin{eqnarray*} \{ x^n \bigm| n\in\mathbb{N} \} \end{eqnarray*}$ genau $\begin{eqnarray*} k \end{eqnarray*}$ Elemente. Und wieviel Elemente hat gleich nochmal $\begin{eqnarray*} \mathbb{Z}_m^+ \end{eqnarray*}$ ???

So schwer ist das doch wirklich nicht.

08.12.2006, 00:37

suye

Auf diesen Beitrag antworten »

Tja, für dich mag es leicht sein .. für mich leider nicht :-/
Das einzige, was ich nicht verstehe ist, warum alle Einheiten erzeugt werden können?
Wenn ord(x) = Phi(m), dann kann ich nachvollziehen, dass 1 auf jeden Fall erzeugt wird (x^0). k wird auch auf jeden Fall erzeugt (k^1). Was beudetet, dass k = ord(x) = Einheit mod. m, korrekt?
Das sich das wiederholt ist auch klar - allerdings, wie gesagt, noch nicht, warum ALLE Einheiten erzeugt werden. traurig

08.12.2006, 00:44

Auf diesen Beitrag antworten »

Eigentlich wird das oben gar nicht gebraucht, dass es genau $\begin{eqnarray*} k \end{eqnarray*}$ Elemente sind, zum Beweis reicht die Erkenntnis, dass es höchstens $\begin{eqnarray*} k \end{eqnarray*}$ sind. Aber es stimmt, es sind genau $\begin{eqnarray*} k \end{eqnarray*}$ .

------------------------

Zum Beweis:

Betrachte $\begin{eqnarray*} \{ x^0,x^1,\ldots,x^{k-1}\} \end{eqnarray*}$ mit $\begin{eqnarray*} k=\varphi(m) \end{eqnarray*}$ .

Jetzt nimm mal an, dass diese Menge weniger als $\begin{eqnarray*} k \end{eqnarray*}$ Elemente enthält - das ist es ja, was du eventuell noch für möglich hältst. Dann muss es nach Schubfachprinzip aber zwei Indizes $\begin{eqnarray*} 0\leq i<j\leq k-1 \end{eqnarray*}$ geben mit $\begin{eqnarray*} x^i\equiv x^j\mod m \end{eqnarray*}$ . Umgestellt ergibt das

$\begin{eqnarray*} x^i(x^{j-i}-1) \equiv 0\mod m \end{eqnarray*}$ ,

wegen der Teilerfremdheit von $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ (nichts anderes bedeutet ja $\begin{eqnarray*} x\in\mathbb{Z}_m^+ \end{eqnarray*}$ ) folgt daraus

$\begin{eqnarray*} x^{j-i}-1 \equiv 0\mod m \end{eqnarray*}$ .

Das ist aber ein Widerspruch zu $\begin{eqnarray*} \operatorname{ord}(x)=k \end{eqnarray*}$ , denn es ist $\begin{eqnarray*} 1\leq j-i\leq k-1 \end{eqnarray*}$ , also ist $\begin{eqnarray*} k \end{eqnarray*}$ nicht der kleinste Index mit $\begin{eqnarray*} x^k\equiv 1\mod m \end{eqnarray*}$ .

Zitat:

Original von suye
Tja, für dich mag es leicht sein .. für mich leider nicht :-/

Tja, ich erwarte, dass Studenten auch selbständig mal ein paar Schritte gehen. Bin halt etwas altmodisch.

08.12.2006, 00:57

suye

Auf diesen Beitrag antworten »

Ich erwarte ja nicht, dass du es mir vorkaust. Ich erwarte eigentlich garnichts und finde es ausgesprochen nett, dass du dir die Zeit nimmst, mir/uns zu helfen.
Aber Fakt ist doch, wenn man gerade in den Anfängen des Studiums ist (ich studiere Informatik, kein Mathematik), dass es einfach nicht frei von der Hand geht.
Und wenn ich was nicht verstehe, dann frage ich nach. Bin ich in der Uni, frage ich meinen Tutor/Professor oder Mitstudenten.
Nun bin ich aber zu Hause, also frage ich hier im Forum und suche nach Erklärungen .. ich bin kein Student, der irgendwas einfach abschreibt und abgibt. Ich will es verstehen!

Diese Aufgabe ist ganz einfach schwer, zumindest für unseren derzeitigen Wissensstand. Kein einziger meiner Mitstudenten konnte diese Aufgabe meines Wissens lösen.

So, zurück zu der Aufgabe:

Mh, das klingt gut - aber das meinte ich eigentlich nicht.
Es geht mir viel mehr darum zu verstehen, warum ich mit einer Einheit x potenziert mit den natürlichen Zahlen ALLE Einheiten bekomme.
Bspw. bei m = 5, Phi(5) = 4, x = 2
2^0 = 0
2^1 = 2
2^3 = 3
2^4 = 1

Nun gut, sind also k Einheiten, also bekomme ich k-verschiedene Restklassen wenn ich x^k rechne - das ist der Punkt den ich noch nicht verstehe.

08.12.2006, 02:20

meow

Auf diesen Beitrag antworten »

nebenbei bemerkt mal:
Danke an diejenigen die hier die Lösung vorangebracht haben ( besonders Arthur und Abakus, wenn ich mich recht entsinne, die daraus keinen eigenen nutzen ziehen und trotzdem helfen )

es war meines wissens wirklich kaum einem von uns (wir meint hier die Hörer von Mathe für Informatiker 1 an der Uni Paderborn - zu einem großen Teil Erstsemester) möglich die Aufgabe selbstständig zu lösen, ich weiß nur von einem Fall, in dem zwei besonders engagierte denen das viel mehr liegt als dem durchschnitt in einer Aktion von mehr als 10 Stunden wohl einen Lösungsweg gefunden haben.....

das spricht leider wirklich nicht gerade für unseren Professor, bzw. die Aufgaben die er uns stellt!

08.12.2006, 07:51

Auf diesen Beitrag antworten »

Zitat:

Original von suye
Mh, das klingt gut - aber das meinte ich eigentlich nicht.
Es geht mir viel mehr darum zu verstehen, warum ich mit einer Einheit x potenziert mit den natürlichen Zahlen ALLE Einheiten bekomme.
Bspw. bei m = 5, Phi(5) = 4, x = 2
2^0 = 0
2^1 = 2
2^3 = 3
2^4 = 1

Nun gut, sind also k Einheiten, also bekomme ich k-verschiedene Restklassen wenn ich x^k rechne - das ist der Punkt den ich noch nicht verstehe.

Was denkst du, was ich oben gerade bewiesen habe. Kann ja sein, dass du das Vorgekaute nicht magst, aber in diesem Fall solltest du es doch mal lesen: Mein letzter Beitrag oben war ein indirekter Beweis, wo genau das bewiesen wurde:

Ist $\begin{eqnarray*} \operatorname{ord}(x)=k \end{eqnarray*}$ , dann sind alle $\begin{eqnarray*} k \end{eqnarray*}$ Werte $\begin{eqnarray*} x^0,x^1,\ldots,x^{k-1} \end{eqnarray*}$ verschiedene Restklassen modulo $\begin{eqnarray*} m \end{eqnarray*}$ . Ist nun speziell $\begin{eqnarray*} k=\varphi(m) \end{eqnarray*}$ , m.a.W. $\begin{eqnarray*} k=\operatorname{ord}(\mathbb{Z}_m^+) \end{eqnarray*}$ , dann erhalten wir wegen der paarweise Verschiedenheit dieser $\begin{eqnarray*} k \end{eqnarray*}$ Potenzen genau $\begin{eqnarray*} \varphi(m)=\operatorname{ord}(\mathbb{Z}_m^+) \end{eqnarray*}$ Werte. Das sind aber genauso viele Werte, wie $\begin{eqnarray*} \mathbb{Z}_m^+ \end{eqnarray*}$ überhaupt enthält, also müssen die Mengen gleich sein.

Vom gruppentheoretischen Standpunkt: $\begin{eqnarray*} x \end{eqnarray*}$ erzeugt ja (also durch seine Potenzen) eine Untergruppe von $\begin{eqnarray*} \mathbb{Z}_m^+ \end{eqnarray*}$ , und zwar vom Umfang $\begin{eqnarray*} \operatorname{ord}(x) \end{eqnarray*}$ . Ist nun speziell $\begin{eqnarray*} \operatorname{ord}(x) = \operatorname{ord}(\mathbb{Z}_m^+) \end{eqnarray*}$ , dann ist diese erzeugte Untergruppe zwangsläufig die gesamte Gruppe $\begin{eqnarray*} \mathbb{Z}_m^+ \end{eqnarray*}$ .

Ich mag das Vorkauen genauso wenig, aber welche Zwischenstufe stellst du dir denn vor? Alle Tipps oben von Abakus und mir habt ihr nicht angenommen.

P.S.: Mit dem Begriff "Einheit" kann ich hier nix anfangen. Für mich ist eine Einheit ein Teiler der 1 in einem Ring, davon kann hier keine Rede sein. Falls du damit die primitiven Wurzeln meinst, dann ist deine Aufzählung falsch, die dürfte nur lauten:

2^1 = 2
2^3 = 3

Damit kriegt man tatsächlich alle primitiven Wurzeln modulo m. Und wenn du dir die zugehörigen Exponenten 1,3 genauer anschaust: Das sind genau diegenigen Exponenten aus $\begin{eqnarray*} 0\leq n\leq \varphi(m)-1 \end{eqnarray*}$ , die teilerfremd zu $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ sind. Und das ist dann auch die allgemeine Aussage: Es gibt entweder keine oder genau $\begin{eqnarray*} \varphi(\varphi(m)) \end{eqnarray*}$ primitive Wurzeln modulo $\begin{eqnarray*} m \end{eqnarray*}$ . Aber das ist nicht Gegenstand der aktuell hier im Thread nachhgefragten Aufgabe.

Neue Frage »

Antworten »

Beweis über die Menge der Einheiten

Verwandte Themen