Beweisen: Teilbarkeit und ggT

Question

Aufgabe:

Beweisen Sie:

Für alle n ∈ N gilt: ggT(n² - n + 1, n + 1) ∈ {1,3}

Problem/Ansatz:

Hallo,

Können Sie mir bitte sagen, wie ich das lösen kann? Vielen Dank

Comments

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

Answer 1

Bestimme den ggT(n² - n + 1, n + 1) mit dem Euklidischen Algorithmus.

Anfang:

n² - n + 1= (n+1)*(n + 1) -3n

-3n =(n+1) *.... + ...

Comments

Ich hab die Methode verstande.ich weiß aber nicht, wie ich auf (n+1) und -3n kommen soll.

---

Du suchst den ggT von n² - n + 1 und n + 1.

Also musst du n² - n + 1 zunächst durch n+1 teilen.

Der dabei entstehende Rest ist -3n.

Nun suchst du den ggT von n+1 und -3n.

Es gilt -3n=(-3)*(n+1)+3

Nun suchst du die gemeinsamen Teiler von -3n und 3.