multiplikativ Inverses < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:09 Di 23.02.2010 | | Autor: | yogi_inf |
| Aufgabe | Bestimmen Sie eine Zahl x element Z(154) mit
41 * mod 154 = 5. |
Ahoi,
Ich würde mich über Hilfe bei einem Ansatz sehr freuen.
Die Möglichkeit das ganze durch "probieren" auszuknobeln ist hier ein wenig kompliziert. Dabei kommt 79 raus. Jetzt ist die Frage, wie man es berechnen kann.
Die Bestimmung des multiplikativ Inversen hilft auch nicht weiter, da 154 dafür eine Primzahl sein müsste laut Skript.
Kann man irgendwie die 154 verkleinern?
Hat jemand eine Idee?
Gruß
yogi
|
|
| |
|
Hallo yogi_inf,
> Bestimmen Sie eine Zahl x element Z(154) mit
> 41 * mod 154 = 5.
Wo ist x in dieser Kongruenz?
Du meinst [mm] $41\cdot{}x [/mm] \ [mm] \equiv [/mm] \ 5 \ [mm] \mod{154}$
[/mm]
> Ahoi,
> Ich würde mich über Hilfe bei einem Ansatz sehr freuen.
> Die Möglichkeit das ganze durch "probieren" auszuknobeln
> ist hier ein wenig kompliziert. Dabei kommt 79 raus. [k]
Ja, darauf komme ich auch!
> Jetzt ist die Frage, wie man es berechnen kann.
Nun, zunächst ist 41 eine Primzahl, also [mm] $\ggT(41,154)=1$ [/mm] und [mm] $1\mid [/mm] 5$
Damit ist die Kongruenz schonmal lösbar.
Dann weiter mit dem eukidischen Algorithmus.
Berechne damit (durch Rückwärtseinsetzen) [mm] $a,b\in\IZ$ [/mm] mit [mm] $a\cdot{}154+b\cdot{}41=1$
[/mm]
Dann ist [mm] $b\cdot{}41=1-a\cdot{}154 [/mm] \ [mm] \equiv [/mm] \ 1 \ [mm] \mod{154}$
[/mm]
Damit ist $b$ das multiplikativ Inverse zu 41 modulo 154
Das [mm] $\cdot{}5$ [/mm] und modulo 154 und du hast es ...
> Die Bestimmung des multiplikativ Inversen hilft auch nicht
> weiter, da 154 dafür eine Primzahl sein müsste laut
> Skript.
> Kann man irgendwie die 154 verkleinern?
>
>
> Hat jemand eine Idee?
> Gruß
> yogi
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:47 Di 23.02.2010 | | Autor: | yogi_inf |
Okay,
das b hab ich berechnet mit ggt(154, 41) = a * 154 + b * 41 = 1 = 4*154 - 15 *41
=> b = -15
b * 41 = -74
-74 mod(154) = 79.
Super das geht :)
Danke für die Hilfe.
edit: Es sollte eine MItteilung sein, statt einer Frage
|
|
|
|
