Partner von azubiworld.com - Logo
 
Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » lösen simultanen Kongruenzen

lösen simultanen Kongruenzen

Universität / Fachhochschule

Tags: chinesischer Restsatz

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Antje11

Antje11 aktiv_icon

11:42 Uhr, 05.01.2012

Antworten
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.
x7mod31 und x6mod94 bzw. y2mod11 und y3mod49

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.

94x658mod2914
31x186mod2914

addieren

125x844mod2914

jetzt kann ich doch den euklidische Algorithmus anwenden.

2914=23125+39,
125=339+8
39=48+7
8=17+1 ggt 1

1=8-(17)
=8-(39-48)=58-139
=-139+58=-139+5(125-339

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."
Neue Frage
Antje11

Antje11 aktiv_icon

13:28 Uhr, 06.01.2012

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

Danke
Antwort
michaL

michaL aktiv_icon

17:00 Uhr, 08.01.2012

Antworten
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:
x7 mod 31 (I)
x6 mod 94 (II)

Tatsächlich gilt ggT(94,31)=1, da 1=94-331. Diese Kongruenz ist also zusammenfassbar zu
xa 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) x=31k+7 für ein geeignetes k
(II) x=94l+6 für ein geeignetes l
31k+7=94l+61=7-6=94l-31k

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-331

Also gilt: 1=94-331=94l-31k31(k-3)=94(l-1). Da 31 und 94 teilerfremd sind, kommen als Lösungen nur k-3=r94 und l-1=r31 infrage, wobei r.
Da wir nur eine Lösung suchen, mache man sich die Sache so einfach wie möglich: r=0. Dann gelten:
k-3=0k=3, l-1=0l=1 und letztlich x=31k+7=94l+6=100=:a

Die beiden Kongruenzen können also zusammengefasst werden zu
x100 mod 2914

Mfg Michael
Antje11

Antje11 aktiv_icon

09:40 Uhr, 09.01.2012

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

VIelen Dank

Antje11

Antje11 aktiv_icon

19:26 Uhr, 09.01.2012

Antworten
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=249-911
lässt sich also zu x≡a mod KgV(11,49)

dann das a bestimmen:

(i)x=11k+2,k
(ii)<=> x=49l+3,l

11k+2=49l-11k1=3-2=49l-11k,

Zerlegung von 1=3-2

1=249-911=49l-11k
11(k-9)=49(l-2)

im Anschluss noch r berechnen:
r=0
K=9 und l=2

einsetz

x=119+2=492+3=101=:a


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

leann aktiv_icon

16:52 Uhr, 11.01.2012

Antworten
Ich habe bei y auch 101 raus :-).

LG
Antwort
leann

leann aktiv_icon

17:05 Uhr, 11.01.2012

Antworten
Wie lautet dies hier zusammengefasst?

sprich:

y101mod...