Hallo Mathe Experten,
ich brauch mal Eure Hilfe.
Aufgabe:
11 * t = 13 mod 16
9 * t = 20 mod 25
Finde t.
Dafür braucht man u.a. den erweiterten Euklid, der auch soweit bekannt und verstanden ist, der chinesische Restsatz, um den es da wohl i.w. geht, erschliesst sich mir jedoch so gar nicht. Ich hab gegooglet, ohne verwertbares Resultat, und mein Buch („Diskrete Strukturen“ von Steger) ist eine dermaßene didaktische Nullnummer, daß ich da echt keinen Zugang finde. Kann mir das jemand „für Dummies“ erklären?
Gruß,
Malte.
PS: Es geht hier _nicht_ um die Erledigung von Hausaufgaben o.ä., obige Aufgabe ist nur ein Beispiel.
Hallo,
der chin. Restsatz eignet sich dazu aus Reihe von Kongruenzen
a mod ni=bi für 1i paarweise teilerfremd, ein
a mod n mit n=n1*n2*…*nm
zu finden, daß alle obigen Kongruenzen erfüllt. Algebraisch bedeuted das, daß die prime Restklassengruppe Zn=(Zn,*,1) isomorph zum direkten Produkt der primen Restklassengruppen Zn(i)=(Zn(i),*,1) ist. Also die Idee, die dahinter steckt ist Kompositionalität, d.h. aus kleinen Stückchen etwas größeres zusammenbauen oder umgekehrt das große in Stückchen zu zerlegen. In Deinem Bsp. sind n(1)=16 und n(2)=25 teilerfremd. Man ermittelt zuerst die Lsg. von
11 * t = 13 mod 16
9 * t = 20 mod 25
modulo 16 und modulo 25 und verfährt dann analog zu
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…
Gruss
Enno
PS: Wenn das nicht reicht poste ich nachher noch mal was dazu.
Hallo,
der chin. Restsatz eignet sich dazu aus Reihe von Kongruenzen
a mod ni=bi für 1i paarweise teilerfremd,
ein
a mod n mit n=n1*n2*…*nm
zu finden, daß alle obigen Kongruenzen erfüllt.
Bis hierhin klar, heisst, die Aufgabenstellung ist verstanden. :-/
Algebraisch bedeuted das, daß die prime Restklassengruppe
Zn=(Zn,*,1) isomorph zum direkten
Produkt der primen Restklassengruppen
Zn(i)=(Zn(i),*,1) ist.
Also die
Idee, die dahinter steckt ist Kompositionalität, d.h. aus
kleinen Stückchen etwas größeres zusammenbauen oder umgekehrt
das große in Stückchen zu zerlegen. In Deinem Bsp. sind
n(1)=16 und n(2)=25 teilerfremd.
Die Grundidee ist auch verstanden, so grob. Meint, ich seh das verschwommen Form annehmen.
Man ermittelt zuerst die Lsg. von
11 * t = 13 mod 16
9 * t = 20 mod 25
modulo 16 und modulo 25 und verfährt dann analog zu
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…
Da kann ich jetzt so gar nichts mit anfangen 
PS: Wenn das nicht reicht poste ich nachher noch mal was dazu.
Das wäre nett. Danke für die Mühe && Grüße,
Malte.
Ok,
wenn man zunächst in 11t=13 mod 16, t=13*11-1=7 mod 16 und in 9t=20 mod 25, t=20*9-1=5 mod 25 bestimmt, gilt es t mod (16*25) zu berechnen. Dazu ordnet man jeder zunächst jeder Kongruenz a mod n(i)=b(i) den Ausdruck
b(i)*n/n(i)*(n/n(i)-1 mod n(i)) zu, also
t mod 16=7 bekommt 7*25*(25-1 mod 16) zugeordnet und
t mod 25=5 bekommt 5*16*(16-1 mod 25) zugeordnet.
t mod (16*25) ergibt sich dann Summe der beiden (modulo 16*25). Betrachtet man das Resultat nun z.B. modulo 16, fällt der korrespondierende Ausdruck für t mod 25=5 wg. dem Faktor 16 weg und es verbleibt
7*25*(25-1 mod 16) mod 16 = (7 mod 16)*(25 mod 16)*(25-1 mod 16) mod 16=7 mod 16
da (25 mod 16)*(25-1 mod 16) mod 16=1. Hier passieren also zwei Dinge. Die modulo 25 Bedingung wird weggeblendet und der identische „Trick“ bei der modulo 16 Bedingung wird durch Multiplikation mit dem Inversen wieder „unsichtbar“ gemacht.
Bestimmen wir nun
25-1 mod 16 = 9-1 mod 16=9 und
16-1 mod 25 = 11
Damit ist t=(7*25*9+5*16*11) mod (16*25)=55.
Zum den primen Restklassengruppen Z1615, Z16 und Z25. Die Elemente sind alle Zahlen Z1615 zu rechnen, komponentenweise in Z16 und Z25 rechnen kann.
Gruss
Enno
1 „Gefällt mir“
Danke
Danke Enno,
das hat schon sehr weitergeholfen. So ganz blick ich das zwar noch nicht, aber rein technisch ist mir der Weg klar.
Gruß,
Malte.