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