Beweis: Für alle n aus N ist ggT(n +1, n² - n + 1) entweder 1 oder 3

Question

Aufgabe:

$$ \text{Beweisen Sie: Für alle } n \in \mathbb{N} \text{ ist ggT}(n + 1, n^2 - n + 1) \text{ entweder 1 oder 3. } $$

Problem/Ansatz:

Ich weiß nicht wie ich bei dieser Aufgabe anfangen soll oder welche Definitionen sinnvoll sein könnten. Ich denke mir es muss eine Fallunterscheidung verwendet werden aber wie sieht diese Unterscheidung aus und wo fange ich mit dem Beweis an?

Ich habe versucht den euklidischen Algorithmus anzuwenden, stehe dabei aber noch aufm Schlauch.

Für eine Hilfestellung wäre ich sehr dankbar!

Gruß

MatheBube

Answer 1

"Ich habe versucht den euklidischen Algorithmus anzuwenden,"

Und warum hast du ihn nicht zum Ende geführt?

Es ist n²−n+1

=n²+n-2n+1

=n²+n-2n-2+3

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

Der ggT von n²−n+1 und (n+1) muss somit auch 3 teilen.

Comments

Das kann ich leider nicht ganz nachvollziehen. Diesen Beweis hast du nun nur mit dem euklidischen Algorithmus hergeleitet?

---

"Diesen Beweis hast du nun nur mit dem euklidischen Algorithmus hergeleitet?"

Nein, weil mir das zu viel Schreibarbeit ist.

Aber wenn du ihn durchführst, kommst du auf den Rest 3.

---

Achso, ok.

Ich komme bei den Algorithmus aber auf keine Lösung. Kannst du mir bitte zeigen wie es zumindest anfängt? Ich denke dann komme ich bestimmt auch auf die Lösung

---

ich bin zwar nicht der Fragesteller aber wenn man die 3 als Rest am Ende raus hat, wie kann man dann arguemtieren, dass der ggt auch 1 seien kann?