Restklassenring < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechnen Sie [mm] 23^{-1} [/mm] in [mm] \IZ_{}/271\IZ_{}. [/mm] |
Hi...
Das Thema: "Rechnen mit Kongruenzen" habe ich erst seit kurzem kennengelernt, nun muss ich diese Aufgabe lösen, aber ich weis nicht wie...
Ich habe schon das ganze Internet abgesucht und keine brauchbaren Ideen finden können.... Ich bin am verzweifeln...
Kann mir vielleicht jemand helfen und mir zeigen, wie man so etwas berechnet?
Bitte, Bitte...
|
|
| |
|
Hallo franzigoth1,
> Berechnen Sie [mm]23^{-1}[/mm] in [mm]\IZ_{}/271\IZ_{}.[/mm]
> Hi...
>
> Das Thema: "Rechnen mit Kongruenzen" habe ich erst seit
> kurzem kennengelernt, nun muss ich diese Aufgabe lösen,
> aber ich weis nicht wie...
> Ich habe schon das ganze Internet abgesucht und keine
> brauchbaren Ideen finden können.... Ich bin am
> verzweifeln...
>
> Kann mir vielleicht jemand helfen und mir zeigen, wie man
> so etwas berechnet?
>
> Bitte, Bitte...
Berechne zunächst den größten gemeinsamen Teiler von 23 und 271.
[mm]271 = a_{1}*23+r_{1}[/mm]
[mm] 23 = a_{2}*r_{1} + r_{2}[/mm]
[mm] r_{1}=a_{3}*r_{2}+r_{3}[/mm]
[mm] \dots [/mm]
[mm] r_{n-3}=a_{n-1}*r_{n-2}+r_{n-1}[/mm]
[mm] r_{n-2}=a_{n}*r_{n-1}+r_{n}[/mm]
Der letzte von 0 verschieden Rest, ist nun der ggT dieser beiden Zahlen.
Sei [mm]r_{n-1}[/mm] dieser von 0 verschiedene Rest.
Der ggt läßt sich auch als Vielfachsumme der beiden Zahlen 23 und 271 scheiben.
Um den ggT als Vielfachsumme darzustellen, gehe wie folgt vor:
[mm]r_{n-1}=1*r_{n-3}-a_{n-1}*r_{n-2}[/mm]
Ersetze dann [mm]r_{n-2}=1*r_{n-4}-a_{n-2}*r_{n-3}[/mm]
Dann steht da:
[mm]r_{n-1}=1*r_{n-3}-a_{n-1}*r_{n-2}[/mm]
[mm]=1*r_{n-3}-a_{n-1}*\left(1*r_{n-4}-a_{n-2}*r_{n-3}\right)[/mm]
[mm]=\left(1+a_{n-1}*a_{n-2}\right)*r_{n-3}-a_{n-1}*r_{n-4}[/mm]
Als nächstes wird [mm]r_{n-3}[/mm] ersetzt:
[mm]r_{n-3}=1*r_{n-5}-a_{n-3}*r_{n-4}[/mm]
Das Spielchen geht so weiter bis Du bei den Zahlen 23 und 271 angekommen bist.
Jetzt gilt: ggt(23,271)=a*23+b*271[/mm]
Betrachtest Du das modulo 271, so sollte a das Inverse zu 23 modulo 271 sein.
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:15 Mi 07.05.2008 | | Autor: | wauwau |
Ich glaube franzigoth1 hat die ursprüngliche Aufgabe nicht verstanden:
[mm] 23^{-1} [/mm] in [mm] \IZ/273\IZ [/mm] zu lösen
finde ein a, sodass es ein b gibt, damit
[mm]23a=273b+1[/mm] mit a,b [mm] \in \IN
[/mm]
|
|
|
|
