A 13 000 000 000 001. Fibonacci-szám hány bites, prím-e, és mennyi a 13-mal osztási maradéka?

A Fibonacci sorozat zárt alakja:

[link]

Kicsit másképp írva

a(n) = 1/gyök(5) * [(1/2+gyök(5)/2)^n - (1/2-gyök(5)/2)^n]

A második tag a zárójelben: -0,618^n

Ez ahogy n nő 0-hoz tart. Ekkora számnál el is hagyható.

a(n) = 1/gyök(5) * [(1/2+gyök(5)/2)^n]

Ebből az alakból kiszámolhatod, hogy hány számjegyű, illetve hány bites.

A 13-mal való osztási maradék periodikusan ismétlődik, ha megkeresed a periódust, akkor meg lehet mondani a pontos maradékot.

A Fibonacci prímekről ezt találtam: [link]

Azt kéne megnézni, hogy n prím-e. Ha nem, akkor Fn se prím.

A 13-mal valo osztas maradeka nem periodikus a Fibonacci szamokra nezve, viszont Ifjutitan linkjen van egy erdekes dolog: Fn akkor es csak akkor osztoja Fm-nak, ha n osztoja m-nek.

F7=13, vagyis ha 13 000 000 000 001 oszthato 7-tel, akkor az annyiadik Fibonacci szam oszthato 13-mal. 13 000 000 000 001 pedig oszthato 7-tel.

13-mal való osztási maradék összesen 13 féle van (0,1,...,12)

ez véges sok lehetőség, van egy olyan emlékem, hogy ilyen esetekben mindenképp ismétlődni fog az osztási maradék, de már nem tudom, hol olvastam ilyet.

Konkrétan itt is ez történik, egy excelben könnyen felírható az első X maradék.

A 29. maradék 1, és a 30. maradék szintén 1. Tehát innentől ismétlődik az egész.

Vagyis a periódus hossza 28.

A n 28-as osztási maradékát kell megnézni.

Az osztási maradék 0.

Vagyis ugyanannyi a maradéka, mint a 28. Fibonacci tagnak, aminek a maradéka 0.

Tehát osztható 13-mal.

A periodikusságról 1 mondat.

13 féle maradék lehet, itt mindig az előző két szám határozza meg a következőt.

Két szám 13*13=169 féle lehet.

Tehát legrosszabb esetben 169 elem után újra olyannak kell lennie, ami már volt. Tehát mindenképp fel kell lépnie a periodikusságnak előbb-utóbb.