Mathe

Wie finde ich alle x Element Z, bei dem System simultaner Kongruenzen ?

2x isomorph zu 3 mod 9
3x isomorph zu 5 mod 7

Als Hinweis ist gegeben :

Zeigen Sie dass 2 (bzw. 3) eine Einheit in dem Ring z/9Z (bzw. Z/7Z) ist
und formrn Sie das Gleichungssystem um.

Bitte nicht nur die Lösung, sondern vorallem den Rechenweg, ich steh zur Zeit leider voll auf'm Schlauch!

mrchat

gehört hier net rein denke ich oder??

cya

Finde ich schon.

Da wir bald ein Programm zum Lösen von Systemen simultaner Kongruenzen
schreiben müssen und wir erst die nötige Mathematik lernen sollen, gehört das sicher zu "Rund um die Programmierung" , wie Mathematik generell.
Oder kannst du Dir Informatik ohne Mathematik vorstellen?

prolog

Hi

Natürlich kann man die Frage hier posten. Aber es gibt bessere Foren für solche Themen. Meine These ist das hier nicht wirklich viele Leute sind, die sich mit diskreter Mathematik richtig auskennen. Ich jedenfalls nicht.

a) 2x isomorph zu 3 mod 9
b) 3x isomorph zu 5 mod 7

Das soll wohl eher kongruent statt isomorph heißen.

Setz Dich auf jeden Fall mal mit dem Thema chinesischer Restsatz auseinander. Der ist dafür prima geeigenet.

Der sagt nämlich zunächst mal, weil 7 und 9 (die beiden Restklassen) Teilerfremd sind ist das Ergebnis eindeutig bestimmt modulo 7*9=63.
Sprich: haben wir eine Lösung, dann haben wir alle Lösungen. Nämlich die Nebenklasse der Lösung in Z/63Z.

Ich schreibe jetzt = für kongruent und wenn ich modulo rechne dann schreibe ich in Klammern modulo was, also zum Beispiel 10 = 2 (8).

a) => 2*x=3 (9), es gilt 5*2 = 10 = 1(9)
=> x = 15 = 6 (9), also x = k*9+6

b) => 3*(k*9+6) = 27*k+18 = 6*k+4 = 5 (7)
=> 6*k = 1 (7), 6*6 = 36 = 1 (7)
=> k = 6(7)

Okay, dann nehmen wir doch einfach mal k=6 => x=60
260 mod 9 = 120 mod 9 = 30 mod 9 = 3 mod 9
360 mod 7 = 180 mod 7 = 40 mod 7 = 5 mod 7

wie gewünscht.
Außerdem wissen wir nach dem chinesischen Restsatz, daß
jedes Element der Form x = 60+k*63 mit k € Z eine Lösung ist und dies die einzigen Lösungen sind!
Hatte ich schon erwähnt, daß Du Dir den chinesischen Restsatz wirklich anschauen solltest?

MfG Jester

P.S.:
Wenn Du's implementieren sollst, dann ist wahrscheinlich der Beweis vom chin. Restsatz interessant, da dort die Lösung konstruiert wird. Das ist leichter zu programmieren. Achja und die Inversen bestimmen kann man auch mit dem euklidischen Algorithmus.

prolog

Hi

Okey einer. Respekt Jester. Apropos chinese remainder theorem es gibt einige gute Bücher zu dem Thema oder einfach googeln. Nur für den Fall dass du das öfter brauchst. Da stehen auch noch ein Haufen weitere Algorithmen drin und deren Herleitungen(bzw. Beweise).

Die Lösung findet man hier auch ein wenig anders!

2x kongruent zu 3 mod 9
3x kongruent zu 5 mod 7

2 ist Einheit in 9 (weil 25 =1 in Z/9Z)
3 ist Einheit in 7 (weil 35 =1 in Z/7Z)

Damit kann man das Gleichungssystem umformen

x kongruent zu 32^-1 mod 9
x kongruent zu 53^-1 mod 7

<=>

x kongruent zu 25 mod 9
x kongruent zu 35 mod 7

<=>

x kongruent zu 6 mod 9
x kongruent zu 4 mod 7

jetzt kann man auch leicht ausprobieren
sehen wir uns x konguent zu 6 mod 9 an:

x kann als Lösung haben: 15, 24, 33, 42, 51, 60 dann widerhohlt sich alles.
Testet man die 6 Werte passt nur 60 auch zu x kongruent zu 4 mod 7
Und natürlich 60+z*63

rüdiger

Original erstellt von mrchat:
**gehört hier net rein denke ich oder??

cya**

Mathe ist hier schon okay im Forum.

Aber die wahl eines besseren Topics, wär nett

[ Dieser Beitrag wurde am 02.06.2003 um 20:41 Uhr von kingruedi editiert. ]

Heute_heiße_ich_smax

Da denkt man schon ein wenig Ahnung von Mathematik zu haben und dann kommt ihr hier mit sowas