ggT < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:42 Do 10.02.2005 | | Autor: | Mukkular |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Moin liebe Leute,
ich habe eine Frage und hoffe, dass mir einer von Euch helfen kann:
Zu lösen seien folgende Probleme:
a) Bestimme, falls vorhanden, x [mm] \in [/mm] {0,1,...,577}, sodass gilt:
187x [mm] \equiv [/mm] 1 (mod 578)
b) Bestimme, falls vorhanden, x [mm] \in [/mm] {0,1,...,577}, sodass gilt:
165x [mm] \equiv [/mm] 1 (mod 578)
Ich denke, man muss erst mittels des Euklidischen Algorithmus ermitteln, ob 578 und 165 bzw. 578 und 187 teilerfremd sind also ggT(578,165)= 1
Wenn ggT = 1, dann kann man anfangen...
aber wie genau?
Danke
Mukkular
|
|
| |
|
Hallo,
die Kongruenz
[mm]ax\; \equiv \;c\;\bmod \;m[/mm]
hat nur dann eine Lösung, wenn ggt(a,m) = 1 ist.
Ist Dir die Eulersche [mm]\varphi [/mm]-Funktion bekannt?
Die Lösung der Aufgabe
[mm]ax\; \equiv \;c\;\bmod \;m[/mm]
gestaltet sich dann so:
[mm] x\; \equiv \;a^{\varphi (m) - 1} \;c[/mm]
Die Funktion [mm]\varphi [/mm] ist wie folgt definiert:
Ist p eine Primzahl, so gilt für sämtliche Potenzen von p:
[mm]\varphi \left( {p^{k} } \right)\; = \;p^{k - 1} \;\left( {p\; - \;1} \right)[/mm]
Weiterhin gilt für ggt(a,b) = 1:
[mm]\varphi \left( {a\;b} \right)\; = \;\varphi (a)\;\varphi (b)[/mm]
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:46 Fr 11.02.2005 | | Autor: | Mukkular |
Hallo Mathepower,
vielen Dank.
Ich habe zwischenzeitlich auch mal ein wenig herumprobiert und nachgeschaut.
Die Lösung habe ich dann mittels Rückwärtseinsetzen in den Euklidischen aLGORITHMUS erhalten.
Aber dennoch: besten Dank für die zeitnahe antwort
Mukkular
|
|
|
|
