# Fibonacci 19^n is multiple of 19 a mathematical property or a unique event? [duplicate]

Considering the 0 as the first index of Fibonacci numbers, I observed that Fibonacci(19^n) is multiple of 19. (Practically I could try till n=7).

Is this a mathematical property of prime numbers or a unique event that is specific to 19?

When I try this for example with 17, Fibonacci(17) is not multiple of 17.

Here are the numbers I got: Fibonacci(19) = 2584

Fibonacci(19^2) = 769246427201094785080787978422393713094534885688979999504447628313150135520

Fibonacci(19^3) = 77223918028134751317220649503760294619865221230630620267515617265364193779206916763586963738360558654810230457156413735199017159966140768740547573257746229247494109984532712091401347666285515192435969639135537907647253236885005214100991831387633945699356234567594641167485415291985660718054685933219394871221498400100111258901259261475463366642201065952364422998360148513334554727909095771178013169606178788334006644248071506848528028582311325288822221480076416532651419962133614666239060215679662332235616407987618995513625384593975015177199076835628238019716550494140439777655697056823084746841987294899174303231734081097478629863529579666839700242772759046754642409866884512721108646717212230848243184944441936279697859930045744488665626818429189604454621986698558824064652025879059159092916364656274927700527580999998549845904852814684478765572041162133000787130785239490138783996782356038579384441027619789715044143077725771905073614061824330107778145071188849207951042179795463036291821280014681035716553223428698534465024303763846035129332867716442513469594596745849394673944644021386821045255174229627277673511937083441014533624863094779259763189446077456590000478046143218621346523209175412741436075035590546332466504145640037681473454798247079649150876012236219180761998674004017783004891145172266418884276720631228242376951029496050745224600341614519267347532497316954001888633011171110848793977790871858970699160034686904

I will stop here but it worked in my R coding with gmp library till 7. Afterwards, computer precision might not be correct.

However when I try the same with 17, it is not multiple of 17. Fibonacci(17) = 987

987 %% 17 = 1

• Nov 24, 2022 at 6:51
• Depending on the residue of $p$ modulo $5$ , either $F_{p-1}$ or $F_{p+1}$ is divisible by $p$. For $p=19$ , the period is $18$ , so we have $19\mid F_n$ iff $18\mid n$ which explains your pattern that repeats forever because of $19^n \equiv 1\mod 18$ Nov 24, 2022 at 7:10
• Special case of the fact that $F_n$ form a divisibility sequence - see the linked dupe. Nov 24, 2022 at 13:28

Your definition of the $$n$$th fibonacci number is a little bit non-standard: normally, we define $$F_0=0$$, $$F_1=1$$, so $$F_2=1$$, $$F_3=2$$ and so on. Then, it's actually $$F_{18}$$ which is $$2584=19\times136$$.
As for the reason behind the pattern you noticed: it's possible to prove that if $$k$$ divides $$F_n$$, then $$k$$ also divides $$F_{mn}$$ for any $$m$$. So, for example, $$19$$ divides $$F_{18}$$, so it also divides $$F_{18}$$, $$F_{36}$$, $$F_{54}$$ and so on.
So you've noticed that $$19$$ divides $$F_{19^k-1}$$ for all $$k$$. That's because $$19^k-1$$ is always a multiple of $$18$$: specifically, $$19^k-1=(19-1)(19^{k-1}+19^{k-2}+\dots+19+1).$$
For $$17$$, it turns out that $$F_9=2\times 17$$, so every $$9$$th fibonacci number is a multiple of $$17$$. This includes every 18th fibonacci number, of course, so it turns out that if a fibonacci number is divisible by 19, it is also divisible by 17.
However, numbers of the form $$17^k-1$$ are not multiples of 9. On the other hand, numbers of the form $$17^k+1$$ are, if $$k$$ is odd, so there's another interesting collection of fibonacci numbers which are divisible by 17.