1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Related. $\endgroup$
    – Jyrki Lahtonen
    Nov 24, 2022 at 6:51
  • 3
    $\begingroup$ 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$ $\endgroup$
    – Peter
    Nov 24, 2022 at 7:10
  • $\begingroup$ Special case of the fact that $F_n$ form a divisibility sequence - see the linked dupe. $\endgroup$
    – Bill Dubuque
    Nov 24, 2022 at 13:28

1 Answer 1

Reset to default
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please strive not to post more (dupe) answers to dupes of FAQs, cf. recent site policy announcement here. $\endgroup$
    – Bill Dubuque
    Nov 24, 2022 at 13:29

Not the answer you're looking for? Browse other questions tagged .