Bestimmten Modulo ausrechnen |
02.01.2011, 19:27 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
Bestimmten Modulo ausrechnen Hallo, ich sitze gerade an einer Aufgabe bei der ich ein yn ausrechnen soll, das mit einer Zahl Multipliziert modulo y = 1 ergibt. Ein Beispiel wäre: y* 2 mod 19 = 1 y ist in dem Fall 10. Das kann ich ja noch im Kopf rechnen Aber bei Fällen wie y* 17 mod 18 = 1 kommt man so nicht weiter. y war 17, oder -1 .... allerdings hab ich das mit meinem Wissen nur mit einem selbstgeschriebenen Programm ausrechnen können. Ich habe auch noch den Fall y*2 mod 17 =1 usw usw usw.... Gibt es hier irgend eine einfachere Methode dieses Problem im Kopf oder auf Papier zu lösen, ohne dass mir vor lauter Probieren Zeit und Papier flöten gehen? mfg Kaji Lim Meine Ideen: Bisher war ich nur soweit jeweils ein vielfaches auszurechnen und 1 zu addieren. Allerdings war ich wenig erfolgreich mit dem GGT, außerdem such ich nicht den GGT sondern den Kleinsten teiler |
||||
02.01.2011, 19:59 | lgrizu | Auf diesen Beitrag antworten » | ||
RE: Bestimmten Modulo ausrechnen Zunächst mal ist richtig: , wenn du nur eine beliebige Zahl benötigst und nicht die kleinstmögliche oder so, dann kann man sich überlegen, wie y aussehen muß, in diesem Fall ist zum Beispiel also . Aus 18*17-17 resultiert dann (18-1)*17=17*17. Analog kann man sich das auch für y*2 mod 17 überlegen. |
||||
02.01.2011, 20:12 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
hallo, was ich meinte war, gibt es einen allgemein gültigen Rechenweg für das modulo Problem? Oder Muss ich jeden Fall individuell behandeln? |
||||
02.01.2011, 20:16 | lgrizu | Auf diesen Beitrag antworten » | ||
Es gibt gültige Rechenregeln, so ist zum Beispiel , also . Wenn man nun eine Lösung haben möchte muss man sich das genau so überlegen, als wenn man eine Lösung in den reellen Zahlen für y*2=1 haben möchte, Multiplikationsregeln. Bei Primzahlen kann man sich auch überlegen, dass jeder Restklassenring ein Körper ist und zu jedem Element also ein Inverses existiert, wenn man dann die Gleichung lösen möchte kann man den kleinen Satz von Fermat nutzen, der da sagt: . |
||||
02.01.2011, 21:00 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
Hi, Also ein spezielles Ergebnis brauche ich nicht. je kleiner und einfacher das Resultat zu errechnen ist, desto besser. Meine Idee war das kgV zu rechnen und 1 zu addieren, funktioniert aber auch nicht immer scheint mir. und wie helfen mir diese Regeln im Bezug auf Aufgaben wie: y * 5 mod 17 = 1 ? Ich muss scheinbar für jede Aufgabe einen neuen Weg finden, gibt es keinen allgemeinen Weg? Ich ersticke hier gerade an meinen ganzen Schmierblättern |
||||
02.01.2011, 21:04 | lgrizu | Auf diesen Beitrag antworten » | ||
Da 17 eine Primzahl ist kann man den kleinen Fermat anwenden: , Nach Fermat ist , also . Damit wäre . Wie gesagt, bei Primzahlen hilft der kleine Fermat wenn es nur um irgendeine Lösung geht. |
||||
Anzeige | ||||
|
||||
02.01.2011, 21:14 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
Die Zahl ist leider etwas zu gross, ich muss später mit den Ergebnissen noch multiplizieren. Wie sieht es mit dem euklidischen Algorithmus aus? Hilft der mir weiter? (Bisher hat ers noch nicht ). |
||||
02.01.2011, 21:22 | lgrizu | Auf diesen Beitrag antworten » | ||
Der Euklidsche Algorithmus sollte dir eigentlich weiter helfen (sorry, an die Option hatte ich gar nicht gedacht): Es ist ggT(5,17)=1, Wenn man nun den ggT nach Bezout darstellt erhält man: 1=7*5-2*17, und es ist 2*17 mod 17=0, also ist 7*5 mod 17=1 mod 17. Ich habe jetzt Gleichheit anstelle von Äquivalenz genutzt, ist hoffentlich nicht so schlimm. |
||||
02.01.2011, 21:40 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
Hi, okay ich kann das schonmal ein wenig besser nachvollziehen. Aber wie genau komme ich auf die 7*5-2*17 ?Ich hab da ja hunderte Möglichkeiten, von denen nur ein paar stimmen. Ausprobieren? Erfahrung? Gibts da irgend einen weg, schnell auf das Ergebnis zu kommen? Gruß Kaji |
||||
02.01.2011, 21:46 | lgrizu | Auf diesen Beitrag antworten » | ||
Da stellt man den ggT mit dem Lemma von Bezout dar, ich mach dir das mal vor, zuerst euklidscher Algorithmus: 17=3*5+2 5=2*2+1 Nun wendet man das ganze "Rückwärts" an: aus 5=2*2+1 folgt (i) 1=5-2*2 und aus 17=3*5+2 folgt (ii) 2=17-3*5 nun setzen wir (ii) in (i) ein und erhalten: 1=5-2*(17-3*5)=7*5-2*17, so weit klar? |
||||
02.01.2011, 22:00 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
(i) = 5 - (2*2). eingesezt 1 = 5-2*(17-3*5) und 17-3*5 = 2, daher kann ich es in (i) einsetzen? |
||||
02.01.2011, 22:02 | lgrizu | Auf diesen Beitrag antworten » | ||
Genau, du gehst also "Rückwärts" um den ggT(a,b) als Linearkombination von a und b darzustellen.. |
||||
02.01.2011, 22:07 | Kaji_Lim | Auf diesen Beitrag antworten » | ||
Hi, was ich noch nicht ganz nachvollziehe kann, ist folgende Auflösung: 7*5-2*17 Woher kommt die 7? Ich hätte an dieser Stelle blind aufgelöst und gesagt 1 = 5 - 2 ( 17 - 15) 1 = 5 - 4 1 = 1 Was würde ich dann an dieser Stelle tun? |
||||
02.01.2011, 22:10 | lgrizu | Auf diesen Beitrag antworten » | ||
Hier steht doch alles.... |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|