Beweis Modulo-Reduzierbarkeit < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:40 Di 02.05.2006 | | Autor: | i-mehl |
Hi!
Nun, ich brauche dringend einen Beweis bzgl. der Tatsache, dass Zahlen modulo n reduzierbar sind, konkret also einen Beweis für folgende Tatsache:
a*b mod n = [(a mod n)*(b mod n)] mod n
Mein Ansatz:
a mod n = r1 <=> a = w1*n + r1,
b mod n = r2 <=> b = w2*n + r2,
a*b mod n = r3 <=> a*b = w3*n + r3
r1*r2 = w4*n + r4 <=> r1*r2 = w4*n + r4
Zu beweisen ist also: r3 = r4
Die letzte Zeile kann man folgendermaßen umformen:
r4 = r1*r2 – w4*n = (a – w1*n)*(b – w2*n) – w4*n
Tja... nur wie geht's weiter?
Bitte helft mir!
PS: Hoffe ich bin in der richtigen Rubrik. Falls nicht, tut es mir leid!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:12 Mi 03.05.2006 | | Autor: | leduart |
Hallo email
> Nun, ich brauche dringend einen Beweis bzgl. der Tatsache,
> dass Zahlen modulo n reduzierbar sind, konkret also einen
> Beweis für folgende Tatsache:
>
> a*b mod n = [(a mod n)*(b mod n)] mod n
>
> Mein Ansatz:
>
> a mod n = r1 <=> a = w1*n + r1,
> b mod n = r2 <=> b = w2*n + r2,
das war genau der richtige Weg!
einfach die 2 letzten gleichungen a*b=(w1*n+r1)*(w2*n+r2)=A*n+r1*r2 ausmultiplizieren, alles mit faktor n zusammenfassen, bleibt nur r1*r2!
Die neuen r3 und r4 machen das nur unübersichtlich!
Gruss leduart
|
|
|
|
