Modulare Arithmetik
-
Hallo zusammen,
ich beschäftige mich gerade mit den Rechenregeln der modularen Arithmetik. Es gilt:
(a + b) mod n = ((a mod n) + (b mod n)) mod n)
Beweis: Es sei a = kn + a mod n und b = ln + b mod n
a + b = (k+l)n + a mod n + b mod n | mod n
(a + b) mod n = ((a mod n) + (b mod n)) mod nWo ist denn plötzlich (k+l)n hin? Warum kann man das rauslassen?
Danke für die Hilfe!
-
Es sei a = kn + a mod n und b = ln + b mod n
a + b
= //Einsetzen von a und b
kn + a mod n + ln + b mod n
= kn + ln + ...
= (k+l)n ...
-
freakC++ schrieb:
Wo ist denn plötzlich (k+l)n hin? Warum kann man das rauslassen?
Weil's ein Vielfaches von n ist.
-
achso! Weil das gar nicht zum Rest gehört?
-
Wenn Du ein Vielfaches von n durch n teilst, erhälst Du als Rest 0. Und 0 kannst Du in der Summe weglassen.
-
stimmt...da war was
-
a mod n ist die Menge (Restklasse) { a, a-n, a+n, a-2n, a+2n, ... }
also ist
a+b mod n die Menge { a+b, a+b-n, a+b+n, a+b-2n, a+b+2n, ... } - was gibt's da zu beweisen
-
Das "also"?
-
eben nicht: (a+(n))+(b+(n)) = a+b+(n) ist die Definition von Addition in Z/nZ
http://de.wikipedia.org/wiki/Faktorring
Rechnet man nicht mit den Restklassen an sich, sondern mit einem bestimmten Repräsentantensystem wie { 0, 1, ... , n-1}, dann wird's erst mühsam, weil man das Ergebnis jeder Rechenoperation mit Div.m.Rest auf den Repräsentanten reduzieren muß.
-
Wenn man als Definition von A+B die Menge {a+b | a in A, b in B} verwendet muß man schon noch was zeigen.
-
a+(n) ist aber nicht nur eine irgend eine Menge, sondern eine Restklasse. Z ist ein Ring, (n) ein Ideal und daher ist da nix mehr zu beweisen. Definition benutzen und fertig.
-
!rr!rr_. schrieb:
a+(n) ist aber nicht nur eine irgend eine Menge, sondern eine Restklasse. Z ist ein Ring, (n) ein Ideal und daher ist da nix mehr zu beweisen. Definition benutzen und fertig.
Du weißt doch gar nicht, was er gegeben hat.
Vielleicht hat er nur die Definition von mod und die Rechengesetzte für ganze Zahlen.
Ob da Ringe oder Ideale drin sind, wird er auch noch beweisen müssen.
-
!rr!rr_. schrieb:
a+(n) ist aber nicht nur eine irgend eine Menge, sondern eine Restklasse. Z ist ein Ring, (n) ein Ideal und daher ist da nix mehr zu beweisen. Definition benutzen und fertig.
Man hat einmal: (a + (n)) + (b + (n)) und einmal [a+b] + (n)
Dabei ist im ersten Ausdruck jedes "+" ein "+" von zwei Mengen, im zweiten Ausdruck ist das "+" zwischen a und b ein "+" von ganzen Zahlen und das zweite "+" ein Plus von zwei Mengen. Dass das das gleiche ist muß man natürlich beweisen.Natürlich folgt das aus der Definition, genau so sind Ideale ja gebaut, aber wann folgt denn bittschön mal was nicht aus den Definitionen? -- Richtig, alles was beweisbar ist folgt aus Definitionen. Aber deswegen kann man noch lange nicht alle Beweise weglassen.
-
in Z/nZ folgt a+b + (n) = a+(n) + b+(n) nicht aus einer Definition, sondern das [i]ist[i] die Definition - die Def. der Addition in einem Faktorring.
habe ich jetzt in diesem Augenblick ein besonders starkes deja Vu, oder habe ich genau das vor wenigen Stunden schon mal geschrieben ?
-
!rr!rr_. schrieb:
in Z/nZ folgt a+b + (n) = a+(n) + b+(n) nicht aus einer Definition, sondern das [i]ist[i] die Definition - die Def. der Addition in einem Faktorring.
Und woher weiß freakC++, daß da so ein Ring vorliegt?
!rr!rr_. schrieb:
habe ich jetzt in diesem Augenblick ein besonders starkes deja Vu, oder habe ich genau das vor wenigen Stunden schon mal geschrieben ?
Das geht nicht bloß Dir so.
-
!rr!rr_. schrieb:
in Z/nZ folgt a+b + (n) = a+(n) + b+(n) nicht aus einer Definition, sondern das [i]ist[i] die Definition - die Def. der Addition in einem Faktorring.
Dann muß er halt die Wohldefiniertheit davon nachweisen. Nenn es wie du willst, da ist was zu tun.
-
muß er eben nicht. Jedes Ideal I ist per Definition eine additive Gruppe, und damit ist die Addition in R/I automatisch wohldefiniert:
a-a' in I, b-b' in I => (a+b)-(a'+b') = (a-a')+(b-b') in I
-
!rr!rr_. schrieb:
Jedes Ideal I
*facepalm* Willst Du's nicht verstehen? freakC++ ist - wenn überhaupt - im 1. Semester Mathe. Da hat er noch nichts von Idealen gehört.
-
!rr!rr_. schrieb:
muß er eben nicht. Jedes Ideal I ist per Definition eine additive Gruppe, und damit ist die Addition in R/I automatisch wohldefiniert:
a-a' in I, b-b' in I => (a+b)-(a'+b') = (a-a')+(b-b') in IJa, und genau sowas muß man im ersten Semester halt mal ordentlich beweisen, inklusive runterbrechen auf die Definition des Ideals -- damit man später sagen kann "ist ja klar, das gilt automatisch". Mich wundert, dass Du dich da überhaupt nicht hin zurückversetzen kannst.
-
ach so. Na dann ...