$F(x^n)$整除$F(x)^n$ Fibonacci

hbghlyj

artofproblemsolving.com/community/c4h2521934p21401320
正整数 $x$, 若存在整数 $n≥2$ 使 $F(x^n)$ 整除 $F(x)^n$, 则它对所有整数 $n≥2$ 成立.
($F(x)$是Fibonacci数列第$x$项, 如$F(1)=1,F(2)=1$.)

正整数$x,k$,
$$F(x+k)=F(k)F(x+1)+F(k-1)F(x)\tag😃\label{star}$$
证明:对$k$归纳.

Lemma 0. Fibonacci数列的每两个相邻项互质
证明: 若 $p|F(x+1)$ 且 $p|F(x)$, 则 $p|F(x-1)$, $p|F(x-2)$, ⋯最终 $p|1$.

Lemma i. $F(x)|F(y)⇔x|y$.

Proof.

$⇐:y=ax$,使用\eqref{star}式,对$a$归纳.
$⇒:$ let $y=ax+b$, such that $F(y)=F(ax+b)=F(ax)F(b+1)+F(ax-1)F(b)$
Using lemma 0, if $F(x)|F(y)$, that means that $F(x)|(F(ax)F(b+1)+F(ax-1)F(b))$, which can be reduced to $F(x)|F(b)$, which is impossible if $x$ doesn't divide $y$, because if that is the case then $F(b)<F(x)$ because $b$ is a module residue of $x$, so we are done.

Lemma ii. $F(ax+1) \equiv F(x+1)^{a} \pmod{F(x)^{2}}$

Proof

Induct on $a$. When $a=1$ it is trivial.
\begin{align*}F(x+(ax+1))&=F(ax+1)F(x+1)+F(ax)F(x)\\&≡F(ax+1)F(x+1)\pmod{F(x)^2}&\text{by lemma i}\end{align*}

Using the previous two lemmas, we can finally start working on the question.
Let $a_{n}=\frac{F(nk)}{F(k)}$, which we know is a sequence of integers by lemma i.
Expanding $F(nk)$ by using the fact that $F(k(n-1)+k)=F(k)F(k(n-1)+1)+F(k-1)F(k(n-1))$, gives us that
$a_{n}=F(k(n-1)+1)+F(k-1)a_{n-1}$
As $a_{1}=1$, $a_{2}=F(k-1)+F(k+1)$, and $a_{3}=F(k-1)^{2}+F(k-1)F(k+1)+F(2k+1)$, it can be shown recursively that
$a_{n}=F(k-1)^{n-1}+F(k+1)F(k-1)^{n-2}+F(2k+1)F(k-1)^{n-3}+...+F((n-1)k+1)$.
Using this closed form of $a_{n}$, we need to find the values of $a_{n}$ such that $a_{n}$ is divisible by $F(k)$, as we are trying to find minimal Fibonacci terms divisible by $F(k)^{2}$.
Using lemma ii in conjunction with the fact that $F(k+1) \equiv F(k-1) \pmod{F(k)}$ for obvious reasons, we conclude that
$a_{n} \equiv nF(k-1)^{n-1} \pmod{F(k)}$, which by also using that $\gcd(F(k-1),F(k))=1$, shows that if $F(k)|a_{n}$, then $F(k)|n$; so, in conclusion, $F(kF(k))$ is the smallest fibonacci number divisible by $F(k)^{2}$.
But how can this be applied to higher powers of $F(k)$?
Well, in order to do that, we need to find all "excess" numbers that divide $a_{F(k)}$ and $F(k)$.
Using lemma ii again on $a_{F(k)}$, we can see that
\begin{aligned}a_{F(k)}&≡F(k-1)^{F(k)-1}+F(k+1)F(k-1)^{F(k)-2}+F(k+1)^{2}F(k-1)^{F(k)-3}+...
\\&≡\frac{F(k+1)^{F(k)}-F(k-1)^{F(k)}}{F(k+1)-F(k-1)}
\\&≡\frac{F(k+1)^{F(k)}-F(k-1)^{F(k)}}{F(k)} \pmod{F(k)^{2}}
\end{aligned}Assume that prime $p>2$ divides $F(k)$. Therefore by LTE, $v_{p}(\frac{F(k+1)^{F(k)}-F(k-1)^{F(k)}}{F(k)})=v_{p}(F(k+1)^{F(k)}-F(k-1)^{F(k)})-v_{p}(F(k))=v_{p}(F(k))$, so $v_{p}(a_{n})=v_{p}(F(k))$.
Therefore if $F(k)$ is odd, $\gcd(F(kF(k)),F(k)^{3})=F(k)^{2}$.
This next part is kind of weird, but I believe it holds.
We are trying to find $v_{2}(F(kF(k)))$ if $2|F(k)$.
You can show that $v_{2}(F(3*2^{n-2}))=n$ for $n>2$ recursively, but I won't get into it unless someone asks otherwise.
Let us split it into 2 cases:
Case 1: $v_{2}(F(k)) \ge 3$
Because if $v_{2}(F(k)) \ge 3$, $v_{2}(F(2k))=v_{2}(F(k))+1$, $v_{2}(F(kF(k)))=v_{2}(F(k))+v_{2}(F(k))=v_{2}(F(k)^{2})$, so in this case $\gcd(F(kF(k)),F(k)^{3})=F(k)^{2}$.
Case 2: $v_{2}(F(k))=1$
In this case, $v_{2}(F(kF(k)))=v_{2}(F(k)^{2})+1$, so $\gcd(F(kF(k)),F(k)^{3})=2F(k)^{2}$, so this case is an exception.

Now by doing the original check for $F(k)|a_{n}$, but replacing $a_{n}$ with $\frac{F(n(kF(k)))}{F(kF(k))}$, allows us, at least in the $v_{2}(F(k)) \neq 1$ case, to show that $F(kF(k)^{2})$ is the smallest fibonacci multiple of $F(k)^{3}$, $F(kF(k)^{3})$ is the smallest fibonacci multiple of $F(k)^{4}$ and so on, which means in this case $F(kF(k)^{n-1})$ is the smallest fibonacci multiple of $F(k)^{n}$.
In the $v_{2}(F(k))=1$ case, $F(kF(k))$ is the smallest fibonacci multiple of $F(k)^{2}$, but $F(k\frac{F(k)^{2}}{2})$ is the smallest fibonacci multiple of $F(k)^{3}$ (because $F(kF(k))$ had an extra 2 in it's factorization that didn't need to be re-added in the next case), $F(k\frac{F(k)^{3}}{2})$ is the smallest fibonacci multiple of $F(k)^{4}$, and so on, which leaves us with the smallest fibonacci multiple of $F(k)^{n}$ is $F(k\frac{F(k)^{n-1}}{2})$ for $n \ge 3$, but $F(kF(k))$ if $n=2$.

Now that we finally have all the parts we need, we can solve the question.
Because of lemma i, $x^n$ must be divisible by the smallest $k$ such that $F(x)^{n}$ divides $F(k)$.
For $v_{2}(F(x)) \neq 1$, $k=xF(x)^{n-1}$, which means $F(x)^{n-1}$ divides $x^{n-1}$, or $F(x)$ divides $x$, which holds for 3 values of $x$, which are $x=(1,2,5)$, in which case all $n$ still work, so this case satisfies the statement.
For $v_{2}(F(x))=1$ and $n \ge 3$, $\frac{F(x)^{n-1}}{2}$ divides $x^{n-1}$, which obviously has no solution (because it implies that $(\frac{x}{F(x)})^{n-1}$ has a denominator of 2, which implies that $2^{\frac{1}{n-1}}$ is rational, which is obviously incorrect).

Therefore, the only solutions of $x$ are $1$, $2$, and $5$, which all produce integers for all integers $n \ge 2$, so we are done.