Bizonyítsuk be, hogy a szomszédos Fibonacci-számok relatív prímek! Hogyan kell bebizonyítani?

Teljes indukcióval:

1-1-2-3-5-stb.

Mondjuk induljunk 2-től, mert az egy 1 se nem prím, se nem összetett.

2 és 3 relatív prímek.

Tehát F3 és F4-re igaz az állítás.

Tegyük fel, hogy n=k-ra még igaz, azaz:

LNKO(Fk, Fk+1)=1.

Mutassuk meg, hogy LNKO(Fk+1, Fk+2)=1.

Fk+2=Fk+Fk+1

LNKO(Fk+1, Fk+2) = LNKO(Fk+1, Fk+Fk+1)

Euklideszi algoritmus szerint:

[link]

LNKO(Fk+1, Fk+Fk+1) = LNKO(Fk+1, Fk), ami az indukciós feltevés szerint 1.

Ezzel kész a bizonyítás.

[

Részletesebben ez a rész:

LNKO(Fk+1, Fk+Fk+1) = LNKO(Fk+1, Fk)

Euklideszi algoritmus azt mondja, hogy a nagyobb számot osszuk a kisebbel:

(Fk+Fk+1) / Fk+1 ennek az osztásnak a maradéka persze éppen Fk.

]

Mi kell ahhoz, hogy két szám ne legyen relatív prím? Az, hogy legyen olyan 1-nél nagyobb egész szám, amivel mindkettő osztható. Máshogy fogalmazva van egy szám, amivel osztva maradékul 0-át kapunk.

Azt is tudni kell, hogy két szám összege esetén egy adott számmal történő maradékképzés is összegződik. Mondjuk összeadom a 13-at, meg a 26-ot. Tízzel osztva 13 maradéka 3, 26 maradéka 6. Az összeg 39, annak a maradéka 9, ami 3 és 6 összege.

A maradékhoz a „mod” műveletet fogom használni.

13 mod 10 = 3

26 mod 10 = 6

(13+26) mod 10 = 39 mod 10 = 9

3+6 = 9

(13 mod 10) + (26 mod 10) = (13+26) mod 10

Van egy kis csavar, vegyük a 17 és a 28 összegét, szintén a 10-el való oszthatóság tükrében:

17 mod 10 = 7

28 mod 10 = 8

(17+28) mod 10 = 35 mod 10 = 5

(7+8) mod 10 = 5

Azaz:

[(17 mod 10) + (28 mod 10)] mod 10 = (17+28) mod 10

Általánosan:

(n+m) mod p = [(n mod p) + (m mod p)] mod p

~ ~ ~

Mit jelent, hogy a két szomszédos Fibonacci szám – jelöljük őket f[n]-el és f[n+1]-vel –relatív prím? Azt, hogy van egy olyan p>1 szám, ami közös osztójuk, azaz

f[n] mod p = 0

f[n+1] mod p = 0

Ebből viszont az következik, hogy az f[n-1] -nek is oszthatónak kell lennie p-vel, hiszen

f[n-1] mod p + f[n] mod p = f[n+1] mod p

f[n-1] mod p + 0 = 0

f[n-1] mod p = 0

Induktív módon el fogunk jutni odáig, hogy

f[1] mod p = 0

f[2] mod p = 0

…

Ez meg ugye nem igaz. A Fibonacci-szám első két tagjának vagy a 0,1 vagy az 1,1 párost szokás tekinteni. Ezek nem oszthatóak 1-nél nagyobb számmal maradék nélkül. Sőt ha két Fibonacci-szám relatív prím, akkor kellett hogy legyen két szomszédos Fibonacci-szám, ahol mindkettő pontosan p.

~ ~ ~ ~ ~ ~ ~

Van olyan Fibonacci szerű számsor, ahol a kezdőérték más. Mondjuk nem 1,1-el indul a sorozhat, hanem mondjuk 6,21 -el. Ekkor így alakul a sorozatunk:

6, 21, 27, 48, 75, 123, 198, 321

Nota bene mivel az első két szám legnagyobb közös osztója 3, azaz nem relatív prímek, így a sorozat további tagjai is mind oszthatóak 3-al.

~ ~ ~ ~ ~ ~ ~

További érdekesség. A maradékok összeadása miatt a Fibonacci-számok maradéka ciklikusan változik egy adott szám esetén. Például kettővel való oszthatóság esetén a mod 2-ket felírva ezt kapjuk:

(0, 1, 1) ; 0, 1, 1 ; 0, 1, 1 ; 0, 1, 1 ; …

Ergo a 2 után minden harmadik szám páros.

3-al való oszthatóság esetén:

(0, 1, 1, 2, 0, 2, 2, 1) ; 0, 1, 1, 2, 0, 2, 2, 1 ; 0, 1, 1, 2, 0, 2, 2, 1 ; …

3 után minden negyedik szám osztható hárommal. (Pontosabban minden 8-adik, de minden nyolcadik után következő negyedik is.)

Ezt Pisano periódusnak hívják. Külön érdekesség, hogy melyik szám esetén mekkora ez a periódus hossz.

2 → 3

3 → 8

4 → 6

5 → 20

6 → 24

7 → 16

8 → 12

9 → 24

10 → 60

11 → 10

12 → 24