Beweisen oder widerlegen: n(n+1) oder n(n+1)+1 durch 3 teilbar?

Question

Hallo :)

Ich soll beweisen oder widerlegen, dass

n * (n + 1) durch 3 teilbar ist

oder

n * (n + 1) + 1 durch 3 teilbar ist (für alle n ∈ ℕ).

Ich habe das bereits mit vollständiger Induktion versucht, bin dann aber beim Induktionsschritt mit n + 1 nicht weitergekommen. Weiß allerdings auch nicht genau, wie ich das mit anderen Beweismethoden angehen könnte..

Ich wäre sehr dankbar, wenn mir jemand helfen könnte :)

Answer 1

Hallo KamikazeCat,

betrachte eine natürliche Zahl \(n \in \mathbb{N}\) und bilde ihren Rest bei der Division durch 3 bzw. beim Bilden des Modulo 3. Da gibt es nur drei Möglichkeiten:

$$n \equiv x \mod 3 \quad x\in \{0,1,2\}$$

Setze nun jeden der drei Fälle in einen der beiden Terme ein. Für den ersten Term \(n(n+1)\) wähle ich \(x=0\) und \(x=2\). Im Fall von \(x=0\) ist \(n\) durch 3 teilbar und für \(x=2\) ist \(n+1\) durch 3 teilbar und damit auch das Produkt von \(n(n+1)\).

Für den zweiten Term bleibt \(x=1\). Es gilt

$$n \equiv 1 \mod 3 \quad \rightarrow  n(n+1)+1 \equiv 0 \mod 3$$

Beweis: Mit \(n \equiv 1 \mod 3\) kann man \(n\) schreiben als \(n=3k+1\) mit \(k \in \mathbb{N}_0\). Das setze ich ein und erhalte:

$$n(n+1)+1 = (3k+1)(3k+2)+1=9k^2 + 9k + 3=3(3k^2+3k+1)$$

und das ist durch 3 teilbar.

Gruß Werner

Comments

Vielen Dank, das macht absolut Sinn :)

---

Hi,

diesen Schritt kann ich noch nicht so ganz nachvollziehen:

Beweis: Mit n = 1  mod 3   kann man n schreiben als   n=3k+1.

Wie kommt man darauf?

MFG

---

n = 1 mod 3 bedeutet, dass ein Rest von 1 zurück bleibt, wenn man n durch 3 teilt. Also kann man n zerlegen in eine Zahl, die durch 3 teilbar ist (das wäre dann das 3k, mit Rest 0) und die 1 (mit Rest 1). Insgesamt also 3k + 1.

Ich hoffe, das war einigermaßen verständlich :)

---

Hallo holgerson,

Wenn \(n \equiv 1 \mod 3\) ist, dann heißt das doch, dass bei der Division von \(n\) durch 3 der Rest 1 verbleibt. Also z.B. \(25:3=8 \text{ Rest }1\). Das bedeutet aber auch, dass nach Subtraktion von \(n-1\) eine Zahl verbleibt, die ohne Rest durch 3 teilbar ist. Also könnte man doch schreiben \(n-1=3k\). Im Fall von \(n=25\) ist das \(25-1=3\cdot 8\). Und statt  \(n-1=3k\) schreibe ich \(n=3k+1\).

Alles klar?

Gruß Werner

---

Macht Sinn, vielen Dank :D

MFG

Answer 2

Hi ich zeige anhand der vollständigen Induktion die Teilbarkeit von n(n+1)+1 durch 3:

IA: n(n+1)+1
setze n = 1
1(1+1)+1= 3
3/3 = 1 ist also schon mal teilbar...

IV: Für ein beliebiges aber festes n Element der Natürlichen Zahlen gelte die Behauptung

IS: n -> n+1
(n+1)(n+1+1)+1 = (n+1)(n+2)+1
= n^2 +2n +n +2 +1
= n^2 +3n +3
= 3n(n/3 +1) +3
Ein Produkt ist durch 3 teilbar wenn einer der Faktoren durch drei teilbar ist!

Das war es :)

Comments

Der Term \(3n(n/3 + 1) +3\) ist nur genau dann durch 3 teilbar, wenn \(n\) durch 3 teilbar ist. Der Beweis ist somit nicht vollständig.

---

Danke, vielleicht hilft mir das bei meinem Problem weiter. (Auch wenn es nicht vollständig ist ;) )

Answer 3

Du könntest mal ein paar Werte für n einsetzen...

Comments

Hab ich schon und bin dann zu dem Schluss gekommen, dass die Aussage wahr ist. Aber wie beweise ich das? Ich kann es ja nicht nur mit Beispielen beweisen, weil ich so nicht alle n ∈ ℕ abdecke...

---

Du könntest beide Folgen mal untereinander schreiben, dann siehst du vielleicht, warum die Aussage gilt.

---

Hmm.. also mir ist jetzt aufgefallen, dass die erste Formel immer gerade Ergebnisse liefert und die zweite Formel immer ungerade. Außerdem, dass immer abwechselnd die erste Formel zweimal eine wahre Aussage liefert und die zweite Formel einmal (dann wieder die erste Formel zweimal usw...). Bin mir aber nicht ganz sicher, ob du darauf hinauswolltest... :D

---

Ja und jetzt betrachte mal die Dreierreste der Folgenglieder...

Answer 4

a) Gegenbeispiel: n=1

1*2 =2 

3 ist kein Teiler von 2.

b) analog z.B. n=2

Comments

Empfehle :  Du schreibst "Ich habe die Aufgabe nicht verstanden" und ziehst deine Antwort zurück.