Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » lösen simultanen Kongruenzen

lösen simultanen Kongruenzen

Universität / Fachhochschule

Tags: chinesischer Restsatz

Antje11 aktiv_icon

11:42 Uhr, 05.01.2012

Hi,
ich habe gerade ein kleines Problem bei der Lösung von zwei Kongruenzen.

Die Aufgabe ist :

Finden Sie ganze Zahlen

x; y,

welche jeweils gleichzeitig folgende zwei Kongruenzen
erfüllen.

x

≡

7 mod 31

und

x

≡

6 mod 94

bzw.

y

≡

2 mod 11

und

y

≡

3 mod 49

Ich habe mal ein bisschen geguckt aber so wirklich weiß ich nicht ob ich das richtig mache und komme auch bei einer Sache nicht weiter.

Für die erste Aufgabe:

31

und

94

haben ja nur den ggt 1

muss ich dann erstmal umformen.

94 x

≡

658 mod 2914

31 x

≡

186 mod 2914

addieren

125 x

≡

844 mod 2914

jetzt kann ich doch den euklidische Algorithmus anwenden.

2914 = 23 \cdot 125 + 39,

125 = 3 \cdot 39 + 8

39 = 4 \cdot 8 + 7

8 = 1 \cdot 7 + 1 \Rightarrow

ggt 1

1 = 8 - (1 \cdot 7)

= 8 - (39 - 4 \cdot 8) = 5 \cdot 8 - 1 \cdot 39

= - 1 \cdot 39 + 5 \cdot 8 = - 1 \cdot 39 + 5 (125 - 3 \cdot 39

und ab da komm ich nicht weiter.

Habe ich jetzt total den blödsinn gerechnet????

Danke schon mal

Grüße

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

Antje11 aktiv_icon

13:28 Uhr, 06.01.2012

Hat irgendwer nen Plan oder nen Tipp für mich?

Danke

michaL aktiv_icon

17:00 Uhr, 08.01.2012

Hallo,

ich hab lange überlegt, ob ich antworten soll. Der Grund liegt darin, dass es für das Zusammenfassen zweier Kongruenzen (bei denen das möglich ist) auch Formeln gibt. Ich habe diese Formeln nie gelernt, sondern verwende meine eigenen Überlegungen.
Und da die eben nicht "Lehrbuch" sind, ...

Nun gut, es geht also um:

x \equiv 7

mod 31 (I)

x \equiv 6

mod 94 (II)

Tatsächlich gilt ggT(94,31)=1, da

1 = 94 - 3 \cdot 31

. Diese Kongruenz ist also zusammenfassbar zu

x \equiv a

mod kgV(31,94), wobei

a

noch zu bestimmen ist, da ggT(31,94)

∣ 7 - 6

gilt.

Um

a

zu bestimmen, verfahre ich immer so:
(I)

\overset{}{\Leftrightarrow} x = 31 k + 7

für ein geeignetes

k \in ℤ

(II)

\overset{}{\Leftrightarrow} x = 94 l + 6

für ein geeignetes

l \in ℤ

\Rightarrow 31 k + 7 = 94 l + 6 \overset{}{\Leftrightarrow} 1 = 7 - 6 = 94 l - 31 k

Nun brauche ich eine Zerlegung von

1 = 7 - 6

in eine "Summe" von Vielfachen von 31 und 94, was ja geht, da der ggT(31,94) ein Teiler davon ist. Glücklicherweise "sieht man eine solche Zerlegung (sonst halt erweiterten euklidischen Algorithmus anwenden):

1 = 94 - 3 \cdot 31

Also gilt:

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

. Da

31

und

94

teilerfremd sind, kommen als Lösungen nur

k - 3 = r \cdot 94

und

l - 1 = r \cdot 31

infrage, wobei

r \in ℤ

.
Da wir nur eine Lösung suchen, mache man sich die Sache so einfach wie möglich:

r = 0

. Dann gelten:

k - 3 = 0 \overset{}{\Leftrightarrow} k = 3

l - 1 = 0 \overset{}{\Leftrightarrow} l = 1

und letztlich

x = 31 k + 7 = 94 l + 6 = 100 = : a

Die beiden Kongruenzen können also zusammengefasst werden zu

x \equiv 100

mod 2914

Mfg Michael

Antje11 aktiv_icon

09:40 Uhr, 09.01.2012

Hi,
da habe ich wirklich total falsch gerechnet :-)

VIelen Dank

Antje11 aktiv_icon

19:26 Uhr, 09.01.2012

Hi,
ich habe das gerade mit deinem "System" für

y

gemacht und wenn ich mich nicht irre und wirklich alles verstanden habe müsste da doch

101

rauskommen oder?

y≡2mod11
y≡3mod49

ggt(11,49)=1, da

1 = 2 \cdot 49 - 9 \cdot 11

lässt sich also zu x≡a

mod

KgV(11,49)

dann das a bestimmen:

(i) \Leftrightarrow x = 11 k + 2, k \in ℤ

(ii)<=>

x = 49 l + 3, l \in ℤ

\Rightarrow 11 k + 2 = 49 l - 11 k \Leftrightarrow 1 = 3 - 2 = 49 l - 11 k,

Zerlegung von

1 = 3 - 2

1 = 2 \cdot 49 - 9 \cdot 11 = 49 l - 11 k

\Leftrightarrow 11 (k - 9) = 49 (l - 2)

im Anschluss noch

r

berechnen:

r = 0

K = 9

und

l = 2

einsetz

x = 11 \cdot 9 + 2 = 49 \cdot 2 + 3 = 101 = : a

Wenn das jetzt stimmt finde ich deine Erklärung super :-) Vielen Dank nochmal

leann aktiv_icon

16:52 Uhr, 11.01.2012

Ich habe bei

y

auch

101

raus :-).

LG

leann aktiv_icon

17:05 Uhr, 11.01.2012

Wie lautet dies hier zusammengefasst?

sprich:

y \equiv 101 mod . .

960940

958395

	Status: nicht eingeloggt	Noch nicht registriert?