multiplikatives Inverses < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechne das Inverse von [17]_1000 im Ring [mm] \IZ/100. [/mm] |
[mm] (1000,17)_\IZ=(17,15)_\IZ=(15,2)_\IZ=(2,1)_\IZ=(1,0)_\IZ=(1)_\IZ
[/mm]
So, und jetzt muss ich ja rückwärts einsetzen, aber das funktioniert irgendwie nicht ganz. Ich habe mich dabei an folgendem beispiel orientiert:
[mm] (99,31)_\IZ=(31,6)_\IZ=(6,1)_\IZ=(1,0)_\IZ=(1)_\IZ
[/mm]
1=31-5*6=31-5*(99-3*31)=(-5)*99+16*31 und daraus folgt 1=31*16 mod 99, also [mm] [31]^{-1}=[16]
[/mm]
Wie muss ich hier rückwärts einsetzen?
Mathegirl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:18 So 27.11.2011 | | Autor: | hippias |
> Berechne das Inverse von [17]_1000 im Ring [mm]\IZ/100.[/mm]
>
> [mm](1000,17)_\IZ=(17,15)_\IZ=(15,2)_\IZ=(2,1)_\IZ=(1,0)_\IZ=(1)_\IZ[/mm]
>
> So, und jetzt muss ich ja rückwärts einsetzen, aber das
> funktioniert irgendwie nicht ganz. Ich habe mich dabei an
> folgendem beispiel orientiert:
>
> [mm](99,31)_\IZ=(31,6)_\IZ=(6,1)_\IZ=(1,0)_\IZ=(1)_\IZ[/mm]
> 1=31-5*6=31-5*(99-3*31)=(-5)*99+16*31 und daraus folgt
> 1=31*16 mod 99, also [mm][31]^{-1}=[16][/mm]
>
> Wie muss ich hier rückwärts einsetzen?
>
> Mathegirl
Wenn Du damit Schwierigkeiten hast, dann vermute ich, dass Dir nicht klar ist, woher die Zahlen aus Deinem Beispiel stammen: Sie kommen aus dem Euklidischen Algorithmus:
$99= 3*31+6$ und
$31= 5*6+1$. Folglich ist $1= 31-5*6=...$ usw. wie oben. Fuehre also wiederholt Divison mit Rest durch, bis Du auf den ggT kommst, dann rueckwaerts einsetzen.
|
|
|
| |
|
aber ich habe doch in meinem Beispiel schon g:=ggT(1000,17)= 1 berechnet!!!
Nur das rückwärts einsetzen scheitert!
1=17-15*?
Mathegirl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 So 27.11.2011 | | Autor: | hippias |
Zeige doch einmal die Ergebnisse der wiederholten Division mit Rest.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:05 So 27.11.2011 | | Autor: | Mathegirl |
weiter kann ich doch gar nicht dividieren als ich in meinem ersten beitrag gezeigt habe!! ich hab doch 1 raus, weiter dividieren geht ja nicht mehr!
Mathegirl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:18 So 27.11.2011 | | Autor: | hippias |
Fuehre bitte folgende Division mit Rest durch - d.h. ermittle die [mm] q_{i}$ [/mm] und [mm] $r_{i}$- [/mm] solange, bis Du auf den Rest $0$ kommst:
$1000= [mm] q_{1}\cdot [/mm] 17+ [mm] r_{1}$, [/mm] $17= [mm] q_{2}r_{1}+ r_{2}$, $r_{1}= q_{3}r_{2}+ r_{3}$...; [/mm] wenn Du das fuer mich erledigt hast, werden wir gemeinsam das Inverse bestimmen. Und vorsicht: Nicht die $q's$ und $r's$ durcheinanderbringen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:26 So 27.11.2011 | | Autor: | leduart |
Hallo mathegirl
was du in deiner kurzschreibweise
$ [mm] (1000,17)_\IZ=(17,15)_\IZ=(15,2)_\IZ=(2,1)_\IZ=(1,0)_\IZ=(1)_\IZ [/mm] $
noch sehen kannst, entgeht mir. z.B was die
[mm] (17,15)_\IZ [/mm] ist-
bie mir läuft das so
1000=58*17+14
17=1*14+3
14=4*3+2
3=1*2+1
jetzt von hinten:
1=3-2
2=14-4*3
eingesetzt
1=3-(14-4*3)=5*3-14
3=17-14
eingesetzt
1=5*(17-14)-14=5*17-6*14
14=1000-58*17
eingesetzt
1=5*17-6*(1000-58*17)=-6*1000+353*17
Wie du das mit deiner Kurzschreibweise hinkriegen willst entgeht mir, du hast darin ja nicht mehr alle Informationen.
Aber: Wieder hast du uns nicht gesagt, was du gemacht hast, nur dass es nicht klappt.
Bitte rechne doch vor!
Gruss leduart
|
|
|
| |
|
Sorry, mein Fehler, das habe ich völlig falsch verstanden!
d.h. [-6]ist das Inverse?
Ich schreibe das gerade nochmal vernünftig auf um das rückwärtseinsetzen anchzuvollziehen.
mathegirl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:08 So 27.11.2011 | | Autor: | leduart |
Hallo
Denk noch mal nach! -6 ist sicher nicht das inverse!
du suchst doch die zahl, so dass 17*z=k*1000+1 ist also
z=1 mod 1000
Gruss leduart
|
|
|
|
