Beweisen Sie : ggT(F_n+1, F_n) = 1

Question

Beweisen Sie folgende Aussage:

Seien F_n die Fibonacci-Zahlen. Für alle n ∈ N gilt: ggT(F_n+1, F_n) = 1

Answer 1

Zeige es per vollst. Induktion:

Für n=1 ist ggT(F2,F1)=ggT(1,1) = 1 klar.

Gilt ggT(F_n+1,F_n)=1 für alle nat. Zahlen bis einschließlich n,

dann folgt: Sei t ein gemeinsamer Teiler von F_n+2 und F_n+1.

Wegen der Rekursion:

==> t ist ein gemeinsamer Teiler von F_n+1+F_n und von F_n+1

==>  t |  (F_n+1+F_n-F_n+1) also t | F_n

Also ist t auch ein gemeinsamer Teiler von Fn und von Fn+1

==>  t =1.  ==>   ggT(F_n+2,F_n+1)=1.

  

Comments

Vielen lieben Dank