Diskrete Strukturen, Komb

Question

Aufgabe:

Beweisen Sie: Für alle n ∈ N ist ggT(n + 1, n² − n + 1) entweder 1 oder 3 .

Problem/Ansatz:

Ich wollte gern fragen, ob meine Lösung richtig ist.

Sei d = ggT(n + 1, n² − n + 1) dann  d | n + 1 und d | n² - n + 1,

Dann gilt: d | n + 1 + n² - n + 1 <=> n² + 2, d.h d | n² + 2 und

d | n² - n + 1 - n - 1 <=> d | n² - 2n

D.h 3 teilt nicht n + 1 und 3 teilt nicht n² − n + 1

Comments

ggT(n + 1, n² - n + 1) = ggT(n + 1, (n² - n + 1) - (n + 1)·(n - 2)) = ggT(n + 1, 3).

---

Danke für die Rückmeldung, Wenn Du mir sagen könntest, was genau hier ggT(n + 1, (n2 - n + 1) - (n + 1)·(n - 2)) passiert, wäre sehr hilfreich.. vielen Dank

---

Allgemein gilt ggT(x, y) = ggT(x, y - z·x) für x,y,z ∈ ℤ.

---

super, vielen Dank