Modulo-Rechnung Beweis

ich bräuchte mal eure hilfe: ich soll folgendes beweisen:frowning:Quersumme(u)+ Quersumme(v)) mod 3 = W mod 3
dabei gilt:
u + v = w
u und v sind zwei positive, ganze zahlen

meine Überlegung:
w mod3 = (u+v) mod3= u mod3 +v mod3
da u und v jeweis zwei positive ganze sind, gilt:
u= a1 * 10^i + a2 *10^(i-1) + … + a0 * 10^0
außerdem gilt 10^x = 3^n +1 --> 10^x ≡ 3^n +1 ≡ 1 (mod3)

–> u≡ a1 *1 + a2*2 + … + a0 *1 (mod 3)
≡ a1 + a2 + … + a0 (mod3)
≡ Q(u)

–> w mod3 = (u+v) mod3=u mod3 +v mod3 = Q(u)mod3 + Q(v)mod3

stimmt das so ?

moin;

sieht soweit richtig aus, bis auf einen Fehler:

(u+v) mod3= u mod3 +v mod3

dies gilt natürlich nicht, das muss schon (u+v) mod 3 bleiben.
Glücklicherweise behindert das den Beweis, so wie du ihn planst, nicht, du hast genau genommen ja sowieso das Falsche bewiesen.

mfG

sieht soweit richtig aus, bis auf einen Fehler:

(u+v) mod3= u mod3 +v mod3

dies gilt natürlich nicht, das muss schon (u+v) mod 3 bleiben.

Wenn man dahinter noch ein mod 3 setzt, stimmt das durchaus.
Also (u+v) mod 3 = ((u mod 3)+(v mod 3)) mod 3.

mfg,
Ché Netzer

Hallo,

stimmt das so ?

ja, bis auf einen Tippfehler: Es muss 10^x = 3n + 1 heißen (nicht „3^n“).

Ich würde in der Lösung deutlich herausstellen, dass der Beweis aus zwei Teilen besteht, und diese auch sauber getrennt voneinander abhandeln:

(1) Wenn eine Funktion f die Eigenschaft hat, dass alle Zahlen x zu ihren Funktionswerten f(x) kongruent sind, dann ist die Summe zweier Zahlen auch stets zur Summe ihrer Funktionswerte kongruent:

x \equiv f(x) ::\textnormal{f"ur alle $x$}
\quad\Longrightarrow\quad
u + v \equiv f(u) + f(v) ::\textnormal{f"ur alle $u$, $v$}

und

(2) Die Quersumme ist eine Funktion mit der Eigenschaft x ≡ f(x).

Der Grund, warum (1) stimmt, ist (u + v) mod m = ((u mod m) + (v mod m)) mod m, und der Grund, warum (2) stimmt, ist 10k = … (siehe oben).

Gruß
Martin

ersteinmal danke :smile:
also kann ich es dann so schreiben?

w mod3 = = (Q(u)mod3 + Q(v)mod3)mod3

und noch was:
muss man noch beweisen, dass
(u+v) mod3=(u mod3 +v mod3) mod3 ist oder kann man es einfach annehmen?