Kongruenzen

20.07.2008, 21:30

Fletcher

Kongruenzen

Guten Abend,

kann mir vielleicht jemand bei folgenden Kongruenzen etwas weiterhelfen?

a)Bestimme alle ganzen Zahlen, die die gegebenen Kongruenzen gleichzeitig erfüllen:

$\begin{eqnarray*} x = 1 mod 3, x=1 mod 5, x=1 mod 7 \end{eqnarray*}$

Gibt es hier eine allg. recht schnelle und einfach Vorgehensweise diese Zaheln zu finden, oder geht das nur durch probieren?

b)Bestimme die Lösungen zu folgender Kongruenz: $\begin{eqnarray*} 15x=3 mod 21 \end{eqnarray*}$

Hier habe ich folgendes gemacht: 21= 7*3

$\begin{eqnarray*} 15x=0 mod 3 \end{eqnarray*}$
Das erfüllen alle $\begin{eqnarray*} x \in \mathbb Z_3 \end{eqnarray*}$

$\begin{eqnarray*} 15x=3 mod 7 \end{eqnarray*}$
Das erfüllt nur die 3

Es folgt also das die gegebene Kongruenz alle Vielfachen von 3 erfüllen.

c)Kann das sein, dass die Kongruenz $\begin{eqnarray*} 20x=12 mod 30 \end{eqnarray*}$ keine Lösungen besitzt?

Vielen Dank, die Klausur rückt näher Augenzwinkern

20.07.2008, 21:37

tmo

Auf diesen Beitrag antworten »

zur a)

Für ein solches x gilt 3|x-1, 5|x-1 und 7|x-1

Stichwort: kgV

zur b)

Du hast richtig erkannt, dass es reicht die Lösungen von $\begin{eqnarray*} 15x \equiv 3 \pmod 7 \end{eqnarray*}$ zu bestimmen. Nun nutze mal $\begin{eqnarray*} 15 = 3 \cdot 5 \end{eqnarray*}$

die c) ist eigentlich fast trivial. Betrachte einfach nur die letzte Ziffer von 20x.

20.07.2008, 23:59

Auf diesen Beitrag antworten »

Zitat:

Original von Fletcher
a)Bestimme alle ganzen Zahlen, die die gegebenen Kongruenzen gleichzeitig erfüllen:

$\begin{eqnarray*} x = 1 mod 3, x=1 mod 5, x=1 mod 7 \end{eqnarray*}$

Gibt es hier eine allg. recht schnelle und einfach Vorgehensweise diese Zaheln zu finden

Ja: http://de.wikipedia.org/wiki/Chinesischer_Restsatz

Im vorliegenden Fall geht das allerdings sehr schnell: Da es jeweils derselbe Rest ist (nämlich 1), ist die Lösung sofort klar:

$\begin{eqnarray*} x\equiv 1 \mod (3\cdot 5\cdot 7) = 1 \mod 105 \end{eqnarray*}$

21.07.2008, 08:23

Fletcher

Auf diesen Beitrag antworten »

Vielen Dank für die Hilfestellungen,

also ich ja bei c) meine Annahme richtig, dass sie nicht lösbar ist und die Begründung dazu lieferst du tmo!

Chinesischer Restsatz ist ein sehr gutes Stichwort, den werde ich mir nochmal genauer anschauen.

Aber bei der b) verstehe ich nicht worauf du hinsaus willst mit der Zerlegung von 15=5*3 ?

Gruß

21.07.2008, 10:56

tmo

Auf diesen Beitrag antworten »

Offensichtlich ist doch $\begin{eqnarray*} 5x \equiv 1 \pmod 7 \Longrightarrow 3 \cdot 5 x \equiv 3 \pmod 7 \end{eqnarray*}$ .

Es gilt aber sogar die Äquivalenz. Übrig bleibt eine relativ einfache Kongruenz.

22.07.2008, 19:00

Fletcher

Auf diesen Beitrag antworten »

Hallo an Alle nochmal,

die letzten Beispiele habe ich jetzt alle nachvollzogen und auch verstanden.

Aber jetzt habe ich noch etwas gefunden:

$\begin{eqnarray*} x=2mod4, x=4 mod 7, x=3mod11 \end{eqnarray*}$

Kann mir jemand sagen, wie ich ein x finde welches diese Kongruenzen gleichzeitig erfüllt? Ähnlich wie oben, ist der ggT(4,7,11)=1 also kann ich auch in $\begin{eqnarray*} \mathbb Z_{308} \end{eqnarray*}$ rechnen, aber wie schaut hier die Kongruenz aus?

Oben war es ja offensichtlich unter Beispiel a) aber wie schaffe ich das jetzt mit der 2, 4 und 3???

Danke für die Antworten Augenzwinkern

22.07.2008, 22:47

tmo

Auf diesen Beitrag antworten »

Bestimme z.b. erst ein x, dass die ersten beiden Kongruenzen erfüllt. Mit dem chinesischen Restsatz kennst du dann alle x, die die ersten beiden Kongruenzen erfüllen.

Suche dann eine von diesen, die auch die dritte Kongruenz erfüllt. Zur Not kann man einfach mal ausprobieren, wenn man nach 11 Versuchen keine Lösung gefunden hat, gibt es keine.

23.07.2008, 06:46

Auf diesen Beitrag antworten »

Zitat:

Original von Fletcher
Ähnlich wie oben, ist der ggT(4,7,11)=1 also kann ich auch in $\begin{eqnarray*} \mathbb Z_{308} \end{eqnarray*}$ rechnen

Vorsicht mit solchen Aussagen: Aus der Teilerfremdheit an sich kann man noch nicht auf die Lösbarkeit der Kongruenz schließen, allenfalls aus der paarweisen Teilerfremdheit. Die Begründung sollte also eher

ggT(4,7) = ggT(4,11) = ggT(7,11) = 1

lauten.

Beispiel: Es ist auch ggT(6,10,15)=1, aber die Kongruenz

$\begin{eqnarray*} x\equiv 0\mod 6, \qquad x\equiv 1\mod 10, \qquad x\equiv 2\mod 15 \end{eqnarray*}$

hat keine Lösung - nicht mal, wenn man das System auf nur 2 der 3 Gleichungen reduziert. Augenzwinkern

23.07.2008, 08:29

Fletcher

Auf diesen Beitrag antworten »

Alles klar das wusste ich nicht, also gilt dieser Satz wirklich nur, wenn diese paarweise teilerfremd sind. Also: $\begin{eqnarray*} ggT(m,n)=1 \end{eqnarray*}$ ist äquivalent zu $\begin{eqnarray*} \mathbb Z_n \oplus \mathbb Z_m \cong \mathbb Z_{mn} \end{eqnarray*}$

Danke nochmal, jetzt müsste ich es heute hinbekommen. Augenzwinkern

Neue Frage »

Antworten »

Kongruenzen

Verwandte Themen