Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem A. 730. (September 2018)

A. 730. Let $\displaystyle F_n$ be the $\displaystyle n$th Fibonacci number ($\displaystyle {F_1=F_2=1}$, $\displaystyle {F_{n+1}=F_n+F_{n-1}}$). Construct infinitely many positive integers $\displaystyle n$ such that $\displaystyle n$ divides $\displaystyle F_{F_n}$ but $\displaystyle n$ does not divide $\displaystyle F_n$.

(7 pont)

Deadline expired on October 10, 2018.

Solution (outline). We will show that $\displaystyle n=4\cdot3^k\cdot23$ satisfies the conditions for all positive integers $\displaystyle k$.

We will use some well-known properties of the Fibonacci sequence.

Lemma 1. If $\displaystyle 3\big|F_n$ then $\displaystyle v_3(F_{3n})=v_3(F_n)+1$. ($\displaystyle v_p(k)$ denotes the exponent of the prime $\displaystyle p$ in the prime factorization of $\displaystyle k$.)

Proof. Let $\displaystyle \varphi=\frac{1+\sqrt5}2$ és $\displaystyle \psi=\frac{1-\sqrt5}2$. By the closed form fo the Fibonacci numbers,

$\displaystyle F_{3n} = \frac{\varphi^{3n}-\psi^{3n}}{\sqrt5} = \frac{(\varphi^n-\psi^n)^3+3\varphi^n\psi^n(\varphi^n-\psi^n)}{\sqrt5} = 5\bigg(\frac{\varphi^n-\psi^n}{\sqrt5}\bigg)^3+3(\varphi\psi)^n\frac{\varphi^n-\psi^n}{\sqrt5} = 5F_n^3+3(-1)^nF_n.$

In the term $\displaystyle 5F_n^3$, the exponent of $\displaystyle 3$ is $\displaystyle 3v_3(F_n)$; in the second term $\displaystyle 3(-1)^nF_n$ the exponent of $\displaystyle 3$ is $\displaystyle v_3(F_n)+1$. The exponent is lower in the second term.

Lemma 2. $\displaystyle 23\big|F_n \,\Longleftrightarrow 24\big|n$.

Proof. It is easy to check that $\displaystyle F_{24}=46368=2016\cdot 23$ is the first Fibonacci number that is divisible by $\displaystyle 23$.

If $\displaystyle 24\big|n$ then $\displaystyle 23\big|F_{24}\big|F_n$.

If $\displaystyle 24\not{\big|}n$ then let $\displaystyle d=gcd(n,24)<24$. Then $\displaystyle gcd(F_n,23)\big|gcd(F_n,F_{24})=F_d$, but $\displaystyle F_d$, preceding $\displaystyle F_{24}$, is not divisible by $\displaystyle 23$.

Hence, if $\displaystyle k\ge1$ and $\displaystyle n=4\cdot3^k\cdot23$ then, by Lemma 2, we have $\displaystyle n\not{\big|}F_n$, because $\displaystyle 23\not{\big|}F_n$, because $\displaystyle 24\not{\big|}n$.

On the other hand,

• By $\displaystyle 12\big|n$ we have $\displaystyle 24\big|144=F_{12}\big|F_n$;
• By $\displaystyle 12\big|F_n$ we have $\displaystyle 144=F_{12}\big|F_{F_n}$;
• By $\displaystyle 3\big|F_4\big|F_{4\cdot23}$ and Lemma 1, we have $\displaystyle 3^k\big|F_n$, so $\displaystyle 3^k\big|F_{F_n}$;
• By $\displaystyle 24\big|F_n$ we have $\displaystyle 23\big|F_{F_n}$.

Therefore, $\displaystyle F_{F_n}$ is divisible by $\displaystyle n=4\cdot3^k\cdot23$.

Comment. More generally, by iterating the Fibonacci numbers, let $\displaystyle F^k(n)=\underbrace{F(\ldots F}_k(n)\dots)$. We show that for every $\displaystyle k\ge2$ there exist infinitely many $\displaystyle n$ such that $\displaystyle n\big|F^k(n)$, but $\displaystyle n$ does not divide any of $\displaystyle F(n),\ldots,F^{k-1}(n)$.

Proof: Let $\displaystyle m$ such that $\displaystyle m\big|F_m$ (for instance, we can choose $\displaystyle m=5^t$ or $\displaystyle m=12\cdot 3^t$ or $\displaystyle m=F^t(12)$ etc.). Let $\displaystyle p$ be a primitive prime divisor of $\displaystyle F^k(m)$ (if $\displaystyle m$ is sufficiently large then there is such a prime, see Carmichael's teorem), and let $\displaystyle n=mp$. Then $\displaystyle m\big|F(m)\big|F^2(m)\big|\ldots\big|F^k(m)$ and $\displaystyle p\big|F^k(m)$, so $\displaystyle n\big|F^k(m)\big|F^k(n)$.

On the other hand, for $\displaystyle 1\le\ell<k$ we have

$\displaystyle \gcd\big(F^\ell(n),n\big) \big| \gcd\big(F^\ell(n),F^k(n)\big) = F^\ell\big(\gcd(F^{k-\ell}(n),n)\big),$

here $\displaystyle F^{k-\ell}(n)$ is not divisible by $\displaystyle p$, and therefore

$\displaystyle \gcd\big(F^\ell(n),n\big) \Big| m,$

so,

$\displaystyle \gcd\big(F^\ell(n),n\big) \big| F^\ell\big(m)\big),$

that is not divisible by $\displaystyle p$.

### Statistics:

 10 students sent a solution. 7 points: Jedlovszky Pál, Kerekes Anna, Matolcsi Dávid, Schrettner Jakab, Szabó 991 Kornél, Szabó Kristóf. 6 points: Beke Csongor. 0 point: 2 students. Not shown because of missing birth date or parental permission: 1 solutions.

Problems in Mathematics of KöMaL, September 2018