ggT < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Finden Sie im Körper F241 ein x mit 37 * x = 1 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Müsste man hier nicht den ggT finden? Jedoch weiß ich nicht, wie man das mit der obigen Gleichung kombinieren kann.
241:36= 6 Rest 19
(...)
18:1= 18 Rest 0. Also ist ggT (18,1)= ggT (1,0)
Also ist 1 der ggT. Jedoch ist die Frage damit nicht beantwortet.
Würde mich über eure Hilfe freuen.
|
|
| |
|
> Finden Sie im Körper F241 ein x mit 37 * x = 1
> Müsste man hier nicht den ggT finden? Jedoch weiß ich
> nicht, wie man das mit der obigen Gleichung kombinieren
> kann.
Hallo,
da 241 eine Primzahl ist, gibt es genau ein [mm] x\in\{1,2,3,\,...\,,240\} [/mm]
mit der gewünschten Eigenschaft, nämlich das multiplika-
tive Inverse von 37.
Wenn du es nicht einfach durch Probieren suchen willst,
kannst du dazu den erweiterten euklidischen Algorithmus
verwenden.
LG Al-Chw.
|
|
|
| |
|
Wenn ich das mit dem erweiterten euklidischen Algorithmus mache kommt folgendes raus:
1= 19-1*18
= 19-1*(37-1*19)= 2*19-1*37
(...)
=2*241-13*37=1
= 37^-1 mod 241= 27
Ist 27 dann mein Ergebnis?
|
|
|
| |
|
Hallo xxela89xx,
hast du kein "Hallo" oder "Tschüß", kein freundliches Wort für die potentiellen Antwortgeber übrig?
> Wenn ich das mit dem erweiterten euklidischen Algorithmus
> mache kommt folgendes raus:
> 1= 19-1*18
> = 19-1*(37-1*19)= 2*19-1*37
> (...)
> =2*241-13*37=1 ![[ok]](/images/smileys/ok.gif "[ok]")
> = 37^-1 mod 241= 27
> Ist 27 dann mein Ergebnis?
Mache doch die Probe: Lässt [mm]27\cdot{}37[/mm] bei Division durch [mm]241[/mm] den Rest 1?
Zu lösen ist doch nun [mm]37\cdot{}x \ \equiv \ 1 \ \operatorname{mod}(241)[/mm]
Ersetzen wir die 1 entsprechend dem, was der erweiterte euklid. Algorithmus geliefert hat:
[mm]37\cdot{}x \ \equiv \ 2\cdot{}241-13\cdot{}37 \ \equiv \ -13\cdot{}37 \ \operatorname{mod}(241)[/mm]
Mithin nach Kürzen von [mm]37[/mm] - wieso ist das erlaubt? - :
[mm]x \ \equiv \ -13 \ \operatorname{mod}(241)[/mm]
Und [mm]-13 \ \equiv \ -13+241=228 \ \operatorname{mod}(241)[/mm]
Damit sollte (modulo Rechenfehler meinerseits) doch [mm]228[/mm] multiplikativ invers zu [mm]37[/mm] in [mm]F_{241}[/mm] sein:
Probe ....
Gruß
schachuzipus
|
|
|
| |
|
Hey, stimmt ich habs gar nicht bemerkt, weil ich zu sehr mit der Aufgabe beschäftigt war :)
Also, 27*37 lässt bei der Division mit 241 nicht den Rest 1, nur habe ich nicht ganz verstanden wieso das so sein muss, dann muss ja 228 auch den Rest 1 lassen oder bin ich jetzt auf einem ganz anderen Weg?
PS: Vielen Dank für die Antworten...
Liebe Grüße
|
|
|
| |
|
moin,
> Hey, stimmt ich habs gar nicht bemerkt, weil ich zu sehr
> mit der Aufgabe beschäftigt war :)
>
> Also, 27*37 lässt bei der Division mit 241 nicht den Rest
> 1, nur habe ich nicht ganz verstanden wieso das so sein
> muss,
Wieso was genau wie sein muss?
Es muss so sein, dass $27*37$ nicht den Rest 1 hat, weil bloßes Ausrechnen dies liefert.
Oder was meinst du?
> dann muss ja 228 auch den Rest 1 lassen oder bin ich
> jetzt auf einem ganz anderen Weg?
Hmm, 228 lässt ganz bestimmt nicht den Rest 1, denn da $228 < 241$ lässt 228 den Rest 228.
Es hat allerdings $228*37$ bei Division durch 241 den Rest 1.
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:00 Di 20.03.2012 | | Autor: | xxela89xx |
Hey,
genau das meinte ich. Jetzt habe ich es verstanden.
Vielen Dank!
Liebe Grüße
|
|
|
|
