Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Simultane Kongruenzen

Simultane Kongruenzen

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie, Kongruenz, simultan

j-frost aktiv_icon

12:17 Uhr, 14.03.2010

Hallo,
wie löse ich die folgende simultane Kongruenz?

I) 2 x \equiv 8 mod 3

II) 4 x \equiv 7 mod 11

III) 6 x \equiv 4 mod 14

I und II finde ich ja noch recht easy, sollten äquivalent sein zu

I') x \equiv 16 \equiv 1 mod 3

II') x \equiv 21 \equiv 10 \equiv - 1 mod 11

,

aber was ist mit III? Zu

6

finde ich einfach kein Inverses in

ℤ / 14 ℤ

, obwohl

ggT (6, 14) = 2 ∣ 4

, oder hab' ich da was übersehen?
Gruß,
j-frost

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Dreiecke und Kongruenz

michaL aktiv_icon

21:30 Uhr, 15.03.2010

Hallo Julian,

also, es geht bei simultanen Kongruenzen stets darum, zwei zu einer neuen (äquivalenten) zusammenzufassen.
Dafür gibt es eine Formel (Stichwort: chinesischer Restsatz, siehe etwa de.wikipedia.org/wiki/Chinesischer_Restsatz )

Ich kann mir die Formel aber einfach nicht merken, daher mal an den ersten beiden Kongruenzen, wie man daraus eine macht, in meiner eigenen Denk- und Schreibweise:

x \equiv 1 mod 3

x \equiv - 1 mod 11

heißt ja:

x = 1 + 3 k

für ein

k

bzw.

x = - 1 + 11 l

für ein

l

, also

1 + 3 k = - 1 + 11 l \overset{}{\Leftrightarrow} 11 l - 3 k = 2

. Das ist nur dann machbar (dann geht es aber auch immer), wenn der

ggT (3; 11)

ein Teiler von 2 ist. Da

ggT (3; 11) = 1

gilt, also erfüllt, etwa

2 = 11 - 3 \cdot 3

Ergibt erstmal:

11 l - 3 k = 11 - 3 \cdot 3 \overset{}{\Leftrightarrow} 11 (l - 1) = 3 (k - 3)

. Also muss

l - 1 = 3

gelten und

k - 3 = 11

bzw.

l = 4

und

k = 14

. Daraus ergibt sich

x = 43

.
Also lassen sich die Kongruenzen

x \equiv 1 mod 3

x \equiv - 1 mod 11

zusammenfassen zu

x \equiv 43 mod kgV (3; 11)

, also

x \equiv 43 mod 33

Die verbleibende Kongruenz kannst du jetzt mit der von mir erstellten wieder zu einer neuen vereinfachen. Probier das doch mal.

Mfg Michael

j-frost aktiv_icon

22:11 Uhr, 17.03.2010

Hm... ich verstehe alles, was du geschrieben hast. Leider fürchte ich, dass das mein Problem nicht löst: Ich scheitere an der Umformung von Gleichung III in die Form

x \equiv a mod m

. Wie geht das bei III?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

738338

736455

	Status: nicht eingeloggt	Noch nicht registriert?