Bestimmten Modulo ausrechnen

Neue Frage »

Kaji_Lim Auf diesen Beitrag antworten »
Bestimmten Modulo ausrechnen
Meine Frage:
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 smile


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? smile

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 smile
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.
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?
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: .
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 Big Laugh
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.
 
 
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 Augenzwinkern ).
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.
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
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?
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?
lgrizu Auf diesen Beitrag antworten »

Genau, du gehst also "Rückwärts" um den ggT(a,b) als Linearkombination von a und b darzustellen..
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 smile

1 = 5 - 2 ( 17 - 15)
1 = 5 - 4
1 = 1

Was würde ich dann an dieser Stelle tun?
lgrizu Auf diesen Beitrag antworten »

Zitat:
Original von lgrizu
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?


Hier steht doch alles....
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »