Modulo Rechnung

19.06.2011, 13:39

Pascal95

Modulo Rechnung

Hallo,

ich möchte folgende Aufgabe lösen:

Zitat:

Sei $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ .
Zeigen Sie: Wenn $\begin{eqnarray*} a,\ b,\ a',\ b'\ \in\mathbb N \end{eqnarray*}$ mit:
$\begin{eqnarray*} a'\equiv a\mod n \end{eqnarray*}$ und $\begin{eqnarray*} b'\equiv b\mod n \end{eqnarray*}$ ,
so gilt auch:
$\begin{eqnarray*} a'+b'\equiv a+b\mod n \end{eqnarray*}$ und $\begin{eqnarray*} a'\cdot b'\equiv a\cdot b\mod n \end{eqnarray*}$ .

Meine Idee wäre folgendes:
$\begin{eqnarray*} p\equiv q\mod r \Leftrightarrow p\mod r=q\mod r \end{eqnarray*}$ .
Ich benutze auch: $\begin{eqnarray*} x+y\mod z=x\mod z+y\mod z \end{eqnarray*}$ (schon hier bin ich mir unsicher...)
Dann wäre
$\begin{eqnarray*} a'+b'\mod n=a'\mod n+b'\mod n=a\mod n+b\mod n=a+b\mod n \end{eqnarray*}$
$\begin{eqnarray*} a'\cdot b'\mod n=a'\mod n\cdot b'\mod n=a\mod n\cdot b\mod n=a\cdot b\mod n \end{eqnarray*}$

Kann man so argumentieren?

19.06.2011, 14:32

IfindU

Auf diesen Beitrag antworten »

RE: Modulo Rechnung, Zeigen Sie...
Du wirst hier vermutlich mit der Definition recht schnell zum Ziel kommen, also
$\begin{eqnarray*} p \equiv q \mod r \end{eqnarray*}$ gdw $\begin{eqnarray*} \exists k \in \mathbb{Z}: k\cdot r + p = q \end{eqnarray*}$

Bei dir sieht es aus als würdest du unbewiesene Äquivalenzen benutzen, nur weil sie richtig aussehen Augenzwinkern

19.06.2011, 14:35

Pascal95

Auf diesen Beitrag antworten »

Hmmm, dann würde ich es so machen...

$\begin{eqnarray*} a'\equiv a\mod n\quad\Leftrightarrow\quad \exists p\in\mathbb Z: a'-a=pn \end{eqnarray*}$
$\begin{eqnarray*} b'\equiv b\mod n\quad\Leftrightarrow\quad \exists q\in\mathbb Z: b'-b=qn \end{eqnarray*}$

$\begin{eqnarray*} a'+b'=a+b\mod n\quad\Leftrightarrow\quad (a'+b')-(a+b)=(a'-a)+(b'-b)=pn+qn=(p+q)n \end{eqnarray*}$
$\begin{eqnarray*} a'\cdot b'=a\cdot b\mod n\quad\Leftrightarrow\quad (a'\cdot b')-(a\cdot b)=(a'-a)\cdot (b'-b)=pn\cdot qn=(p\cdot q)n \end{eqnarray*}$

19.06.2011, 14:39

IfindU

Auf diesen Beitrag antworten »

Eine Kleinigkeit in der allerletzten Umformung ist falsch, aber nichts schlimmes. Freude

...Bzw. warum gilt die erste Gleichung bei der Multiplikation?

19.06.2011, 14:44

Pascal95

Auf diesen Beitrag antworten »

Oh, ja.
Da hab ich einfach Copy & Paste gemacht und + durch * getauscht - so siehts wohl besser aus:
$\begin{eqnarray*} a'\cdot b'=a\cdot b\mod n\quad\Leftrightarrow\quad (a'\cdot b')-(a\cdot b)=(a'-a)\cdot (b'-b)=pn\cdot qn=pqn^2 \end{eqnarray*}$
Edit: Das ist ja auch falsch... einen Moment bitte...
Edit2: Ich weiß nicht, wie man $\begin{eqnarray*} (a'\cdot b' ) - (a\cdot b) \end{eqnarray*}$ vereinfachen kann...

Sind die Definitionen eigentlich äquivalent zueinander:
$\begin{eqnarray*} p \equiv q \mod r \quad\Leftrightarrow\quad \exists k \in \mathbb{Z}: k\cdot r + p = q \end{eqnarray*}$
...und...
$\begin{eqnarray*} p \equiv q \mod r \quad\Leftrightarrow\quad \exists k \in \mathbb{Z}: k\cdot r = p-q \end{eqnarray*}$

Ich vergleiche also:
$\begin{eqnarray*} k\cdot r + p = q \end{eqnarray*}$ mit
$\begin{eqnarray*} k\cdot r = p-q \end{eqnarray*}$

Wenn man bei der ersten Gleichung "-p" rechnet, erhält man:
$\begin{eqnarray*} k\cdot r = q-p \end{eqnarray*}$

Da allerdings $\begin{eqnarray*} q-p \end{eqnarray*}$ den selben Betrag wie $\begin{eqnarray*} p-q \end{eqnarray*}$ hat, die Kongruenz eine Äquivalenzrelation ist, also insbesondere symmetrisch, sollte das do so gehen?

19.06.2011, 15:04

IfindU

Auf diesen Beitrag antworten »

Du weißt ja dass a' = k*n + a nach Definition, musst nur alles einsetzen. Wie Symmetrie helfen soll ist mir gerade nicht so wirklich klar.

$\begin{eqnarray*} (a'\cdot b')-(a\cdot b) = ((kn + a) \cdot (k'n + b)) - a\cdot b = \dots \end{eqnarray*}$

19.06.2011, 15:16

Pascal95

Auf diesen Beitrag antworten »

Ich meinte nicht, dass die Symmetrie helfen sollte, sondern, dass aufgrund der Symmetrie die Definitionen äquivalent sind:

Zitat:

$\begin{eqnarray*} p \equiv q \mod r \quad\Leftrightarrow\quad \exists k \in \mathbb{Z}: k\cdot r + p = q \end{eqnarray*}$
...und...
$\begin{eqnarray*} p \equiv q \mod r \quad\Leftrightarrow\quad \exists k \in \mathbb{Z}: k\cdot r = p-q \end{eqnarray*}$

$\begin{eqnarray*} (a'\cdot b')-(a\cdot b) = ((kn + a) \cdot (k'n + b)) - a\cdot b = (kk'n^2+knb+k'na+ab)-a\cdot b=kk'n^2+knb+k'na=??? \end{eqnarray*}$ ist Vielfaches von $\begin{eqnarray*} n \end{eqnarray*}$ , weil in jedem Summand ein $\begin{eqnarray*} n \end{eqnarray*}$ vorkommt.
$\begin{eqnarray*} kk'n^2+knb+k'na=n(kk'n+kb+k'a) \end{eqnarray*}$ könnte man auch schreiben..

19.06.2011, 15:19

IfindU

Auf diesen Beitrag antworten »

Ist nur noch ein Schritt - du solltest jetzt "schummeln" und nachsehen, was du eigentlich damit
zeigen wolltest und welche Form das Ergebnis dafür haben sollte Augenzwinkern

Edit: Genau, und damit hast du gezeigt, dass a*b und a'*b' kongruent zueinander sind. Freude

19.06.2011, 15:27

Pascal95

Auf diesen Beitrag antworten »

Ok, danke sehr.
Eigentlich hätte ich beim Nachweis von $\begin{eqnarray*} a'+b'\equiv a+b\mod n \end{eqnarray*}$ auch die Definition anwenden können (habe ich eher im Hinterkopf behalten, und so ausgeführt)
Damit meine ich man hätte auch so schreiben können:
$\begin{eqnarray*} a'+b'=a+b\mod n\quad\Leftrightarrow\quad (a'+b')-(a+b)=(kn+a+k'n+b)-(a+b)=kn+a+k'n+b-a-b=kn+k'n=n(k+k') \end{eqnarray*}$ wzbw

Eine Frage noch:
Gilt denn überhaupt $\begin{eqnarray*} x+y\mod z=x\mod z+y\mod z \end{eqnarray*}$ ?

19.06.2011, 15:38

IfindU

Auf diesen Beitrag antworten »

Ich weiß spontan nicht wirklich, was das heißen soll.
x+y mod z soll wohl die Restklasse sein, also die ganze Menge $\begin{eqnarray*} \{(x+y)+kz | k \in \mathbb{N}\} \end{eqnarray*}$ .
Und rechts hast du also $\begin{eqnarray*} [\underbrace{\{x+kz | k \in \mathbb{N}\}}_{[x]} + \underbrace{\{y+kz | k \in \mathbb{N}\}}_{[y]} \end{eqnarray*}$ , also eine Summe von Mengen. Du müsstest erstmal definieren was du damit überhaupt meinst, üblicherweise die Menge $\begin{eqnarray*} \{x+y | x \in [x], y \in [y]\} \end{eqnarray*}$ .

Und dann würde die Gleichung gelten, aber man sollte sie nicht hinschreiben wenn man nicht weiß, was man damit macht. Und ich denke nicht, dass du dir dabei die nötigen Gedanken gemacht hast Augenzwinkern

Edit: Als kleines Beispiel, wenn mans "naiv" machen würde, x = y = 1, n = 2.
Links steht x+y mod 2 = 1 +1 mod 2 = 2 mod 2 = 0.
Rechts steht 1 mod 2 + 1 mod 2 = 1 + 1 = 2.

Der Fehler hier ist dass man sich willkürlich Repräsentaten der Menge wählt.

19.06.2011, 15:45

Pascal95

Auf diesen Beitrag antworten »

Ne, so hab ich nicht gedacht:

Ich frage mich, ob gilt

Zitat:

Wenn $\begin{eqnarray*} x,y,z\in\mathbb N \end{eqnarray*}$ , dann gilt $\begin{eqnarray*} x+y\mod z=x\mod z+y\mod z \end{eqnarray*}$ .

Beispiel:
$\begin{eqnarray*} x=5, y=12, z=3 \end{eqnarray*}$
$\begin{eqnarray*} 5+12\mod 3=5\mod 3+12\mod 3 \end{eqnarray*}$
$\begin{eqnarray*} 17\mod 3=2+0 \end{eqnarray*}$
$\begin{eqnarray*} 2=2\ \checkmark \end{eqnarray*}$

Edit:
Habe nun deinen Edit gesehen und nun ist mir klar, dass die o.g. Aussage falsch ist! (war nur eine Vermutung von mir unglücklich

)

Edit2:
Bei der Restklasse käme aber $\begin{eqnarray*} \{(x+y)+kz | k \in \mathbb{Z}\} \end{eqnarray*}$ . (Z statt N) Augenzwinkern

So meinte ich das aber sowieso nicht, habe den Fehler ja bemerkt anhand deines Gegenbsps.

19.06.2011, 15:51

IfindU

Auf diesen Beitrag antworten »

Öhm...natürlich muss da ein Z hin... wollte nur deine Aufmerksamkeit testen Hammer

19.06.2011, 15:52

Pascal95

Auf diesen Beitrag antworten »

Hehe, klar smile

Nun hat sich aber alles geklärt und ich möchte mich ganz herzlich für deine Hilfe bedanken !

Liebe Grüße

19.06.2011, 15:55

IfindU

Auf diesen Beitrag antworten »

Gerne

Neue Frage »

Antworten »

Modulo Rechnung

Verwandte Themen