Modulo < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:18 Fr 13.06.2008 | | Autor: | barsch |
Hi,
ich habe mehrere Aufgaben der folgenden Form; hier einmal ein Beispiel.
Berechne a, sodass gilt:
(9*a) mod 29 = 1
Nachtrag: Wichtig: [mm] a\in\IN [/mm] - sonst könnte ich ja einfach sagen [mm] a=\bruch{1}{9}.
[/mm]
Wie aber komme ich hier auf mein a?
Ich habe schon versucht, in Wikipedia dahingehend etwas zu finden - jedoch erfolglos. Vielleicht hat von euch jemand eine Idee!?
Danke.
MfG barsch
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:54 Fr 13.06.2008 | | Autor: | pelzig |
> Berechne a, sodass gilt:
> (9*a) mod 29 = 1
>
> Nachtrag: Wichtig: [mm]a\in\IN[/mm] - sonst könnte ich ja einfach
> sagen [mm]a=\bruch{1}{9}.[/mm]
Naja also die Idee ist gar nicht so schlecht mit dem [mm] \frac{1}{9}, [/mm] wenn du dich nämlich im Restklassenring [mm] \IZ/29\IZ [/mm] befindest, ist [mm] \frac{1}{9}, [/mm] also das Inverse von 9, einfach diejenige Zahl, die mit 9 multiplizert 1 ergibt - also genau das was wir wollen.
Zur Berechnung der Inversen in Restklassenringen benutzt man den ![[]](/images/popup.gif) erweiterten euklidischen Algoritmus.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:12 So 15.06.2008 | | Autor: | ZoGGi |
Hm bin an derselben Aufgabe interessiert, aber deine Antwort hilft mir leider nur geringfügig weiter.
Könntest du mir evtl. noch weiter helfen?
Gruß
Alexander
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:50 So 15.06.2008 | | Autor: | ullim |
Hi,
vielleicht gehts so.
Der ggT von 9 und 29 ist 1 weil 29 Prim ist.
Also liefert dir der vorgeschlagene Algorithmus Zahlen s und t für folgende Gleichung
1 = s*9 + t*29
und damit ist s die gesuchte Lösung für die Gleichung 9*a mod 29 = 1
mfg ulim
|
|
|
|
