Autor |
Beitrag |
musicman
| Veröffentlicht am Sonntag, den 07. Januar, 2001 - 10:50: |
|
Kann mir irgendjemand das Ergebnis dieser Gleichung sagen, oder (noch besser) kann mir jemand den Rechenweg dazu erklären: (y*x) mod z=1 Ich würde mich für eine Auflösung nach x interessieren wenn y und z bekannt sind. Danke im voraus, musicman |
Martin
| Veröffentlicht am Sonntag, den 07. Januar, 2001 - 12:18: |
|
Meines Wissens gibt es für diese Gleichung keine allgemeine Lösung. Auf jeden Fall müssen y und z teilerfremd sein, damit es eine Lösung giben kann. Außerdem gilt: Wenn t eine Lösung für x ist, dann ist auch t+z eine Lösung für x und außerdem ist x immer teilerfremd zu z. Am besten du machst dir eine Tabelle wo du immer die kleinste Lösung für x einträgst, dann siehst du die Regelmäßigkeiten. |
Ingo
| Veröffentlicht am Sonntag, den 07. Januar, 2001 - 13:44: |
|
(xy)mod z = 1 => es gibt ein tÎIN,so daß xy=tz+1 <=> es gibt ein tÎIN mit x=(tz+1)/y Sieht wunderbar nach einer Lösung aus,ist es aber nicht.Denn es bleibt die Frage welchen Wert t denn nun annehmen darf,damit x wirklich eine natürliche Zahl ist.Das setzt y als Teiler von tz+1 voraus,was wiederum bedeutet,daß (tz)mod y =-1 womit wir fast wieder am Anfang der Aufgabe wären. Kurz gesagt : Ich schließe mich Martin an.Auch ich kenne keine allgemeine Lösung. |
Zaph (Zaph)
| Veröffentlicht am Sonntag, den 07. Januar, 2001 - 14:32: |
|
Hallo, wie Martin schon sagte, existiert genau dann eine Lösung, wenn ggT(y,z) = 1. Und wie Ingo erwähnte, ist die Gleichung x y - t z = 1 zu lösen. Das funktioniert mit dem "erweiterten euklidischen Algorithmus". Ein Beispiel: y = 13, z = 5, 13 = 2 * 5 + 3 [Teilen mit Rest] 5 = 1 * 3 + 2 [teile immer weiter ...] 3 = 1 * 2 + 1 2 = 2 * 1 + 0 [... bis der Rest 0 ist] Der letzte Rest, der nicht Null ist, ist der ggT der Ausgangswerte 5 und 13. Das nennt man den "Euklidischen Algorithmus". Jetzt kommt die Erweiterung. Löse ab der vorletzten Gleichung rückwärts auf: 1 = 3 - 1 * 2 = 3 - 1 * (5 - 1 * 3) = 2 * 3 - 1 * 5 = 2 * (13 - 2 * 5) - 1 * 5 = 2 * 13 - 5 * 5 Also x = 2, t = 5. Dies ist aber nur eine Lösung. Die allgemeine Lösung lautet x = 2 + 5 k t = 5 + 13 k (k beliebig) |
musicman
| Veröffentlicht am Montag, den 08. Januar, 2001 - 10:29: |
|
Danke für die Erklärungen musicman |
musicman
| Veröffentlicht am Montag, den 08. Januar, 2001 - 11:05: |
|
Ich hab jetzt noch zwei kleine Probleme, 1. z ist grösser als y und 2. meine Zahlen sind ziemlich gross z=1241844408 y=673 Danke |
Zaph (Zaph)
| Veröffentlicht am Montag, den 08. Januar, 2001 - 17:03: |
|
Der Algorithmus funktioniert auch, wenn z > y. Es ist y = 0 * z + 673. Vielleicht hilft dir das folgende Progrämmchen weiter. (Dort ist a durch x, m durch z und z durch y zu ersetzen.) // Berechne a mit a*z = ggT(z,m) mod m für m > 0 int invert(int z,int m){ int x = z, y = m, a = 1, b = 0, q, r; while(y != 0){ q = x/y; r = x - q * y; // Divisionsrest x/y x = y; y = r; r = a - q * b; a = b; b = r; }; // an dieser Stelle x = ggT(z,m) // Ergebnis soll zwischen 0 und m-1 liegen while(a < 0) a += m; while(a >= m) a -= m; return a; }
|
|