Gleichung mit mod lösen < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:23 Mo 02.07.2007 | | Autor: | LL0rd |
| Aufgabe | Q*R= 1 (mod 10^21)
Q=? |
Hallo,
ich sitze gerade vor folgender Aufgabe, haber aber derzeit keine Ahnung, wie ich wirklich da herangehen sollte. Gesucht ist das Q, das R ist eine vom Zufallsgenerator erzeugte Zahl zwischen 1 und 10^21, die Teilerfremd zu 10 ist. Mein Gefühl zu dieser späten Stunde sagt, dass ich hier mit dem Euklidischen Algorithmus eine Lösung finde, aber aus irgendeinem Grund kommt nur Müll heraus. Kann mir da jemand evtl. etwas weiterhelfen? Danke!
|
|
| |
|
> Q*R= 1 (mod 10^21)
> Q=?
Ein solches [mm]Q[/mm] gibt es nicht immer, da [mm]10^{21}[/mm] keine Primzahl ist. Mit anderen Worten: falls [mm]\text{ggT}(Q,10^{21})> 1[/mm] ist, gibt es kein solches [mm]Q[/mm].
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:05 Mo 02.07.2007 | | Autor: | LL0rd |
Sorry, aber ich verstehe deinen Lösungsansatz nicht wirklich. Ich suche doch gerade das Q. Das R spielt doch hier auch eine Rolle, denn das R ist ja Teilferfremt zu 10 (^21). Somit habe ich doch dann eine Lösung. Oder verstehe ich da jetzt etwas falsch?
|
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 15:38 Mo 02.07.2007 | | Autor: | Somebody |
> Sorry, aber ich verstehe deinen Lösungsansatz nicht
> wirklich. Ich suche doch gerade das Q. Das R spielt doch
> hier auch eine Rolle, denn das R ist ja Teilferfremt zu 10
> (^21). Somit habe ich doch dann eine Lösung. Oder verstehe
> ich da jetzt etwas falsch?
Nein, Du verstehst nichts falsch. Ich war offenbar am Morgen vor 7 Uhr noch nicht ganz wach. Wenn R teilerfremd zu [mm]10^{21}[/mm] ist, dann muss es ein solches [mm]Q[/mm] mit [mm]Q\cdot R = 1[/mm] (modulo [mm]10^{21}[/mm]) geben, da hast Du ganz recht.
Nun muss für ein solches [mm]Q[/mm] doch aber auch gelten [mm](Q+1)\cdot R=R[/mm] (modulo [mm]10^{21}[/mm]). Kann man daraus nicht schliessen, dass [mm]Q=10^{21}-1[/mm] ist?
Denn wiederholtes Addieren von [mm]R[/mm] muss, weil [mm]R[/mm] zu [mm]10^{21}[/mm] teilerfremd ist, die maximale Periodenlänge von [mm]10^{21}[/mm] verschiedenen Elementen liefern, bevor man erneut zu [mm]R[/mm] gelangt. (Andernfalls wären [mm]R[/mm] und [mm]10^{21}[/mm] nicht teilerfremt.)
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 16:16 Mo 02.07.2007 | | Autor: | Somebody |
> > Sorry, aber ich verstehe deinen Lösungsansatz nicht
> > wirklich. Ich suche doch gerade das Q. Das R spielt doch
> > hier auch eine Rolle, denn das R ist ja Teilferfremt zu 10
> > (^21). Somit habe ich doch dann eine Lösung. Oder verstehe
> > ich da jetzt etwas falsch?
> Nein, Du verstehst nichts falsch. Ich war offenbar am
> Morgen vor 7 Uhr noch nicht ganz wach. Wenn R teilerfremd
> zu [mm]10^{21}[/mm] ist, dann muss es ein solches [mm]Q[/mm] mit [mm]Q\cdot R = 1[/mm]
> (modulo [mm]10^{21}[/mm]) geben, da hast Du ganz recht.
> Nun muss für ein solches [mm]Q[/mm] doch aber auch gelten
> [mm](Q+1)\cdot R=R[/mm] (modulo [mm]10^{21}[/mm]). Kann man daraus nicht
> schliessen, dass [mm]Q=10^{21}-1[/mm] ist?
> Denn wiederholtes Addieren von [mm]R[/mm] muss, weil [mm]R[/mm] zu [mm]10^{21}[/mm]
> teilerfremd ist, die maximale Periodenlänge von [mm]10^{21}[/mm]
> verschiedenen Elementen liefern, bevor man erneut zu [mm]R[/mm]
> gelangt.
Diese Überlegung ist Müll: man kann schon vorher zu 1 gelangen. Ein einfacheres Beispiel mit kleineren Zahlen: R=3, aber [mm]2\cdot 3=1[/mm] modulo 5.
>(Andernfalls wären [mm]R[/mm] und [mm]10^{21}[/mm] nicht
> teilerfremt.)
|
|
|
|
