Modulorechnungsproblem < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | 35 [mm] \* [/mm] x [mm] \equiv [/mm] 1 mod 3551 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Eine sehr geile Aufgabe an der meine Gruppe ( inklusive mir ) gerade hängen bleibt, hatt vielleicht jemand einen Ansporn wie man diese Aufgabe angehen sollte... ein paar Ansätze hatten wir schon, die leider aber ins "Nichts" liefen.
Gruß, das Eich-Ötti-Schema
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:59 Mi 14.05.2008 | | Autor: | statler |
> 35 [mm]\*[/mm] x [mm]\equiv[/mm] 1 mod 3551
> Eine sehr geile Aufgabe an der meine Gruppe ( inklusive
> mir ) gerade hängen bleibt, hatt vielleicht jemand einen
> Ansporn wie man diese Aufgabe angehen sollte... ein paar
> Ansätze hatten wir schon, die leider aber ins "Nichts"
> liefen.
Hi,
der ökonomischste Weg zu einer Lösung ist die wiederholte Anwendung des euklidschen Algorithmus. Also: 3551 durch 35 teilen mit Rest, dann 35 durch diesen Rest mit neuem kleineren Rest, dann alten Rest durch neuen Rest, was hoffentlich Rest 1 ergibt. Mit Hilfe dieser Rechnung kannn man jetzt rückwärts 1 als Linearkombination von 3551 und 35 darstellen, womit man fertig ist.
(Kontrolle: x = 2435 ist eine Lösung.)
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Aufgabe | Euklidscher Algor.
3551 : 35 = 101 + R16
35 : 16 = 2 + R3
3 : 1 = 3
Weiter gehts
16 = 3551 - 101 * 35
3 = 35 - 16 * 2
1 = 16 - 5 * 3
Wenn wir jetzt einsetzten erhalten wir am Schluss:
1 = 11 * 3551 - 35 * 1116 |
Ah ok, jetzt sind wir schon einen Schritt weiter... der euklidsche Algor. ist uns bekannt ( wir wären trotzdem nicht auf die Idee gekommen ihn anzuwenden ;D )... also danke erst einmal dafür. Wir haben die obige Lösung und wenn wir jetzt 1116 nutzen haben wir einen Rest von 3550 ( also 3551 - 1 ). Aber wir wissen jetzt nicht wie wir weiter vorgehen müssen, vor allem um auf Ihr Ergebnis zu kommen.
Ich danke Ihnen vorab mal für Ihren Lösungansatz ;D
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:47 Mi 14.05.2008 | | Autor: | statler |
Hi!
Vorab: Wir sind hier per 'du'.
> Euklidscher Algor.
> 3551 : 35 = 101 + R16
> 35 : 16 = 2 + R3
> 3 : 1 = 3
> Weiter gehts
> 16 = 3551 - 101 * 35
> 3 = 35 - 16 * 2
> 1 = 16 - 5 * 3
> Wenn wir jetzt einsetzten erhalten wir am Schluss:
> 1 = 11 * 3551 - 35 * 1116
> Ah ok, jetzt sind wir schon einen Schritt weiter... der
> euklidsche Algor. ist uns bekannt ( wir wären trotzdem
> nicht auf die Idee gekommen ihn anzuwenden ;D )... also
> danke erst einmal dafür. Wir haben die obige Lösung und
> wenn wir jetzt 1116 nutzen haben wir einen Rest von 3550 (
> also 3551 - 1 ). Aber wir wissen jetzt nicht wie wir weiter
> vorgehen müssen, vor allem um auf Ihr Ergebnis zu kommen.
Mein Ergebnis habe ich absichtlich etwas verfälscht 
Wenn wir die Gl.
1 = 11 * 3551 - 35 * 1116
mal modulo 3551 betrachten und etwas umbauen, steht da doch
1 [mm] \equiv [/mm] 35*(-1116) mod 3551
Die gefundene Lösung ist also x = -1116.
Aber es gilt auch
0 = (-35)*3551 + 3551*35
und das kannn ich beliebig oft zu meiner Gl. addieren oder von ihr abziehen. Damit kriege ich alle weiteren Lösungen
Gruß
Dieter
|
|
|
|
