Divisionsalgorithmus

21.09.2010, 16:04

kepheus1

Divisionsalgorithmus

Edit (mY+): Bitte KEINE Hilfeersuchen in der Überschrift und auch sonst nicht! Titel modifiziert.

Hallo!
Ich bearbeite gerade eine Aufgabe, die einer anderen Aufgabe ähnelt, von der ich den Lösungsweg habe, den ich allerdings nicht vollständig nachvollziehen kann. Bei der Aufgabe ging es um den Divisionsalgorithmus bzw. den Rest einer Division. Ich weiß aber nicht, worum es bei der folgenden Aufgabe geht.
Die Aufgabe ist:

$\begin{eqnarray*} Y = \{ 1, 2, 3 \} \end{eqnarray*}$

$\begin{eqnarray*} p: \mathbb{Z} \rightarrow Y \end{eqnarray*}$

$\begin{eqnarray*} z \mapsto r \end{eqnarray*}$

$\begin{eqnarray*} z = 3 * q + r, q \in \mathbb{Z} \end{eqnarray*}$

$\begin{eqnarray*} R_p := \Big\{ (z_1, z_2) \in \mathbb{Z} \times \mathbb{Z} \; | \; r_1 = r_2 \Big\} \subset \mathbb{Z} \times \mathbb{Z} \end{eqnarray*}$

Danach folgen die Unteraufgaben a) bis d). Allerdings ist mir schon die Definition nicht klar. Ich schreibe mal auf, was ich denke.

- Y ist eine Menge mit den Elementen 0, 1 und 2
- p ist eine Abbildung, die jeweils einer ganzen Zahl ein Element aus Y (also 0, 1 oder 2) zuweist
- z (aus Z) wird abgebildet auf r (aus Y)
- und z entspricht 3 * q + r

Also:

$\begin{eqnarray*} R_p := \Big\{ (0, 0), (4, 4), (8, 8) \Big\} \end{eqnarray*}$

Stimmt das so weit? Mein Hauptproblem ist, dass ich nicht genau weiß, welchen Wert q jeweils hat. Angenommen hab ich jetzt jeweils q = r.

Danke!
Kai

21.09.2010, 17:24

Cugu

Auf diesen Beitrag antworten »

Zitat:

Y ist eine Menge mit den Elementen 0, 1 und 2

Können wir uns auf $\begin{eqnarray*} Y = \{ 0, 1, 2 \} \end{eqnarray*}$ einigen?

Zitat:

p ist eine Abbildung, die jeweils einer ganzen Zahl ein Element aus Y (also 0, 1 oder 2) zuweist

Ja.

Zitat:

z (aus Z) wird abgebildet auf r (aus Y)

Ja.

Zitat:

und z entspricht 3 * q + r

Hier wäre es natürlich wünschenswert $\begin{eqnarray*} r \end{eqnarray*}$ in Abhängigkeit von $\begin{eqnarray*} z \end{eqnarray*}$ zu kennen. Gegeben ist aber nur eine implizite Darstellung für $\begin{eqnarray*} r \end{eqnarray*}$ .

Es gilt
$\begin{eqnarray*} \Big\{ (z_1, z_2) \in \mathbb{Z} \times \mathbb{Z} \; | \; r_1 = r_2 \Big\} \supsetneqq \Big\{ (0, 0), (4, 4), (8, 8) \Big\} \end{eqnarray*}$ ,
aber keineswegs Gleichheit der beiden Mengen.

Zitat:

Mein Hauptproblem ist, dass ich nicht genau weiß, welchen Wert q jeweils hat. Angenommen hab ich jetzt jeweils q = r.

Nein, das ist falsch. Ein paar Beispiele $\begin{eqnarray*} (z=1,5,10) \end{eqnarray*}$ :

$\begin{eqnarray*} 1=3\cdot 0 + 1 \Rightarrow q=0, r=1 \end{eqnarray*}$

$\begin{eqnarray*} 5=3\cdot 1 + 2 \Rightarrow q=1, r=2 \end{eqnarray*}$

$\begin{eqnarray*} 10=3\cdot 3 + 1 \Rightarrow q=3, r=1 \end{eqnarray*}$

21.09.2010, 17:59

kepheus1

Auf diesen Beitrag antworten »

Zitat:

Original von Cugu

Zitat:

Y ist eine Menge mit den Elementen 0, 1 und 2

Können wir uns auf $\begin{eqnarray*} Y = \{ 0, 1, 2 \} \end{eqnarray*}$ einigen?

Klar, können wir. Ist mein sprachlicher Ausdruck dafür falsch oder aus welchem Grund legst du darauf wert?

Zitat:

Es gilt
$\begin{eqnarray*} \Big\{ (z_1, z_2) \in \mathbb{Z} \times \mathbb{Z} \; | \; r_1 = r_2 \Big\} \supsetneqq \Big\{ (0, 0), (4, 4), (8, 8) \Big\} \end{eqnarray*}$ ,
aber keineswegs Gleichheit der beiden Mengen.

Hm, ok. Eine Gleichheit der Mengen wollte ich damit auch nicht zum Ausdruck bringen (trotzt des gleichen Index, ist natürlich ein Fehler). Ich wollte ausdrücken, dass die Menge auf der rechten Seite aus der linken "hervorgeht", wenn man Y={0, 1, 2} annimmt und damit r=0, r=1 und r=2 und nur für diese drei r's die Menge "hinschreibt".
Wenn es meine nicht ist, gibt es dann überhaupt eine äquivalente Menge für R_p mit konkreten Werten? (Konkrete Werte sind für mich Zahlen, so dass ich anschließend leichter überprüfen kann, ob diese Menge symmetrisch ist, etc. Geht natürlich auch ohne. Aber das ist die Aufgabe a)).

Zitat:

Mein Hauptproblem ist, dass ich nicht genau weiß, welchen Wert q jeweils hat. Angenommen hab ich jetzt jeweils q = r.

Hm ok, dann verstehe ich es komplett gar nicht und muss nochmal alles von vorne betrachten. Das bringt mich aber trotzdem erstmal weiter.

Danke vielmals.

21.09.2010, 18:28

Cugu

Auf diesen Beitrag antworten »

Du hast oben $\begin{eqnarray*} Y = \{ 1, 2, 3 \} \end{eqnarray*}$ geschrieben, das meinte ich.

Sei es drum.
z.B. ist $\begin{eqnarray*} p(1)=p(10) \end{eqnarray*}$ und folglich sind $\begin{eqnarray*} (1,10) \in R_p \end{eqnarray*}$ und $\begin{eqnarray*} (10,1) \in R_p \end{eqnarray*}$ . Das Problem mit konkreten Werte ist folgendes: Die Menge ist nicht endlich!

Natürlich ist die Menge in dem Sinne symmetrisch, dass $\begin{eqnarray*} (a,b)\in R_p \Rightarrow (b,a)\in R_p \end{eqnarray*}$ . Dies liegt einfach daran, dass die Relation $\begin{eqnarray*} = \end{eqnarray*}$ symmetrisch ist.

$\begin{eqnarray*} p \end{eqnarray*}$ macht nicht anderes als einer ganzen Zahl $\begin{eqnarray*} z \end{eqnarray*}$ den Rest $\begin{eqnarray*} r \end{eqnarray*}$ , der bei ganzzahliger Division durch $\begin{eqnarray*} 3 \end{eqnarray*}$ verbleibt, zuzuordnen. Das hast du bestimmt früher beim schriftlichen Dividieren auch schon mal gemacht.

21.09.2010, 19:32

kepheus1

Auf diesen Beitrag antworten »

Hallo,
ich glaube, dass ichs jetzt im Großen und Ganzen verstanden habe. :-)
Bis auf das q:

Zitat:

Original von Cugu
$\begin{eqnarray*} 1=3\cdot 0 + 1 \Rightarrow q=0, r=1 \end{eqnarray*}$

$\begin{eqnarray*} 5=3\cdot 1 + 2 \Rightarrow q=1, r=2 \end{eqnarray*}$

$\begin{eqnarray*} 10=3\cdot 3 + 1 \Rightarrow q=3, r=1 \end{eqnarray*}$

Hier ist jeweils z bekannt. q und r nicht. Oder weißt du r schon vorher und stellst auf q um?

Danke nochmal.

21.09.2010, 20:34

Cugu

Auf diesen Beitrag antworten »

Naja, du kannst dir das doch so vorstellen:

Du fängst an mit $\begin{eqnarray*} z=10 \end{eqnarray*}$ .
Ist $\begin{eqnarray*} 10 \in Y \end{eqnarray*}$ ? Nein!
Also ziehen wir $\begin{eqnarray*} 3 \end{eqnarray*}$ ab.

$\begin{eqnarray*} 10=1\cdot3+7 \end{eqnarray*}$
Ist $\begin{eqnarray*} 7 \in Y \end{eqnarray*}$ ? Nein!
Also ziehen wir $\begin{eqnarray*} 3 \end{eqnarray*}$ ab.

$\begin{eqnarray*} 10=2\cdot3+4 \end{eqnarray*}$
Ist $\begin{eqnarray*} 4 \in Y \end{eqnarray*}$ ? Nein!
Also ziehen wir $\begin{eqnarray*} 3 \end{eqnarray*}$ ab.

$\begin{eqnarray*} 10=3\cdot3+1 \end{eqnarray*}$
Ist $\begin{eqnarray*} 1 \in Y \end{eqnarray*}$ ? Ja!

Zumindest für natürliche Zahlen kann man per Induktion zeigen, dass das immer klappt. Für negative ganze Zahlen müsste man das noch ein bisschen modifizieren.

21.09.2010, 20:50

kepheus1

Auf diesen Beitrag antworten »

Achso, jetzt hab ichs verstanden. -.-
Niemals hätte ich gesehen, dass es sich hierbei um eine Teilung handelt. Schließlich wird addiert. Aber deswegen frage ich ja.

Ich habe nebenbei auch schonmal weitergerechnet. Bei den Teilaufgaben geht es darum zu überprüfen, ob R_p reflexiv, symmetrisch und transitiv ist. Ich würde bei allen drei Eigenschaften sagen, dass sie zutreffen. Die Symmetrie hast du ja oben schon erklärt.

Die Reflexivität ist eigentlich auch klar. Ich weiß nur oft nicht, wie ich das beweisen soll ("Zeigen Sie"). Eigenltich gar nicht. Es ist doch klar, dass das r entsprechend für z das gleiche ist wie für z und (z, z) deswegen Element von R ist.

Bei der Transitivität finde ich keine Tupel, für die es nicht gilt. Aber das ist natürlich kein Beweis, dass es nicht doch welche gibt.
(Hab mir beispielsweise (3, 6), (6, 9) und (3, 9) herausgesucht und es anhand derer erklärt.) Die Transitivität wird nur gebrochen, wenn ich Tupel verwende, die sowieso nicht Elemente der Menge sind. Und um die geht es ja nicht.

Danke für deine Unterstützung.

Neue Frage »

Antworten »

Divisionsalgorithmus

Verwandte Themen