Kongruenzen

01.07.2019, 15:09	.Tina.	Auf diesen Beitrag antworten »
Kongruenzen Meine Frage: Hallo, ich habe folgende Gleichung: $\begin{eqnarray} 3x + 5 \equiv 4 (mod 55) \end{eqnarray}$ Ich weiß leider gar nicht, wie ich die lösen soll. In den Lösungen stand nur: ist äquivalent zu: $\begin{eqnarray} 3x \equiv 54 (mod 55) \end{eqnarray}$ ist äquivalent zu : $\begin{eqnarray} x\equiv 18 (mod 55) \end{eqnarray}$ Wie kommt man von 3x+5 kongruent zu 4 mod 55 auf 3x kongruent zu 54 (mod 55)? Gibt es da irgendeine Rechenregel, die mir gerade nicht bewusst ist? Im letzten Schritt teil man dann einfach durch 3. Aber damit ist doch die Aufgabe noch nicht gelöst oder? Ich möchte doch eine Lösung für x rausbekommen. Hilft mir da irgendwie der chinesische Restsatz weiter? Oder könnte ich den erweiterten euklidischen Algorithmus anwenden um eine Lösung für x zu bekommen? Ich würde mich freuen, wenn mir jemand weiterhelfen kann. Viele Grüße Tina. Meine Ideen: -
01.07.2019, 16:22	Helferlein	Auf diesen Beitrag antworten »
Du machst Dir das Leben schwerer als es ist. Mit Kongruenten kannst Du vieles rechnen, was auch mit Gleichungen geht. In deinem Fall wurde zunächst 5 subtrahiert und dann die Restklasse ausgenutzt, denn -1 entspricht der 54. Danach wurden beide Seiten mit dem Inversen von drei multipliziert. Da dies alles Äquivalenzumformungen sind, stehen deine Lösungen fest : x=18+55k mit beliebigen ganzen Zahlen k.
01.07.2019, 16:47	HAL 9000	Auf diesen Beitrag antworten »
@Tina Mal noch die einzelnen Rechenschritte etwas näher ausgeführt: $\begin{eqnarray} 3x+5&\equiv& 4\bmod 55\qquad \bigm\|\;-5\\ 3x&\equiv& -1\bmod 55 \end{eqnarray}$ Nun ist die ganze Zahl -1 nicht durch 3 teilbar, daher suchen wir eine ganze Zahl in derselben Restklasse wie -1, die durch 3 teilbar ist. Und das tut man durch fortlaufende Addition mit Modul 55, bis man das geschafft hat: -1 nicht durch 3 teilbar -1+55 = 54 ist durch 3 teilbar, Treffer. Daher geht es weiter mit $\begin{eqnarray} 3x&\equiv& 54\bmod 55\qquad \bigm\|\;:3\\ x&\equiv& 18\bmod 55 \end{eqnarray}$ . Diese Trial- und Error-Methode ist grundsätzlich gut geeignet für Kongruenzen $\begin{eqnarray} ax\equiv b\bmod m \end{eqnarray}$ , solange $\begin{eqnarray} a \end{eqnarray}$ betragsmäßig klein (und natürlich teilerfremd zu $\begin{eqnarray} m \end{eqnarray}$ ) ist. Für größere $\begin{eqnarray} a \end{eqnarray}$ zieht man dann doch ein systematisches Verfahren wie den EEA angewandt auf $\begin{eqnarray} a,m \end{eqnarray}$ hinzu.
02.07.2019, 09:01	.Tina.	Auf diesen Beitrag antworten »
Vielen lieben Dank. Nochmal eine andere Frage. Ich habe mir gerade mal noch ein anderes Beispiel angeguckt. Wenn ich die Kongruenz habe $\begin{eqnarray} x^{2} - 1 \equiv 0 (mod 35) \end{eqnarray}$ Dann könnte ich die ja umschreiben zu: $\begin{eqnarray} x^{2} \equiv 1 (mod35) \end{eqnarray}$ Wenn ich jetzt die 35 in ihre Primfaktoren zerlege, hätte ich ja: $\begin{eqnarray} x^{2} \equiv 1 (mod7) \end{eqnarray}$ und $\begin{eqnarray} x^{2} \equiv 1 (mod5) \end{eqnarray}$ Wie würde ich dann hier weitermachen, um das $\begin{eqnarray} x^{2} \end{eqnarray}$ umzuschreiben. Ich könnte es ja zu x mal x umschreiben. Aber das bringt mich glaube auch nicht so wirklich weiter.
02.07.2019, 10:28	Helferlein	Auf diesen Beitrag antworten »
Die Lösung 1 und 6 bzw. 1 und 4 für die Einzelgleichungen sind Dir einleuchtend? Dann musst Du nur noch zeigen, dass dies die einzigen Möglichkeiten sind und danach die beiden Lösungsmengen schneiden.
04.07.2019, 10:20	.Tina.	Auf diesen Beitrag antworten »
Ja, die Lösungen 1 und 6 bzw. 1 und 4 sind mir klar. Aber woher weiß ich denn, dass das die einzigen Möglichkeiten sind? Wie kann ich das denn zeigen?
Anzeige

04.07.2019, 17:32	HAL 9000	Auf diesen Beitrag antworten »
Aus $\begin{eqnarray} 0\equiv x^2-1 = (x-1)(x+1)\bmod p \end{eqnarray}$ folgt entweder $\begin{eqnarray} x-1\equiv 0\bmod p \end{eqnarray}$ oder $\begin{eqnarray} x+1\equiv 0\bmod p \end{eqnarray}$ , da der Restklassenring modulo $\begin{eqnarray} p \end{eqnarray}$ für Primzahlen $\begin{eqnarray} p \end{eqnarray}$ nullteilerfrei ist. Ganz allgemein hat die Gleichung $\begin{eqnarray} x^2\equiv a\bmod p \end{eqnarray}$ für ungerade Primzahlen $\begin{eqnarray} p \end{eqnarray}$ sowie $\begin{eqnarray} a\not\equiv 0\bmod p \end{eqnarray}$ entweder keine Lösung oder genau zwei, damit verbunden sind dann die Bezeichnungen "Quadratischer (Nicht-)Rest" für $\begin{eqnarray} a \end{eqnarray}$ . P.S.: Quadratische Kongruenzen sind ein ganz eigenes, ausführlichst erforschtes Thema - ein wenig Grundlagenwissen dazu wäre angebracht, vielleicht kommt ja noch was dazu in deiner Lehrveranstaltung bzw. du hast es verpasst.
09.07.2019, 15:39	.Tina.	Auf diesen Beitrag antworten »
Hab es jetzt hinbekommen. Vielen Dank nochmal für eure Hilfe

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »