Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

(y*x)modz=1

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Zahlentheorie » (y*x)modz=1 « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

musicman
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 07. Januar, 2001 - 10:50:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 07. Januar, 2001 - 12:18:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Ingo
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 07. Januar, 2001 - 13:44:   Beitrag drucken

(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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 07. Januar, 2001 - 14:32:   Beitrag drucken

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)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

musicman
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Januar, 2001 - 10:29:   Beitrag drucken

Danke für die Erklärungen
musicman
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

musicman
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Januar, 2001 - 11:05:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Januar, 2001 - 17:03:   Beitrag drucken

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;
}

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page