Modulo umkehren < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:10 Fr 31.07.2009 | | Autor: | swtrse |
| Aufgabe | Bestimmung einer Zahl(x) die folgende Bedingung erfüllt.
x modulo a = b
x modulo c = d
Wobei a, b, c und d gegeben sind. |
Hallo,
Modulo ist ja bekantlich der Rest einer Division.
Ich versuche nun möglichst schnell eine Zahl zu ermitteln die diese Bedingungen erfüllt. Mein derzeitiger Lösungansatz funktioniert zwar ist aber für große Zahlen ungeeignet da viel zu langsam.
Beispiel:
a = 5, b=4, c = 7, d = 5
x modulo 5 = 4
x modulo 7 = 5
4,5 -> (4 < 5) -> 4+5
9,5 -> (9 > 5) -> 5+7
9,12 -> (9 < 12) -> 9+5
14,12 -> (14 > 12) -> 12+7
14,19 -> (14 < 19) -> 14+5
19,19 -> (19 = 19) -> gefunden.
Gibt es hier einen schnelleren Weg zum zum Ergebniss zu kommen?
Es muss nicht die kleinste Zahl sein die diese Bedinung erfüllt, im Grunde reicht mir eine Beliebige.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.mymathforum.com/viewtopic.php?f=40&t=8977
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:29 Fr 31.07.2009 | | Autor: | rabilein1 |
> Bestimmung einer Zahl(x) die folgende Bedingung erfüllt.
> x modulo a = b
> x modulo c = d
> Wobei a, b, c und d gegeben sind.
>
> Mein derzeitiger Lösungansatz funktioniert zwar,
> ist aber für große Zahlen ungeeignet da viel zu langsam.
Wenn man eine Lösungsmöglichkeit gefunden hat, ist das doch gut.
Ab wann ist "große Zahl"? Was heißt "zu langsam"? Das ist alles relativ.
> Beispiel: a = 5, b = 4, c = 7, d = 5
Dann kommen für a = 5, b = 4 in Frage:
4 - 9 - 14 - 19 - 24 - 29 - 34 - 39 - 44 - 49 - 54 - 59 - ...
Und für c = 7, d = 5 kommen in Frage:
5 - 12 - 19 - 26 - 33 - 40 - 47 - 54 - 61 - ...
Die 19 und die 54 kommen in beiden Reihen vor.
Alle 35 (=a*c) kommen die Zahlen in beiden Reihen vor.
Falls a und c durcheinander gekürzt werden können (das ist hier nicht der Fall), dann ist die Wiederholung noch öfter als a*c.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:00 Mo 03.08.2009 | | Autor: | swtrse |
Zahlen im Milliarden Bereich und höher.
Und zu langsam ist wenn mein Computer länger als ~5 Minuten für die Berechnung braucht, was mit meinem Algorythmuss der Fall war.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:08 Fr 31.07.2009 | | Autor: | abakus |
> Bestimmung einer Zahl(x) die folgende Bedingung erfüllt.
> x modulo a = b
> x modulo c = d
> Wobei a, b, c und d gegeben sind.
> Hallo,
>
> Modulo ist ja bekantlich der Rest einer Division.
> Ich versuche nun möglichst schnell eine Zahl zu ermitteln
> die diese Bedingungen erfüllt. Mein derzeitiger
> Lösungansatz funktioniert zwar ist aber für große Zahlen
> ungeeignet da viel zu langsam.
> Beispiel:
> a = 5, b=4, c = 7, d = 5
> x modulo 5 = 4
x lässt bei Teilung durch 5 den Rest 4. Also gilt x=5m+4
> x modulo 7 = 5
x lässt bei Teilung durch 7 den Rest 5. Also gilt x=7n+5
Gleichsetzen von x führt auf 5m+4=7n+5.
Dann gilt auch 5m+4 [mm] \equiv [/mm] 7n+5 mod k (gleiche große Terme lassen bei Teilung durch eine beliebige Zahl k natürlich auch den gleichen Rest).
Wenn wir k=5 oder k=7 wählen, verschwindet 5m oder 7n.
Für k=5 wird daraus
4 [mm] \equiv [/mm] 7n+5 mod 5,
4 [mm] \equiv [/mm] 7n mod 5,
4 [mm] \equiv [/mm] 2n mod 5,
2 [mm] \equiv [/mm] n mod 5.
Die einfachste Möglichkeit dafür ist n=2, und wegen x=7n+5 ist x dann 19.
Gruß Abakus
> 4,5 -> (4 < 5) -> 4+5
> 9,5 -> (9 > 5) -> 5+7
> 9,12 -> (9 < 12) -> 9+5
> 14,12 -> (14 > 12) -> 12+7
> 14,19 -> (14 < 19) -> 14+5
> 19,19 -> (19 = 19) -> gefunden.
>
> Gibt es hier einen schnelleren Weg zum zum Ergebniss zu
> kommen?
> Es muss nicht die kleinste Zahl sein die diese Bedinung
> erfüllt, im Grunde reicht mir eine Beliebige.
>
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> http://www.mymathforum.com/viewtopic.php?f=40&t=8977
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:54 Mo 03.08.2009 | | Autor: | swtrse |
Danke
So etwas hab ich gsucht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:27 Sa 01.08.2009 | | Autor: | felixf |
Hallo!
> Bestimmung einer Zahl(x) die folgende Bedingung erfüllt.
> x modulo a = b
> x modulo c = d
> Wobei a, b, c und d gegeben sind.
> Hallo,
>
> Modulo ist ja bekantlich der Rest einer Division.
> Ich versuche nun möglichst schnell eine Zahl zu ermitteln
> die diese Bedingungen erfüllt. Mein derzeitiger
> Lösungansatz funktioniert zwar ist aber für große Zahlen
> ungeeignet da viel zu langsam.
Sagt dir der Chinesische Restsatz etwas? Der liefert doch einen sehr schnellen Algorithmus, der bei kleinen Zahlen zwar etwas uebertrieben wirkt, aber insbesondere bei grossen Zahlen zeigt wie schnell er eigentlich ist.
Dazu berechnet man erstmal $g = ggT(b, d)$; der ![[]](/images/popup.gif) Erweiterte Euklidische Algorithmus liefert Zahlen $h, k [mm] \in \IZ$ [/mm] mit $g = h b + k d$ (wir nehmen an, dass $g [mm] \ge [/mm] 1$ ist).
Ist $g = 1$, so kann man jetzt $x = h b c + k d a$ (modulo $b d$) waehlen; dann gilt $x [mm] \equiv [/mm] k d a [mm] \equiv [/mm] a (1 - h b) [mm] \equiv [/mm] a [mm] \pmod{b}$ [/mm] und $x [mm] \equiv [/mm] h b c [mm] \equiv [/mm] c (1 - k d) [mm] \equiv [/mm] c [mm] \pmod{d}$, [/mm] also $x$ ist die gesuchte Loesung.
Im Fall $g > 1$ muss man etwas geschickter vorgehen. Am besten faktorisiert man erstmal $b$ und $d$ als Produkt von Primzahlpotenzen, sagen wir $b = [mm] p_1^{x_1} \cdots p_n^{x_n}$ [/mm] und $c = [mm] p_1^{y_1} \cdots p_n^{y_n}$. [/mm] Dann bekommt man zu jedem $i [mm] \in \{ 1, \dots, n \}$ [/mm] die Gleichungen $x [mm] \equiv [/mm] a [mm] \pmod{p_i^{x_i}}$ [/mm] und $x [mm] \equiv [/mm] c [mm] \pmod{p_i^{y_i}}$. [/mm] Damit es ueberhaupt eine Loesung gibt, muss $a [mm] \equiv [/mm] c [mm] \pmod{p_i^{\min\{ x_i, y_i \}}}$ [/mm] gelten fuer alle $i$; wenn dies fuer ein $i$ nicht gilt, ist man gleich fertig mit der Meldung "Es gibt keine Loesung!". Stimmt dies fuer alle $i$, so schmeisst man die Gleichung mit dem kleineren Exponenten zu [mm] $p_i$ [/mm] weg. Dann hat man $n$ Gleichungen mit teilerfremden Moduli, und verwendet den obigen Fall fuer $g = 1$ einfach $n - 1$ mal, um je zwei dieser Gleichungen zu einer zusammenzufassen; schliesslich erhaelt man eine Gleichung $x [mm] \equiv [/mm] ... [mm] \pmod{kgV(b, d)}$, [/mm] und die ... sind dann die gesuchte Loesung.
> Beispiel:
> a = 5, b=4, c = 7, d = 5
Hier sieht man sofort: $1 = (-1) [mm] \cdot [/mm] b + 1 [mm] \cdot [/mm] d$, womit $h = -1$ und $k = 1$ ist. Damit ist $x = h b c + k d a = -4 [mm] \cdot [/mm] 7 + 5 [mm] \cdot [/mm] 5 = -28 + 25 = -3 [mm] \equiv [/mm] -3 + b d = -3 + 20 = 17$. Und siehe da, $17 [mm] \equiv [/mm] 1 [mm] \pmod{4}$ [/mm] und $17 [mm] \equiv \pmod{5}$, [/mm] was auch so sein sollte.
> x modulo 5 = 4
> x modulo 7 = 5
> 4,5 -> (4 < 5) -> 4+5
> 9,5 -> (9 > 5) -> 5+7
> 9,12 -> (9 < 12) -> 9+5
> 14,12 -> (14 > 12) -> 12+7
> 14,19 -> (14 < 19) -> 14+5
> 19,19 -> (19 = 19) -> gefunden.
Nun, $19 [mm] \equiv [/mm] 3 [mm] \pmod{4}$ [/mm] und nicht $19 [mm] \equiv [/mm] 1 [mm] \pmod{4}$, [/mm] womit 19 keine Loesung ist! Da hast du dich wohl verrechnet?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:37 Sa 01.08.2009 | | Autor: | felixf |
Hallo!
> Im Fall [mm]g > 1[/mm] muss man etwas geschickter vorgehen. Am
> besten faktorisiert man erstmal [mm]b[/mm] und [mm]d[/mm] als Produkt von
> Primzahlpotenzen, sagen wir [mm]b = p_1^{x_1} \cdots p_n^{x_n}[/mm]
Es reicht uebrigens aus, das ganze auf hoechstens sechs Gleichungen zu erweitern:
man waehlt natuerliche Zahlen $z, y, z', y'$ mit folgenden Eigenschaften:
1) $z, y$ sind teilerfremd;
2) es gilt $z' [mm] \mid [/mm] z$ und $y' [mm] \mid [/mm] y$;
3) es gilt $b = z' y$ und $d = z y'$.
(Salopp: $z$ / $z'$ enthalten die Primzahlpotenzen, bei denen der Exponent in $d$ hoeher ist, und $y$ / $y'$ enthalten die Primzahlpotenzen, bei denen der Exponent in $b$ hoeher ist.)
Dann muss man folgende zwei Bedingungen zur Loesbarkeit testen: $a [mm] \equiv [/mm] c [mm] \pmod{z'}$ [/mm] und $a [mm] \equiv [/mm] c [mm] \pmod{y'}$
[/mm]
Und schliesslich erhaelt man folgende zwei Gleichungen: $x [mm] \equiv [/mm] a [mm] \pmod{y}$, [/mm] $x [mm] \equiv [/mm] c [mm] \pmod{z}$
[/mm]
Hier sind $y$ und $z$ teilerfremd, und man kann diese also wie im ersten Post beschrieben loesen. Die Loesung ist dann das gesuchte $x$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:08 Sa 01.08.2009 | | Autor: | rabilein1 |
Beispiel:
a = 5, b = 4, c = 7, d = 5
> Nun, [mm]19 \equiv 3 \pmod{4}[/mm] und nicht [mm]19 \equiv 1 \pmod{4}[/mm],
> womit 19 keine Loesung ist! Da hast du dich wohl
> verrechnet?
Häää ???
19:5 = 3 Rest 4
19:7 = 2 Rest 5
> Und siehe da, ... , was auch so sein sollte.
Ich weiß nicht, wie du auf 17 kommst. Da sollte immer 19 raus kommen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:51 Sa 01.08.2009 | | Autor: | felixf |
Hallo,
> Beispiel:
> a = 5, b = 4, c = 7, d = 5
>
> > Nun, [mm]19 \equiv 3 \pmod{4}[/mm] und nicht [mm]19 \equiv 1 \pmod{4}[/mm],
> > womit 19 keine Loesung ist! Da hast du dich wohl
> > verrechnet?
>
>
> Häää ???
> 19:5 = 3 Rest 4
> 19:7 = 2 Rest 5
Oh. Ich bin irgendwie gerade von $x [mm] \equiv [/mm] a [mm] \pmod{b}$ [/mm] und $x [mm] \equiv [/mm] c [mm] \pmod{d}$ [/mm] ausgegangen. Also in meinen beiden Beitraegen.
Wenn man alles dementsprechend anpasst, dann stimmt es wieder...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:55 Mo 03.08.2009 | | Autor: | swtrse |
Genau so etwas hat mir gefehlt.
Der Praktische test fehlt mir zwar noch doch ich bin überzeigt das mir das sehr weiterhilft.
|
|
|
|
