Aufgabe zum größten gemeinsamen Teiler. Bsp. ggT(10n + 11, 8n + 9) =?

Question

Sei n ∈ ℕ, n > 0, beliebig. Berechnen Sie

a) ggT(10n + 11, 8n + 9),

b) ggT(n², n + 1).

Geben Sie jeweils alle Rechenschritte an.

Comments

Kennst du irgendeneinen Algorithmus, um den GGT zu berechnen?

Bsp. https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler#Euklidischer_und_steinscher_Algorithmus 

ggT(10n + 11, 8n + 9), 

(10n + 11):(8n + 9) = 1   Rest 2n + 2 

8n + 9 

-----------

2n + 2 

usw.

(8n + 9):(2n+2) = 4   Rest 1

(8n + 8)

-----------

         1

(2n + 2): 4 = 0.5n + 0.5     Rest 0 

GGT ist 0.5n + 0.5 (ist nur eine natürliche Zahl, wenn n ungerade ist)

Kann das sein? 

Teste es für ein paar ungerade n . 

2. Fall: n gerade

noch separat anschauen.

---

Deine Rechnung ist falsch.

Grüße,

M.B.

---

Das ist eine gute Übungsaufgabe. Überlassen wir die Fehlersuche sailorsinachan .

---

hahaha; dass Deine Lösung nicht stimmen kann, hast Du doch selber schon gemerkt.

Grüße,

M.B.

Answer 1

Ist g = ggT(10n + 11, 8n + 9), dann gilt g | 10n + 11 und g | 8n + 9, also auch g | (10n + 11) - (8n + 9) = 2n + 2.

Wegen g | 2n + 2 gilt auch g | 4·(2n + 2). = 8n + 8

Aus g | 8n + 9 und g | 8n + 8 folgt g | (8n + 9) - (8n + 8) = 1.

Wegen g | 1 ist g = 1.