Kongruenzen

Neue Frage »

21.04.2009, 21:33

lamodus

Auf diesen Beitrag antworten »

Kongruenzen

Ich soll folgendes beweisen: (n^3 + 5n + 10) mod 3 = 1

zuerst einmal: was bedeutet dieses mod?

21.04.2009, 21:44

Elvis

Auf diesen Beitrag antworten »

mod heißt modulo, das hilft dir aber noch nicht weiter.
Definition $\begin{eqnarray*} a\equiv b\,(mod\, c) \end{eqnarray*}$ genau dann, wenn $\begin{eqnarray*} c|(a-b) \end{eqnarray*}$ . "|" ist das Symbol für Teiler ohne Rest.
Du sollst zeigen, daß $\begin{eqnarray*} n^3+5n+10 \end{eqnarray*}$ bei Division durch 3 immer (d.h. für jedes n) den Rest 1 hat.

21.04.2009, 21:57

lamodus

Auf diesen Beitrag antworten »

okay danke..hast du vielleicht einen tip, wie ich das machen könnte? Mir fällt grad nix ein.

es gibt einfach immer 1+eine Zahl die durch 3 teilbar ist.

aber wieso genau find ich nicht raus. Wird halt was mit der potenz und dem addieren und so zu tun haben, dass immer eine durch drei teilbare Zahl+1 rauskommt.

Gibt ja auch solche Tricks, wo man zu Beginn eine beliebige Zahl zw 1 und 10 nennt und dann durch versch. rechenoperationen immer auf selbe resultat kommt, oder so Big Laugh

21.04.2009, 22:52

Airblader

Auf diesen Beitrag antworten »

Zeige, dass $\begin{eqnarray*} n^3 + 5n + 9 \end{eqnarray*}$ für alle n restlos durch 3 teilbar ist. Möglich zB über Induktion.

air

21.04.2009, 22:56

lamodus

Auf diesen Beitrag antworten »

Was ist Induktion? Sorry, noch nie davon gehört..

21.04.2009, 22:57

Airblader

Auf diesen Beitrag antworten »

Okay, gehen wir es anders an.
Du kennst weder die Vollständige Induktion, noch weißt du, was modulo überhaupt bedeutet - willst aber eine Aufgabe darüber lösen.

Stellen wir also folgende Frage: Welche Mittel hast du überhaupt zur Verfügung und warum hast du eine Aufgabe, deren Thematik du nicht kennst?

air

21.04.2009, 23:04

lamodus

Auf diesen Beitrag antworten »

Weil ich eine alte Maturaprüfung lösen muss und hier in der Schweiz jeder Lehrer für seine Klasse eine eigene Maturaprüfung schreiben kann. (Und die, die ich habe ist von einem anderen Lehrer.)

Ist es anders nicht zu lösen? Also ohne das Induktionszeug.. Denn dann müsste ich das nat. meinem Lehrer sagen.

Aber vielleicht geht es ja anders. Oder es ist irgendwie ein Spezialfall wo es leicht geht oder so..

21.04.2009, 23:12

Airblader

Auf diesen Beitrag antworten »

Induktion wäre zumindest eine sehr simple Möglichkeit, das Ganze anzugehen. Sicherlich gibt es noch eine andere, aber mir fällt gerade keine ein (ist ja auch spät Augenzwinkern

).
Aber selbst wenn, so befürchte ich, dass sie in die Trickkiste der Modulorechnung greift (simples Faktorisieren geht hier leider nicht). Und da muss ich mich wiederholen:

Es macht keinen Sinn, eine Aufgabe zu bearbeiten, wenn man eigentlich gar nicht weiß, um was es da geht. Euer Lehrer kann kaum verlangen, dass ihr eine Aufgabe zur Modulorechnung löst, wenn ihr das nicht einmal hattet.

air

21.04.2009, 23:15

lamodus

Auf diesen Beitrag antworten »

ok, dann teil ich ihm das mal mit.

22.04.2009, 20:12

Elvis

Auf diesen Beitrag antworten »

Kongruenzen
Bitte, nicht so. unglücklich

Nicht über vollständige Induktion. unglücklich

Das geht ganz anders viel besser. smile

Fangen wir mal vorne an, und erklären ein bißchen mehr über Kongruenzrelationen, denn genau darum geht es in dieser Aufgabe.

Definition 1: Eine Kongruenzrelation " $\begin{eqnarray*} \equiv \end{eqnarray*}$ " ist eine Äquivalenzrelation "~" , die mit den Operationen auf einer algebraischen Struktur verträglich ist.

Das bekannteste Beispiel einer Kongruenzrelation ist gerade diese "Kongruenz mod m" in ganzen Zahlen $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ . Die Definition hatte ich bereits gepostet.
Definition 2: Für ganze Zahlen $\begin{eqnarray*} a,b,m \in \mathbb Z \end{eqnarray*}$ ist $\begin{eqnarray*} a\equiv b \mod m \Leftrightarrow m|(a-b) \end{eqnarray*}$
Das ist dann gleichbedeutend damit, daß $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ bei Division durch $\begin{eqnarray*} m \end{eqnarray*}$ denselben Rest haben. Also heißt $\begin{eqnarray*} x\equiv 1\mod m \end{eqnarray*}$ auch $\begin{eqnarray*} x=m\cdot y+1 \end{eqnarray*}$ .

Es ist allgemein bekannt, daß folgendes gilt:
Satz 3: Bei der Division durch $\begin{eqnarray*} m \end{eqnarray*}$ gibt es genau $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene Reste, nämlich $\begin{eqnarray*} 0,1,...,m-1 \end{eqnarray*}$

Jetzt kommt der große Trick mit der "algebraischen Struktur". In ganzen Zahlen $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ kann man addieren ( $\begin{eqnarray*} + \end{eqnarray*}$ ) und multiplizieren ( $\begin{eqnarray*} \cdot \end{eqnarray*}$ ) , und die Kongruenz $\begin{eqnarray*} \mod c \end{eqnarray*}$ ist damit verträglich, das heißt
Satz 4: $\begin{eqnarray*} a\equiv b\mod m \end{eqnarray*}$ und $\begin{eqnarray*} c\equiv d\mod m \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} a+b\equiv c+d\mod m \end{eqnarray*}$ und $\begin{eqnarray*} a\cdot c\equiv b\cdot d\mod m \end{eqnarray*}$

So, und nun lösen wir die Aufgabe.

(i) $\begin{eqnarray*} 10/3=3\, Rest\, 1\Leftrightarrow 10\equiv 1\mod 3 \end{eqnarray*}$

(ii) Wenn wir beweisen können, daß $\begin{eqnarray*} n^3+5n\equiv 0\mod 3 \end{eqnarray*}$ , sind wir fertig, denn dann gilt nach Satz 4
$\begin{eqnarray*} n^3+5n\equiv 0\mod 3 \end{eqnarray*}$ und $\begin{eqnarray*} 10\equiv 1\mod 3 \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} n^3+5n+10\equiv 0+1\equiv 1\mod 3 \end{eqnarray*}$

(iii) Nach Satz 3 ergibt die Division von $\begin{eqnarray*} n \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ die drei möglichen Reste 0,1,2.

Im folgenden wenden wir immer wieder Satz 4 an:
(iv) $\begin{eqnarray*} n\equiv 0\mod 3\Rightarrow n^3+5n=n\cdot (n^2+5)\equiv 0\cdot(n^2+5)\equiv 0\mod 3 \end{eqnarray*}$
(v) $\begin{eqnarray*} n\equiv 1 \mod 3\Rightarrow n^3+5n\equiv 1^3+5\cdot 1\equiv 6\equiv 0\mod 3 \end{eqnarray*}$
(vi) $\begin{eqnarray*} n\equiv 2\mod 3\Rightarrow n^3+5n\equiv 2^3+5\cdot 2\equiv 8+10 \equiv 18 \equiv 0\mod 3 \end{eqnarray*}$

Damit sind wir fertig Prost

Für jede ganze Zahl $\begin{eqnarray*} n \in \mathbb Z \end{eqnarray*}$ ist $\begin{eqnarray*} n^3+5n\equiv 0\mod 3 \end{eqnarray*}$ , außerdem ist $\begin{eqnarray*} 10\equiv 1\mod 3 \end{eqnarray*}$ , also ist nach Satz 4 immer $\begin{eqnarray*} n^3+5n+10\equiv 1\mod 3 \end{eqnarray*}$

P.S.: Für Schüler, die sich mit Kongruenzrechnung beschäftigt haben, ist das alles selbstverständlich, und die Lösung der Aufgabe beschränkt sich auf die Schritte (i)-(vi). Wer sich nicht mit Kongruenzrechnung auskennt, hat keine Chance.

P.P.S.:Es tut mir leid, daß ich in diesem speziellen Fall die komplette Lösung dargestellt habe, aber ich hatte den deutlichen Eindruck, daß wir sonst nie fertig werden.

22.04.2009, 20:17

domelius

Auf diesen Beitrag antworten »

RE: Aufgabe einer Maturaprüfung
Zeige, dass für jede ganze n, n(n^2+5) durch 3 teilbar ist:

Jede ganze Zahl n kann man in einer der folgenden Formen darstellen:
n=3k, n=3k+1, n=3k+2, wo k eine ganze Zahl ist.

Fall 1: 3k(9k^2+5) ist durch 3 teilbar

Fall 2: (3k+1)(9k^2+6k+6) ist durch 3 teilbar

Fall 3: (3k+2)(9k^2+12k+9) ist durch 3 teilbar

22.04.2009, 20:18

Elvis

Auf diesen Beitrag antworten »

Kongruenzrechnung
Goethes Faust: "Aus 10 mach 1, das ist das Hexeneinmaleins". Augenzwinkern

22.04.2009, 22:41

Elvis

Auf diesen Beitrag antworten »

Kongruenzrechnung
Mit "ein bißchen mehr" Mathematik gibt es eine kurze Lösung der Aufgabe. Kleiner Satz von Fermat $\begin{eqnarray*} \Rightarrow\,n^3\equiv n\mod3 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\,n^3+5n\equiv n+5n\equiv 6n \equiv 0\mod 3 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\,n^3+5n+10\equiv 10\equiv 1\mod 3 \end{eqnarray*}$

Wer kann's noch kürzer ? Big Laugh

23.04.2009, 18:24

Airblader

Auf diesen Beitrag antworten »

RE: Kongruenzrechnung

Zitat:

Original von Elvis
Wer kann's noch kürzer ? Big Laugh

"Das Problem ist trivial." Augenzwinkern

air

27.04.2009, 05:08

lamodus

Auf diesen Beitrag antworten »

Hab gar nicht gesehen, dass ihr noch weitergemacht habt.. Echt super! Danke für die vielen Lösungen etc. Versteh sie zwar nicht alle, aber was solls... Freude

27.04.2009, 19:47

Elvis

Auf diesen Beitrag antworten »

kongruenzrechnung
Hallo, lamodus schön, dass du wieder da bist. Wink

Ich kann dir das Verständnis vielleicht noch ein wenig erleichtern, indem ich den kleinen Satz von Fermat weglasse, und direkt rechne: bei Division durch 3 gibt es als Rest nur 0, 1 oder 2

wenn $\begin{eqnarray*} n \end{eqnarray*}$ durch 3 teilbar ist, dann auch $\begin{eqnarray*} n^3 \end{eqnarray*}$
wenn die Division $\begin{eqnarray*} n \end{eqnarray*}$ durch 3 den Rest 1 hat, dann auch die Division $\begin{eqnarray*} n^3 \end{eqnarray*}$ durch 3
wenn die Division $\begin{eqnarray*} n \end{eqnarray*}$ durch 3 den Rest 2 hat, dann auch die Division $\begin{eqnarray*} n^3 \end{eqnarray*}$ durch 3

und das heißt eben in Formeln $\begin{eqnarray*} n^3\equiv n\mod 3 \end{eqnarray*}$ , und der Rest ist ein Kinderspiel. smile

Neue Frage »

Antworten »

Kongruenzen

Verwandte Themen