Lösungsanzahl einer Kongruenz

08.01.2009, 22:35	Bjoern1982	Auf diesen Beitrag antworten »
Lösungsanzahl einer Kongruenz Hallo, und noch ein Problem habe ich mit der folgenden Aufgabe: a) Gegeben ist dass k \| p-1 und man soll zeigen dass die Kongruenz $\begin{eqnarray} x^k \equiv 1\ mod\ p \end{eqnarray}$ genau k verschiedene Lösungen besitzt. b) Verallgemeinert soll man dann noch die Kongruenz $\begin{eqnarray} x^k \equiv a\ mod\ p \end{eqnarray}$ betrachten und einen einfrachen Weg finden, wie man k,p und den Index I(a) dazu benutzen kann um auf die Anzahl der Lösungen der Kongruenz zu kommen. Ich bin aus dem Thema irgendwie total raus und bitte um einen Hinweis was ich benötige um hier weiter zu kommen. Gruß Björn
08.01.2009, 22:46	AD	Auf diesen Beitrag antworten »
Du hast doch sicher kennengelernt, dass in zyklischen Gruppen $\begin{eqnarray} (\mathbb{Z}/m\mathbb{Z})^ \end{eqnarray}$ für $\begin{eqnarray} x,a \in (\mathbb{Z}/m\mathbb{Z})^* \end{eqnarray}$ folgende Äquivalenz gilt: $\begin{eqnarray} x^k \equiv a \mod m \quad \Longleftrightarrow \quad k\cdot \operatorname{ind}_g(x) \equiv \operatorname{ind}_g(a) \mod \varphi(m) \end{eqnarray}$ mit irgendeiner promitiven Wurzel $\begin{eqnarray} g\mod m \end{eqnarray}$ . Ist $\begin{eqnarray} m \end{eqnarray}$ Primzahl, also $\begin{eqnarray} m=p \end{eqnarray}$ , dann wird daraus $\begin{eqnarray} x^k \equiv a \mod p \quad \Longleftrightarrow \quad k\cdot \operatorname{ind}_g(x) \equiv \operatorname{ind}_g(a) \mod (p-1) \end{eqnarray}$ Der Index der 1 ist 0, also gilt speziell $\begin{eqnarray} x^k \equiv 1 \mod p \quad \Longleftrightarrow \quad k\cdot \operatorname{ind}_g(x) \equiv 0 \mod (p-1) \end{eqnarray*}$ . Damit lassen sich alle deine Fragen ziemlich bequem beantworten.
08.01.2009, 22:48	Bjoern1982	Auf diesen Beitrag antworten »
Hui was ein Glück dass du um diese Zeit nochmal reinschaust, ich werde is damit mal probieren Danke
09.01.2009, 10:41	Bjoern1982	Auf diesen Beitrag antworten »
Hast du vielleicht noch einen kleinen Hinweis auf was ich genau achten muss um Informationen über die ANZAHL der Lösungen zu bekommen - irgendwie sehe ich es noch nicht Edit: Normalerweise würde ich ja Aussagen über die Anzahl von Lösungen mittels des ggT machen ---> ggT(k,p-1) Zum einen bin ich aber unsicher ob das überhaupt hinkommt und zum anderen würde ich damit ja nicht Bezug auf den Index ind(a) nehmen
09.01.2009, 11:59	AD	Auf diesen Beitrag antworten »
Nochmal genauer: $\begin{eqnarray} \operatorname{ind}_g \end{eqnarray}$ ist eine bijektive Abbildung von $\begin{eqnarray} (\mathbb{Z}/p\mathbb{Z})^ \end{eqnarray}$ nach $\begin{eqnarray} \mathbb{Z}/(p-1)\mathbb{Z} \end{eqnarray}$ . Du musst also nur nachzählen, für wieviele Restklassen $\begin{eqnarray} y\in \mathbb{Z}/(p-1)\mathbb{Z} \end{eqnarray}$ die Kongruenz $\begin{eqnarray} k \cdot y \equiv 0 \mod (p-1) \end{eqnarray}$ gilt. Und wenn du richtig nachzählst, kommst du auf die Anzahl $\begin{eqnarray} k \end{eqnarray*}$ .
10.01.2009, 13:52	Bjoern1982	Auf diesen Beitrag antworten »
Abzählen...ok wenn ich das mal mit ein paar Zahlen durchspiele haut das auch hin. Nur verallgemeinernd zu sagen, dass es auch immer für jeden Teiler k von p-1 diese k Lösungen gibt, dazu fällt mir weiterhin irgendwie nur das Kriterium ggt(k,p-1)=k für die Anzahl der Lösungen ein Edit: Wie könnte denn eine Argumentation durch Abzählen lauten ? Muss man das mit Induktion zeigen ?
Anzeige

10.01.2009, 15:53	AD	Auf diesen Beitrag antworten »
Herrje... Wenn ich das "Abzählen" in Anführungszeichen schreibe, dann solltest du das nicht so wörtlich nehmen. Ich hatte angenommen, dass du inzwischen genug Erfahrung mit linearen Kongruenzen hast - nimm den Weg, der dir am besten geläufig ist. Ich finde es ziemlich unnötig, alles wieder auf den Urschleim zurückführen zu müssen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »