Beweis Modulorechnung
-
Hallo zusammen,
ich steige unter anderem gerade in die Welt der mathematischen Beweise ein. Ich soll zeigen, dass die Aussage a|b äquivalent zu a mod b == 0 ist.
Das ist sowas von trivial, dass ich beim Beweis schon wieder nicht so sicher bin. Ich bitte euch, meine Idee zu überprüfen und ggf. zu verbessern.
Um eine Äquivalenz zu zeigen, zeigt man die Implikation in beide Richtungen.
Schritt 1: a|b => b mod a = 0
Wenn a b teilt (z.B. a = 2 und b = 4), so lässt sich a als a = q * b darstellen. Die Definition des Rests heißt logischerweise r = a - q * b. Nun setze den obigen Ausdruck für a ein und ich erhalten r = qb - qb = 0. Das entspricht gerade b mod a = 0.
Schritt 2: b mod a = 0 => a|b
Wenn der Rest 0 ist bedeutet dies: 0 = a - q*b. Wenn ich diese Gleichung nach a auflöse, dann erhalte ich a = qb. Das entspricht gerade der Notation a|b.
Ich habe also (hoffentlich) gezeigt, dass die Aussagen äquivalent sind.
Meine Frage: War das jetzt wirklich ein Beweis, der stimmt, oder habe ich etwas falsch gemacht? Mir kommt das viel zu trivial vor. Schritt 2 ist ja eigentlich Schritt 1, nur rückwerts.
Herzlichen Dank
lg, freakC++
-
freakC++ schrieb:
ich steige unter anderem gerade in die Welt der mathematischen Beweise ein. Ich soll zeigen, dass die Aussage a|b äquivalent zu a mod b == 0 ist.
Das ist sowas von trivial, dass ich beim Beweis schon wieder nicht so sicher bin. Ich bitte euch, meine Idee zu überprüfen und ggf. zu verbessern.
Du hast es gerade mit Nachdenken versucht. Und er Beweis ist mit vielen irghendwoherkommenden Annahmen und Sätzen gespickt, die ich jetzt gar nicht so genau kenne. In diesem Sinne ist er niocht scharf. Hast nicht genannt, was Du eingeführt hast.
Sag mal, hast Du eine Definition von | und von % vorliegen?
Falls ja, kannste da einfach einsetzten! Dann ist der Beweis scharf.
-
Schritt 2 ist ja eigentlich Schritt 1, nur rückwerts.
Ist doch super, wenn das geht. Dann kann man es gleich als Äquivalenz aufschreiben.
Wie definierst du b mod a? Divisionsrest ist ein bisschen schwammig. Sagen wir so: b mod a = r :<=> es gibt ein q, so dass b = qa + r mit 0 <= r < a.
Dann kann es direkt hinschreiben:
a|b <=> es gibt q mit qa = b <=> es gibt q mit b = qa + 0 <=> b mod a = 0
-
Für mod kenne ich die Definition b mod a := b - a·⌊b/a⌋.
Dann wäre der Beweis vermutlich: a|b :⇔ ∃k: a·k = b. Dann ist b/a = k, somit b mod a = b - ak. Da aber ak = b, gilt dann also b mod a = b - b = 0.
-
genau genommen ist a mod b die Äquivalenzklasse
a+(b) = {a, a-b, a+b, a-2b, a+2b, ... } und aus dieser Definition folgt sofort 0 in a+(b) <=> b|a
-
volkard schrieb:
Du hast es gerade mit Nachdenken versucht. Und er Beweis ist mit vielen irghendwoherkommenden Annahmen und Sätzen gespickt, die ich jetzt gar nicht so genau kenne. In diesem Sinne ist er niocht scharf. Hast nicht genannt, was Du eingeführt hast.
Sag mal, hast Du eine Definition von | und von % vorliegen?
Falls ja, kannste da einfach einsetzten! Dann ist der Beweis scharf.Ich habe tatsächlich einfach die Definition von | und % angewandt. Ich habe sie so hier stehen:
Rest r = a - qb = a % b
a | b = b = mpDa bin ich aber froh, dass mein Beweis stimmt.
