Euklids algoritme (opgave)

Opgaven lyder
(først kridter jeg lige banen op)

Algoritme betyder i denne sammenhang en samling instruktioner der trin for trin beskriver hvilke operationer der skal udføres for at løse en matematisk opgave.

Ved største fælles divisor for to hele tal a og b (a og b ≠ 0) forstår vi det største hele tal, der går op i både a og b, dette betegnes sfd(a,b). Dette kan sammenfattes i følgende divisionsligning, for division af a med b, hvor q = kvotienten og r = resten.
a = b * q + r

Hvis sfd(a,b) = 1, har a og b ikke nogen fælles faktorer og er derfor indbyrdes primiske.

Hvis a og b er to tal, kaldes ethvert tal t af formen: t = h*a + k*b for en linearkombination af a og b.
For dette gælder følgende sammenhæng med Euklids algortime : sfd(a,b) = h*a + k*b

Jeg skal nu bevise at to på hinanden følgende fibonaccital fn og fn+1 er indbyrdes primiske, altså sfd=1

Dette skal jeg gøre ved hjælp af følgende sætning for leddene i fibonaccifølgen:
f(n+1)^2 = fn*f(n+2)+ (-1)^n


Jeg er bare virkelig lost...!!..
Alle med mulige ideer til løsning, vil være engle:D