Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:35 Mo 09.02.2009 | | Autor: | Pille456 |
Hi!
Ich rechne momentan noch ein wenig mit dem chinesischen Restsatz um ihn komplett zu verstehen. Dabei kam ich auf einen interessanten Fall, den ich bisher so nicht hatte:
Wie berechne ich folgendes Gleichungssystem?:
(1) 17 x = 1 mod 73
(2) 15 x = 4 mod 49
Die einzelnen Gleichungen kann ich recht problemlos mit dem euklidischen Algo. berechnen. Für (1) sieht das dann so aus: 73*s+17*t = 1 => t = -30 = 43 (in mod 73) was schon die Lösung wäre. Nur wie mache ich das in dieser Abhängigkeit?
Passend dazu wäre auch interessant wie man solche Gleichungen lösen könnte:
17x + 2 = 1 mod 73 oder 17x+2x²+3 = 1 mod 73
Oder zumindest erkennen kann, ob diese Gleichungen mit dem chin. Restsatz lösbar sind. Also allgemein kann ich den chin. Restsatz ja nur anwenden, wenn die Modulu (..?) teilerfremd, also einen ggT = 1 haben.
|
|
| |
|
Hallo Pille456,
so ganz verstehe ich die Zielrichtung Deiner Frage nicht.
> Wie berechne ich folgendes Gleichungssystem?:
> (1) 17 x = 1 mod 73
> (2) 15 x = 4 mod 49
> Die einzelnen Gleichungen kann ich recht problemlos mit
> dem euklidischen Algo. berechnen.
Eben. Du hast ja schon ermittelt, dass adäquat ist:
(1) [mm] x\equiv43\mod{73}
[/mm]
Ebenso ermittelst Du die Äquivalenz
(2) [mm] x\equiv46\mod{49}
[/mm]
...und ab da geht es mit dem chin. Restsatz weiter.
> Passend dazu wäre auch interessant wie man solche
> Gleichungen lösen könnte:
> 17x + 2 = 1 mod 73
wie oben: [mm] x\equiv30\mod{73}
[/mm]
> oder 17x+2x²+3=1 mod 73
Diese Gleichung ist nicht lösbar.
> Oder zumindest erkennen kann, ob diese Gleichungen mit dem
> chin. Restsatz lösbar sind.
Das ist allerdings nicht mit dem chin. Restsatz zu zeigen!
> Also allgemein kann ich den
> chin. Restsatz ja nur anwenden, wenn die Modulu (..?)
> teilerfremd, also einen ggT = 1 haben.
Üblicherweise "Moduln" (Betonung u), theoretisch möglich, aber unüblich: "Moduli" (Betonung o).
Ansonsten stimmt das nicht ganz. Auch im Fall nicht teilerfremder Moduln gibt es unter bestimmten Bedingungen Lösungen. Lies mal diesen ![[]](/images/popup.gif) Abschnitt in der Wikipedia.
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:46 Mo 09.02.2009 | | Autor: | Pille456 |
Danke schonmal!
Könntest du die Rechnung für
$ [mm] x\equiv30\mod{73} [/mm] $
bzw. $ [mm] x\equiv46\mod{49} [/mm] $ mal posten? Sehe gerade nicht wie du da gerechnet hast bzw. wie man so umformen kann.
Das es eine Lösung bei ggT [mm] \not= [/mm] 1 geben kann, weiss ich, aber ist irrelevant, wenn die Aufgabenstellung heißt "Finden Sie mit Hilfe des chinesischen Restsatzes..." :)
|
|
|
| |
|
Hallo pille,
das hast Du doch selbst schon gerechnet - erweiterter euklidischer Algorithmus. Du suchst das [mm] \mod{49} [/mm] multiplikativ Inverse zu 15. Geht genauso wie vorher [mm] \mod{73}. [/mm] (Zu 14 hättest Du kein Inverses gefunden!)
Das Inverse zu 15 ist 36. Dann folgt:
[mm] 15x\equiv4\mod{49}\ \Rightarrow\ 36*15x\equiv x\equiv36*4\equiv144\equiv46\mod{49}
[/mm]
Übrigens kannst Du nicht einfach sagen, dass es keine Lösungen mit dem chin. Restsatz gibt, bloß weil der paarweise ggT der Moduln nicht immer 1 ist; die genau definierte Ausnahme habe ich Dir doch verlinkt.
Gruß,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mo 09.02.2009 | | Autor: | Pille456 |
Ahja okay danke! Die Inversenrechnung war mir nicht ganz klar. Ich habe das recht intuitiv gerechnet bzw. gar nicht so realisiert, da wir in der Vorlesung nur Beispiele mit ax = 1 mod m hatten.
Aber habs nun verstanden, danke!!!
|
|
|
|
