Modulo Beweis

04.03.2013, 21:24

Grummelchen

Modulo Beweis

Hallo, ich habe hier ein Übungsblatt, bei dem ich bei zwei Teilaufgaben nicht weiß was ich machen soll.

Also:

Sei m>=2 eine Natürliche Zahl, dann kann jede ganze Zahl a endeutig durch a=k*m+r, 0<=r<=m-1 darstellen.
Die ganzen Zahlen k und r können als Funktionswerte a DIV m = k und a MOD m=r...
Es seien a, b ganze Zahlen, zeige für die Operatoren: +,-,*
Zeige, dass gilt:
(a op b) MOD m = (a MOD m) op (b MOD m) MOD m

Die einzige Beweismöglichkeit, die ich kenne ist die Induktion.
Was mir hier einfällt wäre einzig und allein, dass man in die untere Gleichung etwas von oben einsetzt.
Nur wäre das ja nur eine andere Darstellung und kein Beweis.

r MOD m = r op r MOD m
Im Endeffekt ist r op r wieder irgendeine Zahl, also a

r MOD m = a MOD M

Das kann doch nicht ganz passen? r kann man schließlich wieder durch etwas anderes ausdrücken una a MOD m wiederrum durch r.

Könnte mir da bitte jemand helfen?

und
Bestimme kleinstes n von den natürlichen Zahlen.
n^3/3 > n^2,81
Keine Ahnung was ich da machen soll....

04.03.2013, 21:39

lgrizu

Auf diesen Beitrag antworten »

RE: Modulo Beweis
Das notwenige, um den Beweis direkt zu führen steht doch in der Aufgabenstellung:

jede ganze Zahl a kann dargestellt werden als $\begin{eqnarray*} a= k \cdot m +r~(*) \end{eqnarray*}$ , dabei ist $\begin{eqnarray*} a \mod m \equiv r \end{eqnarray*}$

Jetzt nimm dir doch einfach mal zwei Zahlen a und b und stelle sie wie in (*) dar, dann wende übliche Rechenregeln in den ganzen Zahlen an, wie weit kommst du?

Zitat:

Original von Grummelchen

Nur wäre das ja nur eine andere Darstellung und kein Beweis.

r MOD m = r op r MOD m

Das, was du da gemacht hast ist schlichtweg falsch.

Nimm dir zum Beispiel r=1 und m=3, dann ist $\begin{eqnarray*} 2 \mod 3=(r+r) \mod 3 \not\equiv r \mod 3=1 \mod 3 \end{eqnarray*}$

05.03.2013, 13:16

Grummelchen

Auf diesen Beitrag antworten »

Okay, ich dachte das würde so auch gehen, weil im Endeffekt hab ichs ja so eingesetzt.

Naja ich hab mir jetzt malüberlegt, dass dürfte doch so gehen wie bei Mengen.
Zuerst die linke Seite so umschreiben, dass sie wie die rechte aussieht und dann die rechte in die linke?

Wie du auf r+r kommst weis ich gar nicht.

Habe halt mal so:
(km + r op km+r) mod m
(km+a mod m OP km + b mod m)mod m

Wie ich da km wegbekomme sehe ich nicht..
Das einzige, was mir dazu einfällt wäre km durch a -r auszudrücken.
...Nur drehe ich mich da auf meinem Blatt total im Kreis und versuche immer etwas durch etwas anderes auszudrücken.

a-r +a mod m OP b-r +b mod m
2a-r mod m op 2b-r mod m
2km mod m op 2km mod m
Hmmm, ne komme immer aufs gleiche raus.

05.03.2013, 13:44

lgrizu

Auf diesen Beitrag antworten »

Wir setzen einmal:

$\begin{eqnarray*} a=k_1 \cdot m+r_1 \end{eqnarray*}$ und $\begin{eqnarray*} b=k_2 \cdot m+r_2 \end{eqnarray*}$

Nun rechnen wir aus (Beispiel Addition):

$\begin{eqnarray*} a+b=k_1 \cdot m+r_1+k_2 \cdot m+r_2 \underbrace{=}_{\text{Kommutativgesetz}}k_1 \cdot m+k_2 \cdot m+r_1+r_2 \end{eqnarray*}$

Nun noch Assoziativgesetz anwenden und danach Distributivgesetz, dann hat man es......

06.03.2013, 20:43

Grummelchen

Auf diesen Beitrag antworten »

Ja, was du da rechnest ist mir schon klar nur weiß ich nicht wie mich das weiterbringt?

Habe jetzt mal:

ka *m +ra + kb *m + rb mod m

Nach dem Distributivgesetz? bekomme ich dann

m * (ka + kb) + (ra + rb) mod m = ra + rb mod m ....rechte Seite

Gibt es da eine Möglichkeit die rechte Seite zu erweitern oder links das m*(ka + kb) zu entfernen?

06.03.2013, 21:35

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von Grummelchen

Nach dem Distributivgesetz? bekomme ich dann

m * (ka + kb) + (ra + rb) mod m = ra + rb mod m ....rechte Seite

Das ist doch schon mal okay, allerding lass das modulo doch erst mal weg, wir rechnen erst mal ganz normal in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$

Wir haben also:

$\begin{eqnarray*} a+b=(k_a+k_b) \cdot m + (r_a+r_b) \end{eqnarray*}$

Nun sollte es leicht sein zu zeigen, dass $\begin{eqnarray*} (a+b) \mod m =r_a+r_b \end{eqnarray*}$

07.03.2013, 21:46

Grummelchen

Auf diesen Beitrag antworten »

Nun sollte es leicht sein zu zeigen, dass $\begin{eqnarray*} (a+b) \mod m =r_a+r_b \end{eqnarray*}$

Müsste dabei nicht auf der rechten Seite ebenfalls ein mod m stehen?

Aber ich weiß trotzdem nicht weiter?

Das einzige wäre, ist modulo assoziativ?
dann wäre doch :
a mod m + b mod m = ra + rb ??

08.03.2013, 08:01

lgrizu

Auf diesen Beitrag antworten »

Es ist doch nach Definition $\begin{eqnarray*} r_a=a \mod m \end{eqnarray*}$ und $\begin{eqnarray*} r_b=b \mod m \end{eqnarray*}$ .

Es ist also zu zeigen, dass $\begin{eqnarray*} (a+b) \mod m = r_a + r_b =a \mod m + b \mod m \end{eqnarray*}$

Wir haben:

$\begin{eqnarray*} a+b=(k_a+k_b) \cdot m + (r_a+r_b) \end{eqnarray*}$

Damit ist doch $\begin{eqnarray*} (a+b) div m = k_a+k_b \end{eqnarray*}$ und $\begin{eqnarray*} (a+b) \mod m = ??? \end{eqnarray*}$

Jedenfalls deckt das schon mal den Fall $\begin{eqnarray*} r_a+r_b<m \end{eqnarray*}$ ab.

Nun gibt es noch den Fall, dass. $\begin{eqnarray*} r_a+r_b >m \end{eqnarray*}$ ist, dieser Fall ist ganz ähnlich zu behandeln

Neue Frage »

Antworten »

Modulo Beweis

Verwandte Themen