zeigen Sie, dass h(a) = 1 genau dann, wenn a= 2

Question

Aufgabe:

Sei a ∈ ℤ, a ≥ 2. Definiere die Höhe h(a) als die größte Zahl n, so dass Euklids Algorithmus n Schritte braucht, um ggT(a,b) zu berechnen, wobei b alle ganzen Zahlen mit 0 < b < a durchläuft. (d.h n ist so, dass ggT(a,b) = r_n-1 )

(a) zeigen Sie, dass h(a) = 1 genau dann, wenn a= 2

Problem/Ansatz:

Bis jetzt habe ich:

Sei a ∈ ℤ, a≥2 so dass, h(a) = 1

Falls a ≠ 2 so ist a > 2. Setze b:= a-1 ≥ 2

Der Euklidische Algorithmus auf a,b gibt:

a = 1 • b + 1

b = b • 1 + 0

Habe das als Lösung bist jetzt erhalten, verstehe aber nicht woher die zwei Schritte a und b kommen und woher das b:= a - 1 ≥ 2 kommt.

!

Comments

Hallo,

mir ist nicht klar, was Du fragst. b=a-1 zu nehmen ist eine Idee, also der "Pfiff" am Beweis. Mit diese Idee erfordert der Algorithmus füt ggt(a,a-1) 2 Schritte:

a=1*(a-1)+1

a-1=(a-1)*1+0

Gruß