multiplikatives Inverses < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Finde ein multiplikatives Inverses zu [2010] in [mm] \IZ [/mm] /3967 [mm] \IZ! [/mm] |
okay...also muss ich doch eigentlich folgendermaßen beginnen....ich nutze den erweiterten euklidischen algorithmus..
m*m´+n*n´=1
[mm] m*m´-1=n*n´\equiv [/mm] 0
mod n [mm] \Rightarrow m*m´\equiv [/mm] 1
aber ich weiß nicht wie man das nun genau berechnet!
Bitte um Tipps!
Mathegirl
|
|
| |
|
Hallo Mathegirl,
> Finde ein multiplikatives Inverses zu [2010] in [mm]\IZ[/mm] /3967
> [mm]\IZ![/mm]
> okay...also muss ich doch eigentlich folgendermaßen
> beginnen....ich nutze den erweiterten euklidischen
> algorithmus..
>
> m*m´+n*n´=1
> [mm]m*m´-1=n*n´\equiv[/mm] 0
> mod n [mm]\Rightarrow m*m´\equiv[/mm] 1
>
>
> aber ich weiß nicht wie man das nun genau berechnet!
Siehe hier:
![[]](/images/popup.gif) Erweiterter euklidischer Algorithmus - Funktionsweise am Beispiel
>
> Bitte um Tipps!
>
> Mathegirl
Gruss
MathePower
|
|
|
| |
|
Die seite habe ich ja schon gesehen aber ich komme immer nicht so leicht darauf....
ja...damit habe ich herausbekommen, dass der ggT hierbei 1 sein muss.
Aber wie bestimme ich nun das multiplikative Inverse??
(Stimmt doch ggT ist 1 oder?)
Mathegirl
|
|
|
| |
|
Hallo Mathegirl,
> Die seite habe ich ja schon gesehen aber ich komme immer
> nicht so leicht darauf....
>
> ja...damit habe ich herausbekommen, dass der ggT hierbei 1
> sein muss.
Nein, du kannst den [mm]\ggT(a,b)[/mm] immer als [mm]x\cdot{}a+y\cdot{}b[/mm] darstellen (Lemma von Bézout)
> Aber wie bestimme ich nun das multiplikative Inverse??
>
> (Stimmt doch ggT ist 1 oder?)
Ja, hier ist der [mm]\ggT(2010,3967)=1[/mm]
Wende den euklidischen Algorithmus an, um den [mm]\ggT[/mm] zu bestimmen, setze rückwärts ein, dann bekommst du die Darstellung [mm]\ggT(3097,2010)=1=x\cdot{}3097+y\cdot{}2010[/mm]
Damit ist zu lösen: (du suchst ja das multiplikativ Inverse zu $2010$ modulo $3967$)
[mm]2010\cdot{}z \ \equiv \ 1 \ \operatorname{mod}(3967)[/mm]
>
> Mathegirl
Gruß
schachuzipus
|
|
|
| |
|
und genau bei diesem rückwärtsrechnen habe ich Probleme!!
habe diese seite mal als "Muster" genommen
http://www.mathematik.uni-ulm.de/ReineMath/mitarbeiter/lubo/ws08/files/ADM/Probeklausur_Lsg.pdf
aber ich verstehe nicht so ganz wie ich das zurückführe und auf das multiplikative Inverse komme...also ich weiß auch nicht wie ich in diesem Beispiel auf die 14 komme! bzw wie ich orher auf die 11 komme..
Darin liegt ehr das Problem!
Mathegirl
|
|
|
| |
|
Hallo nochmal,
> und genau bei diesem rückwärtsrechnen habe ich Probleme!!
>
> habe diese seite mal als "Muster" genommen
>
> http://www.mathematik.uni-ulm.de/ReineMath/mitarbeiter/lubo/ws08/files/ADM/Probeklausur_Lsg.pdf
>
> aber ich verstehe nicht so ganz wie ich das zurückführe
> und auf das multiplikative Inverse komme...also ich weiß
> auch nicht wie ich in diesem Beispiel auf die 14 komme! bzw
> wie ich orher auf die 11 komme..
>
> Darin liegt ehr das Problem!
Na, das steht doch da ausführlichst vorgerechnet, was ist daran unverständlich??
Du beginnst in der letzten Zeile und stellst nach 1 (=ggT) um
[mm]1=33-1\cdot{}32[/mm]
Nun erstze die 32, schaue dazu in die Zeile darüber (nach [mm]32[/mm] umgestellt ist das: [mm]\red{32=65-1\cdot{}33}[/mm]
Also [mm]1=33-1\cdot{}\red{32}=33-1\cdot{}\red{(65-1\cdot{}33)}=33-1\cdot{}65+1\cdot{}33=2\cdot{}33-1\cdot{}65[/mm]
Nun sukzessive weiter, ersetze nun die 33 durch die Zeile darüber.
Das führe solange fort, bis du den ggT als LK der beiden beteiigten Zahlen dargestellt hast.
Damit gehst du in die Kongruenz (entsprechend deiner oben - s. andere Antwort) und rechnest das mit einfachster Kongruenzrechnung aus!
>
> Mathegirl
Gruß
schachuzipus
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:48 So 09.01.2011 | | Autor: | reverend |
Hallo Mathegirl,
am besten postest Du mal die ersten Zeilen Deiner eigenen Rechnung.
Dann kann man sehen, ob Du das Prinzip verstanden hast oder nicht.
So aufs Geratewohl kann doch niemand mehr sagen, höchstens noch einmal den Wikipedia-Artikel mit anderen Worten schreiben - oder Deine Aufgabe machen. Wir finden hier aber besser, wenn Du Deine Aufgabe machst, sie also rechnest, ggf. vorstellst und natürlich auch selbst tippst. Dann bekommst Du bestimmt passende Hilfe.
Im Moment wüsste ich z.B. nicht, was ich noch mehr sagen sollte als schon gesagt ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:27 So 09.01.2011 | | Autor: | SolRakt |
Hallo Mathegirl,
Du solltest bei sowas immer wie folgt vorgehen:
1.) Erweiterten Euklidischen Algorithmus anwenden. Wenn da ggt(a,b)=1 rauskommt, ist das Element in [mm] \IZ [/mm] / 3967 [mm] \IZ [/mm] multiplikativ invertierbar. Also das hast du anscheinend auch richtig bzw. ggT(3967,2010) = 1.
2.) Hier kommst du anscheinend nicht mehr weiter. Also:
Du kannst denn ggT auch umschreiben, wie folgt:
ggT(3967,2010) = 1 = 493 * 3967 - 973 * 2010
Aber du weißt schon, wie man darauf kommt?
Das inverse bestimmst du nun mit
[mm] 2010^{-1} [/mm] = (-973) mod 3967 = 2994
Einfach die Zahlen immer so einsetzen.
ich hoffe, dass ich mich jetzt nicht verrechnet habe xD Hast du denn noch Fragen dazu?
|
|
|
|
