Bestimmen Sie den ggT variabler Zahlenpaare

Question

Aufgabe:

Bestimmen Sie den ggT variabler Zahlenpaare.

ggT(2n-1,2n² -1)

Problem/Ansatz:

Mir sind folgende Sätze bekannt:
1) ggT(a,a)=a
2) ggT(a,1)=12)
3) ggT(a,0)=a
4) ggT(a,b)=ggT(b,a)
5) ggT(a,b)=ggT(a-b,a)

Ich weiß nicht wie man das lösen soll ..
Laut Lösung soll das Ergebnis=1 sein.

Ich gehe davon aus, dass man die Sätze anwenden und dadurch umformen muss?
Jeder Tipp wäre hilfreich!

Answer 1

Hallo,

5) ggT(a,b)=ggT(a-b,a)

dies kann man verallgemeinern zu $$\text{ggT}(a,b) = \text{ggT} (a,b + ma), \quad m \in \mathbb Z$$(siehe Wiki) dann könnte die Umformung so aussehen: $$\text{ggT}(2n-1,2n^{2} -1) \\ = \text{ggT}(2n-1,2n^{2} -1 - n(2n-1)) \\ = \text{ggT}(2n-1, n-1) \\ = \text{ggT}(2n-1-2(n-1), n-1) \\ = \text{ggT}(1, n-1) \\ = 1$$ Bem.: beim Euklidischen Algorithmus macht man ja auch nichts anderes, als ein Vielfaches der kleineren Zahl von der größeren zu subtrahieren.

Comments

$$ = \text{ggT}(2n-1,2n^{2} -1 - n(2n-1)) $$

Müsste das dann nicht $$ = \text{ggT}(2n-1,2n^{2} -1 + n(2n-1)) $$ lauten?
wegen ggT(a,b+m*a).

Vielen dank schon mal.

---

\(m \in \mathbb Z\) heißt, es darf auch \(m = \colorbox{#ffff00}-n\) sein, selbst wenn \(n \in \mathbb N\)

---

Bem.: beim Euklidischen Algorithmus macht man ja auch nichts anderes, als ein Vielfaches der kleineren Zahl von der größeren zu subtrahieren.

Setze doch mal \(n=7\). Wenn man nach dem euklidischen Algorithmus den ggT berechnet macht man es doch genauso:$$\text{ggT} (13,99) \\ = \text{ggT}(13, 99 - 7 \cdot 13) \\ = \text{ggT}(13, 6) \\ = \text{ggT}(13-2 \cdot 6, 6) \quad \text{usw.}$$das ist exakt das gleiche!