Modulo Rechnung (Beweis)

02.02.2014, 13:59

samsonB

Modulo Rechnung (Beweis)

Meine Frage:
Hallo,

Ich komme auf kein Ergebnis bei dieser Aufgabe mit Restklassenrechnung:

Beweisen sie:

$\begin{eqnarray*} n^{3}\equiv n \quad mod \ 6 \quad \forall \ n \in \mathbb N \end{eqnarray*}$

Meine Ideen:
Das einzige was mit da einfällt, ist das direkte Anwenden der Definition:

$\begin{eqnarray*} n^{3}\equiv n \quad mod \ 6 \ \Leftrightarrow 6 \ teilt \ n^{3}-n \end{eqnarray*}$

Aber warum nun 6 und wie man das so umformt dass es die Aussage beweist, ist mir ein Rätsel!?

02.02.2014, 14:02

dastrian

Auf diesen Beitrag antworten »

RE: Modulo Rechnung (Beweis)
Vielleicht nicht die eleganteste, aber einfachste Lösung wäre, die verschiedenen Fälle einfach durchzugehen.

Es reicht ja, die Behauptung für $\begin{eqnarray*} n = 0,1,2,3,4,5 \end{eqnarray*}$ zu beweisen. (Warum?)

02.02.2014, 14:08

10001000Nick1

Auf diesen Beitrag antworten »

@dastrian: Findest du vielleicht vollständige Induktion eleganter? smile

Wenn ja, könntest du es auch damit machen.

02.02.2014, 14:08

samsonian

Auf diesen Beitrag antworten »

ok, stimmt. das würde sogar gar nicht mal so lange dauern.

02.02.2014, 14:12

samsonian

Auf diesen Beitrag antworten »

Zitat:

Original von 10001000Nick1
@dastrian: Findest du vielleicht vollständige Induktion eleganter? smile

Wenn ja, könntest du es auch damit machen.

ich habe schon an induktion gedacht aber da sehe ich keinen fortschritt außer, dass ich da nun "6 teilt (n+1) hoch3 - (n+1)" stehen habe. Es gibt ja keine "linke seite" die ich umformen kann um die induktionsvorraussetzung zu verwenden, oder doch?

02.02.2014, 14:14

10001000Nick1

Auf diesen Beitrag antworten »

Dann forme doch einfach mal $\begin{eqnarray*} (n+1)^3-(n+1) \end{eqnarray*}$ ein bisschen um (erstmal die Klammern auflösen).

02.02.2014, 14:20

samsonian

Auf diesen Beitrag antworten »

Wenn ich mich nicht verrechnet habe...

$\begin{eqnarray*} (n+1)^{3}-(n+1)=n^{3}+3n^{2}+3n+1-(n+1)= n^{3}+3n^{2}+2n \end{eqnarray*}$

02.02.2014, 14:23

10001000Nick1

Auf diesen Beitrag antworten »

Du hast dich nicht verrechnet.
Und jetzt ist $\begin{eqnarray*} n^3+3n^2+2n=(n^3-n)+(3n^2+3n). \end{eqnarray*}$

Weißt du, wie es jetzt weiter geht?

02.02.2014, 14:32

samsonian

Auf diesen Beitrag antworten »

Ich sehe, dass der Term nun so umgeformt ist dass $\begin{eqnarray*} n^{3}-n \end{eqnarray*}$ darin auftaucht. Ist das unsere Induktionsvorrassetzung? Ich weiss nicht genau "wohin" wir umformen...

02.02.2014, 14:35

10001000Nick1

Auf diesen Beitrag antworten »

Eigentlich braucht man jetzt nicht mehr viel umformen.

Wir haben ja jetzt $\begin{eqnarray*} (n+1)^3-(n+1)=(n^3-n)+(3n^2+3n). \end{eqnarray*}$
Der erste Summand ist laut Induktionsvoraussetzung durch 6 teilbar. Und $\begin{eqnarray*} (3n^2+3n)=3(n^2+n) \end{eqnarray*}$ ist ebenfalls durch 6 teilbar, weil $\begin{eqnarray*} (n^2+n) \end{eqnarray*}$ durch 2 teilbar ist (müsste man evtl. auch noch zeigen).
Damit ist dann auch die Summe durch 6 teilbar.

02.02.2014, 14:39

samsonian

Auf diesen Beitrag antworten »

Die Argumentation versteh ich. Thanks. Ich werde mich mal erkundigen, welcher Lösungsweg für diese Aufgabe angedacht war.

02.02.2014, 14:43

10001000Nick1

Auf diesen Beitrag antworten »

Mir ist jetzt noch ein Beweis eingefallen, den ich noch "schöner" (und vor allem kürzer) finde.

$\begin{eqnarray*} n^3-n=n(n^2-1)=n(n-1)(n+1). \end{eqnarray*}$
Das ist also ein Produkt dreier aufeinanderfolgender ganzer Zahlen. Davon ist mindestens eine durch 2 teilbar und genau eine durch 3 teilbar. D.h. das Produkt muss durch 6 teilbar sein.

02.02.2014, 14:54

samsonian

Auf diesen Beitrag antworten »

Das ist natürlich sehr schick und macht Sinn!!!! smile

02.02.2014, 21:34

RavenOnJ

Auf diesen Beitrag antworten »

Im Sinne der Moulo-Rechnung könntest du auch beweisen, dass $\begin{eqnarray*} \forall n\in \mathbb N: n^3=n\mod 2\land n^3=n\mod 3 \end{eqnarray*}$ . Daraus folgt nämlich deine Behauptung.

Neue Frage »

Antworten »

Modulo Rechnung (Beweis)

Verwandte Themen