Lineare Kongruenz mit unbestimmten Modul

23.12.2012, 14:14	clavat	Auf diesen Beitrag antworten »
Lineare Kongruenz mit unbestimmten Modul Meine Frage: Bestimmen Sie die Lösungsmenge der folgenden Kongruenz $\begin{eqnarray} 99 x \equiv 7 \ mod \ n \end{eqnarray}$ , wobei $\begin{eqnarray} x \in \mathbb{Z}, n \in \mathbb{N} \end{eqnarray}$ Meine Ideen: Also ich weiß wohl, wie ich solche Kongruenzen löse, wenn das n bekannt ist... Aber so??? Erstmal ist klar, dass n teilerfremd zu 99 sein muss, da sonst ihr ggT nicht 7 teilt. Aber wie soll man dann weiter vorgehen? Normalerweise würde ich dann 1 als Linearkombination von 99 und n schreiben über den erweiterten euklidischen Algorithmus. Und dann einfach mit 7 multiplizieren. Aber wie soll das gehen, wenn ich n nicht kenne? Kann man x dann überhaupt explizit angeben?
23.12.2012, 14:52	Mystic	Auf diesen Beitrag antworten »
RE: Lineare Kongruenz mit unbestimmten Modul Wenn n ein Vielfaches von 3 oder 11 ist, dann ist die Lösungsmenge leer, ansonsten besteht sie aus genau jenen ganzen Zahlen, welche zu $\begin{eqnarray} 7 \cdot 99^{\lambda(n)-1} \mod n \end{eqnarray}$ kongruent sind ( $\begin{eqnarray} \lambda(n) \end{eqnarray}$ ist dabei die sog. Carmichaelfunktion)...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »