multiplikativ inverses Element < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:57 Di 26.07.2011 | | Autor: | taiBsu |
| Aufgabe | Ermitteln Sie das multiplikativ Inverse von m in [mm] \IZ_n [/mm] für:
(i) m = 21, n = 101. |
Also, damit überhaupt ein multiplikativ Inverses von m besteht, muss ja der ggT von m und n 1 sein, richtig? Also habe ich gerechnet:
[mm] \IZ_101
[/mm]
ggT(21, 101) = 1
101 = 4 * 21 + 17
21 = 1 * 17 + 4
17 = 4 * 4 + 1
Rueckrechnung:
1 = 17 - 4 * 4
= 17 - 4 * (21 - 1 * 17)
= 5 * 17 - 4 * 21
= 5 * (101 - 4 * 21) - 4 * 21
= 5 * 101 - 24 * 21
= (-24) * 21 + 5 * 101 (fuer die Form 1 = [mm] \alpha [/mm] * a + [mm] \beta [/mm] * p)
Mein Script / Professor sagt mir, dass die Zahl [mm] b:=\alpha [/mm] mod p dann das multiplikativ Inverse sei, was ja dann in diesem Fall bei der Form 1 = [mm] \alpha [/mm] * a + [mm] \beta [/mm] * p die Zahl -24 wäre?
Wenn ich jetzt aber -24 * 21 mod 101 rechne, komm ich nicht auf 1, sondern auf -100. Wer kann mir helfen?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
www.matheboard.de
Bekomme da aber da irgendwie nie eine richtig eine Antwort...
|
|
| |
|
Hallo taiBsu,
> Ermitteln Sie das multiplikativ Inverse von m in [mm]\IZ_n[/mm]
> für:
> (i) m = 21, n = 101.
>
> Also, damit überhaupt ein multiplikativ Inverses von m
> besteht, muss ja der ggT von m und n 1 sein, richtig? Also
> habe ich gerechnet:
>
> [mm]\IZ_101[/mm]
> ggT(21, 101) = 1 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> 101 = 4 * 21 + 17
> 21 = 1 * 17 + 4
> 17 = 4 * 4 + 1
>
> Rueckrechnung:
>
> 1 = 17 - 4 * 4
> = 17 - 4 * (21 - 1 * 17)
> = 5 * 17 - 4 * 21
> = 5 * (101 - 4 * 21) - 4 * 21
> = 5 * 101 - 24 * 21
> = (-24) * 21 + 5 * 101 (fuer die Form 1 = [mm]\alpha[/mm] * a +
> [mm]\beta[/mm] * p)
Du suchst [mm]x\in\IZ_{101}[/mm] mit [mm]21\cdot{}x \ \equiv \ 1 \ \operatorname{mod}(101)[/mm]
Mit deiner errechneten LK der 1 also
[mm]21\cdot{}x \ \equiv \ 5\cdot{}101-24\cdot{}21 \ \equiv \ 0-24\cdot{}21 \ = \ -24\cdot{}21 \ \operatorname{mod}(101)[/mm]
Also [mm]21\cdot{}x \ \equiv \ -24\cdot{}21 \ \operatorname{mod}(101)[/mm]
Nun kürzen:
Also [mm]x \ \equiv \ -24 \ \equiv \ 77 \ \operatorname{mod}(101)[/mm]
Also ist [mm]77[/mm] das mult. Inverse von [mm]21[/mm] in [mm]\IZ_{101}[/mm]
Rechne mal die Probe, ob tatsächlich [mm]21\cdot{}77 \ \equiv \ 1 \ \operatorname{mod}(101)[/mm] gilt, ob also [mm]21\cdot{}77[/mm] bei Division durch [mm]101[/mm] den Rest [mm]1[/mm] lässt ...
>
>
> Mein Script / Professor sagt mir, dass die Zahl [mm]b:=\alpha[/mm]
> mod p dann das multiplikativ Inverse sei, was ja dann in
> diesem Fall bei der Form 1 = [mm]\alpha[/mm] * a + [mm]\beta[/mm] * p die
> Zahl -24 wäre?
> Wenn ich jetzt aber -24 * 21 mod 101 rechne,
> komm ich nicht auf 1, sondern auf -100. Wer kann mir helfen?
Was modulo 101 dasselbe wie 1 ist (-100+101=1)
Du musst hier: [mm] 21x\equiv -24\cdot{}21 [/mm] \ [mm] \operatorname{mod}(101)$ [/mm] kürzen:
Beachte [mm]ac\equiv bc \ \operatorname{mod}(101) \ \Rightarrow a \ \equiv \ b \ \operatorname{mod}\left(\frac{101}{\operatorname{ggT}(c,101)}\right)[/mm]
>
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> www.matheboard.de
>
> Bekomme da aber da irgendwie nie eine richtig eine
> Antwort...
>
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:21 Di 26.07.2011 | | Autor: | taiBsu |
Tatsächlich komme ich beim Rechnen von 77 * 21 mod 101 auf 1, ich verstehe nur leider gerade nicht, wie man von -24 mod 101 auf 77 kommt? Wenn ich wie beschrieben kürze mit [mm] \bruch{101}{ggT(c,101)} [/mm] , komme ich doch, wenn ich c einsetze, auf den ggT von 21 und 101, welcher dann wiederum 1 ist und dann bleibe ich doch wieder bei mod 101?
|
|
|
| |
|
Hallo nochmal,
>
> Tatsächlich komme ich beim Rechnen von 77 * 21 mod 101 auf
> 1, ich verstehe nur leider gerade nicht, wie man von -24
> mod 101 auf 77 kommt?
Na, [mm] $-24+1\cdot{}101=77$
[/mm]
Welche Elemente liegen denn in der Restklasse $[-24]$
Doch alle [mm] $-24+k\cdot{}101$ [/mm] mit [mm] $k\in\IZ$
[/mm]
> Wenn ich wie beschrieben kürze mit
> [mm]\bruch{101}{ggT(c,101)}[/mm] , komme ich doch, wenn ich c
> einsetze, auf den ggT von 21 und 101, welcher dann wiederum
> 1 ist und dann bleibe ich doch wieder bei mod 101?
Ja, hier geht das Kürzen gefahrlos
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:47 Di 26.07.2011 | | Autor: | taiBsu |
Mache ich das denn einfach bei jeder Berechnung des multiplikativ Inversen so? Also [mm] \alpha [/mm] + 1 * p = m ?
|
|
|
| |
|
Hallo taiBsu,
>
>
> Mache ich das denn einfach bei jeder Berechnung des
> multiplikativ Inversen so? Also [mm]\alpha[/mm] + 1 * p = m ?
>
Das machst Du nur, wenn das multipikativ Inverse [mm]\alpha[/mm] negativ ist,
und Du ein positives multiplikativ Inverses erhalten willst.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:56 Di 26.07.2011 | | Autor: | taiBsu |
Super!!! Danke euch allen! Das hat mir wahnsinnig geholfen. Wenn die Zahl also positiv wäre, könnte ich sozusagen diesen Schritt außer Acht lassen, ja?
|
|
|
| |
|
Hallo nochmal,
> Super!!! Danke euch allen! Das hat mir wahnsinnig geholfen.
> Wenn die Zahl also positiv wäre, könnte ich sozusagen
> diesen Schritt außer Acht lassen, ja?
Es ist ja mit dem Inversen auch immer jedes ganzzahlige Vielfache ein Inverses.
Also -24 oder 77 oder 77+101=178 oder [mm] $-24-3\cdot{}101$ [/mm] usw.
Meist gibt man den kleinsten positiven Vertreter an, hier die 77
Aber -24 ist als Lösung genauso richtig
Gruß
schachuzipus
>
|
|
|
| |
|
Hallo nochmal,
PS:
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> www.matheboard.de
>
> Bekomme da aber da irgendwie nie eine richtig eine
> Antwort...
Bitte stets den direkten Link zu deinem post einstellen, "matheboard.de" ist doch viel zu allgemein ...
Danke
Gruß
schachuzipus
|
|
|
|
