Local-global with Fibonacci numbers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Local-global with Fibonacci numbers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2020 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#1 h Jul 28, 2020, 7:45 AM • 3 Y

Y by yayitsme, Loppukilpailija, richrow12

Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\geq 3$ . Let $k$ be a positive integer. Suppose that for every positive integer $m$ there exists a positive integer $n$ such that $m \mid F_n-k$ . Must $k$ be a Fibonacci number?

Proposed by Fedir Yudin.

This post has been edited 1 time. Last edited by MarkBcc168, Dec 30, 2020, 4:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1508 posts

#2 h Jul 28, 2020, 7:49 AM • 2 Y

Y by parmenides51, aac3020

We claim that the answer is yes. Take $m>>k$ such that $m=F_{2t}$ for some large integer $t$ . Use Cassini identity $F_{2t}F_{2t+2}=F_{2t+1}^2-1$ to get that $F_{2t+1}^2 \equiv 1$ mod $F_{2t}$ . Working mod $F_{2t}$ and using induction we can also see that $F_{2t+n} \equiv F_{n}F_{2t+1}$ mod $F_{2t}$ (base cases $F_{2t+1}, F_{2t+2}$ are easily verified and induction step is done using distributive property of multiplication and the linear recurrence). Since $F_{2t+1}^2 \equiv 1$ mod $F_{2t}$ by Cassini identity, we check that $F_{4t+n} \equiv F_{2t+n}F_{2t+1} \equiv F_{n}(F_{2t+1})^2 \equiv F_n$ mod $F_{2t}$ . So we can see that the Fibonacci numbers give us at most $4t$ possible remainders mod $F_{2t}$ . Also, using $F_{m}+F_{m+1}=F_{m+2}$ we can check that $F_{2t-1} \equiv F_{2t+1}$ mod $F_{2t}$ and $F_{2t-2} \equiv (-1)*F_{2t+2}$ mod $F_{2t}$ . Using these as base cases we can apply induction and prove that for all non-negative integers $n \leq 2t$ we have $(-1)^{n+1}F_{2t-n} \equiv F_{2t+n}$ mod $F_{2n}$ . Now using the earlier proved fact that $F_{4t+n} \equiv F_{n}$ mod $F_{2t}$ , we can see that for any Fibonacci number $F_q$ , it is congruent mod $F_{2t}$ to a number of the form $\pm F_v$ where $0 \leq v \leq 2t-1$ . So now consider the positive integer $n$ for which $m=F_{2t}|F_n-k$ . By the previous argument, $n$ is congruent to some number of the form $\pm F_r$ mod $F_{2t}$ where $0 \leq r \leq 2t-1$ .
Thus $F_{2t}|\pm F_r-k$ for some appropriate choice of sign. Now since $r$ is between $0$ and $2t-1$ , we have $|F_r| \leq F_{2t-1}=F_{2t}-F_{2t-2}$ . Now, since we chose $m=F_{2t}$ to be very large in comparison to $k$ , we can see that $|k|<|F_{2t-2}|$ . Thus $| \pm F_r-k|<F_{2t}$ and $F_{2t}| \pm F_r-k$ , so we can see that $\pm F_r-k$ is forced to be equal to $0$ . So $k=\pm F_r$ for some Fibonacci number less than $F_{2t}$ . But $k$ is a positive integer and $0 \leq r \leq 2t-1$ . Thus $k=F_r$ . So $k$ has to be a Fibonacci number. Proved

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

354 posts

#3 h Jul 28, 2020, 7:54 AM • 4 Y

Y by ayan.nmath, Juanscholtze, Lcz, sabkx

For the sake of contradiction assume that there exists such $k$ which is not a Fibonacci number
Then for all primes $p$ and some $m$ we have $F_{m}\equiv k\pmod{p}$
Note that $n$ is a Fibonacci number if and only if $5n^2-4$ or $5n^2+4$ is a perfect square.
So for all primes either $5k^2-4$ or $5k^2+4$ is a quadratic residue modulo primes which is obviously a contradiction as for any two fixed integers we can have a prime such that both integers are quadratic non residue modulo prime
Remark

This post has been edited 6 times. Last edited by Superguy, Aug 3, 2020, 11:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

643 posts

#4 h Jul 28, 2020, 8:41 AM • 4 Y

Y by Superguy, Gaussian_cyber, Juanscholtze, Mango247

MarkBcc168 wrote:

Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\geq 3$ . Let $k$ be a positive integer. Suppose that for every positive integer m there exists a positive integer $n$ such that $m \mid F_n-k$ . Must $k$ be a Fibonacci number?

Proposed by Fedir Yudin.

Solution. Yes, we claim that $k$ must be a Fibonacci Number. Define $g(n)$ to be least possible natural number satisfying $F_n\mid F_{g(n)}-k$ and set $F_0=0.$ Let $\phi=\tfrac{1+\sqrt 5}{2}.$ The following facts are well known and easy to prove

$F_n=\left[\tfrac{\varphi^n}{\sqrt 5}\right]$ where $[\cdot]$ is the nearest integer function.
$F_n=\tfrac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}.$
$F_{2n}>\varphi F_{2n-1}.$
$F_{m+n}=F_{m-1}F_n+F_mF_{n+1}.$
$F_{n-1}F_{n+1}-F_n^2=(-1)^n.$
$\gcd(F_m,F_n)=F_{\gcd(m,n)}.$

Claim 1. $F_{2n}\mid F_{4n}$ and $F_{2n}\mid F_{4n+1}-1.$

Proof. The first divisibility is trivial by (vi). For the latter part notice that (iv) implies $F_{4n+1}=F_{2n-1}F_{2n+1}+F_{2n}F_{2n+2}\equiv F_{2n-1}F_{2n+1}\pmod{F_{2n}}.$ Using (v) we have that $F_{2n-1}F_{2n+1}-F_{2n}^2=1.$ Hence the claim. $~\square$

The above claim implies that $g(2n)<4n.$ Assume that $k$ is not a Fibonacci number, so let us set $g(2n)=2n+p$ for now where $p\ge 1$ . Using (iv) we have $k\equiv F_{2n+p}\equiv F_pF_{n-1}\pmod {F_n}.$ Let $a=\left\lfloor \tfrac{F_p}{\varphi}\right\rfloor$ and $b=F_p-a\varphi.$

Claim 2 $|F_{n}-\varphi F_{n-1}|=\frac{\varphi^{-n}(2+\varphi)}{\sqrt 5}.$ Proof.
$\begin{align*} |F_{n}-\varphi F_{n-1}|&=\left|\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}-\varphi\left(\frac{\varphi^{n-1}-(-\varphi)^{-n+1}}{\sqrt 5}\right)\right|\\ &=\frac{1}{\sqrt 5}\left|\varphi^n-(-\varphi)^{-n}-\varphi^n+(-1)^{n-1}\varphi^{-n+2}\right|\\ &=\frac{1}{\sqrt 5}\left|(-\varphi)^{-n}+(-1)^{n}\varphi^{-n+2}\right|\\ &=\frac{1}{\sqrt 5}\left|\varphi^{-n}+\varphi^{-n+2}\right|\\ &=\frac{\varphi^{-n}(2+\varphi)}{\sqrt 5}.\tag*{$\square$} \end{align*}$ Claim 3. Let $R$ be the remainder when $F_pF_{n-1}$ is divided by $F_n$ where $p\le n-1.$ Then
$-1+\left\{\frac{F_p}{\varphi}\right\}F_{n-1}<R<1+\left\{\frac{F_p}{\varphi}\right\}F_{n-1}$ for all large $n$ where $\{\cdot\}$ denotes the fractional part.

Proof. Let $b=\left\{\frac{F_p}{\varphi}\right\}$ and $a=\left\lfloor\frac{F_p}{\varphi}\right\rfloor.$ Note that $\lim_{n\to \infty} \frac{a}{\varphi^{p-1}}=5^{-\tfrac12}.$ Now
$F_pF_{n-1}-aF_n=a(\varphi F_{n-1}-F_n)+bF_{n-1}$ By claim 1 it is not hard to see that the claim follows. $\square$

Therefore it follows that
$-1+\left\{\frac{F_p}{\varphi}\right\}F_{2n-1}<k<1+\left\{\frac{F_p}{\varphi}\right\}F_{2n-1}\qquad(\star)$ for all large $n$ where $1\le p\le 2n-1$ Again let $b=\left\{\frac{F_p}{\varphi}\right\}$ and $a=\left\lfloor\frac{F_p}{\varphi}\right\rfloor.$ We have $F_p=a\varphi+b$ as usual. By claim 1 it follows that $F_{p-1}=\left[\frac{F_p}{\varphi}\right]$ hence if $p$ is odd then $a=F_{p-1}-1$ and otherwise $a=F_{p-1}.$ Therefore
$b=F_p-a\varphi= \begin{cases}F_p-F_{p-1}\varphi &,\text{ if }p\text{ is even}\\ F_p-F_{p-1}\varphi+\varphi &,\text{ otherwise }\end{cases}.$ If $p$ is odd, $F_p>F_{p-1}\varphi$ hence $bF_{2n-1}=(\varphi+F_p-\varphi F_{p-1})F_{2n-1}=F_{2n-1}\cdot\frac{2+\varphi}{\varphi^p\sqrt 5}+F_{2n-1}\varphi\to+\infty$ as $n\to\infty.$ Therefore $p$ must be even for all large $n.$ In this case we obtain
$bF_{2n-1}=(F_p-\varphi F_{p-1})F_{2n-1}=F_{2n-1}\cdot\frac{2+\varphi}{\varphi^p\sqrt 5}$ Using the fact that $F_{2n-1}\approx \frac{\varphi^{2n-1}}{\sqrt 5}\implies bF_{2n-1}\approx \varphi^{2n-1-p}\cdot\frac{2+\varphi}5$ we can conclude that $2n-p$ is eventually constant. So let $p=2n-c$ for all large $n$ where $c$ is a constant natural number. Since $p$ is even hence $c$ is also even. Now we have that $F_{2n}\mid F_{2n-c}F_{2n-1}-k$ for all large $n.$ Notice that $F_{2n-c}\equiv (-1)^cF_cF_{2n-2}\pmod{F_n}\equiv F_cF_{2n-2}\pmod{F_{2n}}\equiv -F_cF_{2n-1}\pmod{F_n}.$ This implies that $F_{2n}\mid F_c+k$ since $F_{2n-1}^2\equiv F_{2n-1}F_{2n+1}\equiv 1\pmod{F_{2n}}.$ Taking $n\to+\infty$ we obtain a contradiction. And we are done. $~\blacksquare$

This post has been edited 2 times. Last edited by ayan.nmath, Jul 28, 2020, 8:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

124 posts

#5 h Jul 28, 2020, 9:10 AM • 7 Y

Y by AforApple, Wizard_32, diegoca1, Nuterrow, sabkx, Mango247, bin_sherlo

The answer is yes, and suppose for the sake of contradiction that such a $k$ exists, where $k$ is not a Fibonacci number. Then take $m = F_{2a}$ large enough so that $F_{2a-1} > k$ . Let $S_i = F_i \mod F_{2a}$ . Then $S_i = F_i$ for $1 \leq i < 2a, S_{2a} = 0$ , and it is easy to show by induction that for $0 < i < 2a,$ $S_{2a+i} = \begin{cases} F_{2a-i} &,\text{ if }i\text{ is odd}\\ F_{2a} - F_{2a-i} &,\text{ if }i\text{ is even}\end{cases}$ Then we find $S_{4a+1} = S_{4a+2} = 1$ , so $S_i$ repeats every $4a$ and thus produces no new values after $S_{4a}$ . However since $F_n \equiv k \mod F_{2a}$ for some $n$ yet $k$ is not a Fibonacci number and $k < F_{2a-1}$ , we have that $k$ must be of the form $F_{2a} - F_{2x}$ for some $1 \leq x \leq a-1$ . However the least number of this form is $F_{2a} - F_{2(a-1)} = F_{2a-1}$ , so $k > F_{2a-1}$ , contradiction, showing no such $k$ exists. $\blacksquare$

This post has been edited 1 time. Last edited by mathfun5, Jul 28, 2020, 9:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

56 posts

#6 h Jul 28, 2020, 9:44 AM • 1 Y

Y by vvluo

The answer is that k must be a Fibonacci number.

Claim 1: For all positive integers $m, n$ with $n\geq m\geq 2$ , $F_n F_m=F_{n+1}F_{m-1}+F_{n+1-m}(-1)^{m-1}$

Proof: Note $F_nF_2=F_n \cdot\ 1=F_n$ and $F_{n+1}F_{1}+F_{n-1}(-1)^1=F_{n+1}-F_{n-1}=F_{n}$ so this is true for $m=2$ and $F_{n}F_{3}=2F_{n}, F_{n+1}F_{2}+F_{n-2}(-1)^2=F_{n+1}+F_{n-2}=F_{n}+F_{n-1}+F_{n-2}=2F_{n}$ so this is also true for $m=3$ .

If it is true for $m-1$ and for $m$ , then $F_{n}F_{m+1}=F_{n}F_{m}+F_{n}F_{m-1}=F_{n+1}F_{m-1}+F_{n+1-m}(-1)^{m-1}+F_{n+1}F_{m-2}+F_{n+2-m}(-1)^{m-2}=F_{n+1}F_{m}+(-1)^{m-2}(F_{n+2-m}-F_{n+1-m})=F_{n+1}F_{m}+(-1)^mF_{n-m}$ so it is also true for $m+1$ .
By induction, this completes the proof of the claim.

Claim 2: When taking the Fibonacci sequence modulo F_{n+1}, all residues R with $F_{n-1}<R<F_{n}$ are missing for $n\geq 5$ (this just ensures that the set of such R is nonempty)

Proof: By letting $m=n$ in the above claim, $F_{n}^2=F_{n+1}F_{n-1}+F_{1}(-1)^{n-1} \Rightarrow F_{n+1}F_{n-1}-F_{n}^2=(-1)^n$ , so $F_{n}^2 \equiv 1$ or $-1$ mod $F_{n+1}$ .

If $F_{n}^2 \equiv 1$ mod $F_{n+1}$ , then when writing the sequence modulo $F_{n+1}$ , we will get $1, 1, 2, 3, ..., F_{n-1}, F_{n}, 0, F_{n}\times 1, F_{n}\times 1, F_{n}\times 2, ..., F_{n}F_{n-1}, F_{n}^2 (\equiv 1), 0, 1, 1, 2, 3...$ after which we see it will just repeat.
If If $F_{n}^2 \equiv -1$ mod $F_{n+1}$ , then when writing the sequence modulo $F_{n+1}$ , we will get $1, 1, 2, 3, ..., F_{n-1}, F_{n}, 0, F_{n}\times 1, F_{n}\times 1, F_{n}\times 2, ..., F_{n}F_{n-1}, F_{n}^2 (\equiv -1), 0, -1, -1, -2, -3, ..., -F_{n-1}, -F_{n}, 0, -F_{n}\times 1, -F_{n}\times 1,- F_{n}\times 2, ...,- F_{n}F_{n-1}, -F_{n}^2 (\equiv 1), 0, 1, 1, 2, 3 ...$ and we see that it will just repeat.

Therefore the possible residues we can get are $0, \pm F_{1}, \pm F_{2},..., \pm F_{n-1}, \pm F_{n}, \pm F_{n}F_{1}, \pm F_{n}F_{2}, ... , \pm F_{n}F_{n-1}, \pm F_{n}^2$ .

Note $F_{n-1}<R<F_{n} \Leftrightarrow F_{n}>F_{n+1}-R>F_{n-1}$ , so as none of $F_{1}, F_{2}, ... , F_{n-1}, F_{n}$ lie in the range $F_{n-1}<R<F_{n}$ , this means that when taken modulo $F_{n+1}$ , none of $-F_{1}, -F_{2}, ... , -F_{n-1}, -F_{n}$ do either.

By Claim 1, we know $F_n F_m=F_{n+1}F_{m-1}+F_{n+1-m}(-1)^{m-1} \equiv (-1)^{m-1}F_{n+1-m}$ mod $F_{n+1}$ for $n\geq m\geq 2$ .

Therefore we get that $\pm F_{n}F_{1} \equiv \pm F_{n}$ mod $F_{n+1}$ , and using the above, this means that $\pm F_{n}F_{1}, \pm F_{n}F_{2}, ... , \pm F_{n}F_{n-1}, \pm F_{n}^2$ in some order are congruent to $\pm F_{1}, \pm F_{2},..., \pm F_{n-1}, \pm F_{n}$ mod $F_{n+1}$ and we know that none of these leave a residue R in the required range. This completes the proof of the claim.

If k is not a Fibonacci number, then let $F_{r-1}<k<F_{r}$ . Then by the result of Claim 2, there is no positive integer n such that $F_{r+1} \mid F_{n}-k$ and so k must be a Fibonacci number.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

77 posts

#7 h Jul 28, 2020, 9:54 AM

Y by

Consider modulo $F_{2l - 2} + F_{2l}$ first $4l - 2$ elements of the sequence:
$F_1, F_2, ..., F_{2l - 1}, - F_{2l - 2}, F_{2l - 3}, - F_{2l - 4}, F_{2l - 5}, ..., - F_{2i}, F_{2i - 1}, ..., - F_2, F_1, 0,$ and after this remainders will be the same.
So, assume on the contrary, that $k$ isn't a Fibonacci number, picking $m = F_{2l - 2} + F_{2l} > k$ we must have that $k$ is of the form $F_{2l - 2} + F_{2l} - F_{2j}$ , where $j \le l - 2$ , but all these numbers are from the interval $[F_{2l} + F_{2l - 3} ; F_{2l} + F_{2l - 2}]$ , but choosing $l$ large enough, it's obvious, that $k$ can't belong to simultaneously all intervals $[F_{2l} + F_{2l - 3} ; F_{2l} + F_{2l - 2}]$ , where $l$ can be large enough, which concludes the proof.

This post has been edited 3 times. Last edited by mshtand1, Mar 31, 2022, 12:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

330 posts

#8 h Jul 28, 2020, 11:54 AM

Y by

mathfun5 wrote:

The answer is yes, and suppose for the sake of contradiction that such a $k$ exists, where $k$ is not a Fibonacci number. Then take $m = F_{2a}$ large enough so that $F_{2a-1} > k$ . Let $S_i = F_i \mod F_{2a}$ . Then $S_i = F_i$ for $1 \leq i < 2a, S_{2a} = 0$ , and it is easy to show by induction that for $0 < i < 2a,$ $S_{2a+i} = \begin{cases} F_{2a-i} &,\text{ if }i\text{ is odd}\\ F_{2a} - F_{2a-i} &,\text{ if }i\text{ is even}\end{cases}$ Then we find $S_{4a+1} = S_{4a+2} = 1$ , so $S_i$ repeats every $4a$ and thus produces no new values after $S_{4a}$ . However since $F_n \equiv k \mod F_{2a}$ for some $n$ yet $k$ is not a Fibonacci number and $k < F_{2a-1}$ , we have that $k$ must be of the form $F_{2a} - F_{2x}$ for some $1 \leq x \leq a-1$ . However the least number of this form is $F_{2a} - F_{2(a-1)} = F_{2a-1}$ , so $k > F_{2a-1}$ , contradiction, showing no such $k$ exists. $\blacksquare$

This is the best solution here

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

#9 h Jul 28, 2020, 11:58 AM • 14 Y

Y by Mathematicsislovely, Wizard_32, Superguy, ayan.nmath, Eliot, hansu, srijonrick, Juanscholtze, amar_04, Aritra12, pog, diegoca1, sabkx, L567

set $k=$ $\prod_{} p{_i} ^{r_i}$
put $m=k \implies f_u = \prod_{} p_{i} ^ {a_i} \times S$ such that $gcd(S,k)=1$ and $a_i \geq r_i$
put $m= \prod_{} p{_i}^{r_{i}+1} \times S$ now $f_v = \prod p_{i}^{r_i}\times T$ and $gcd (T,Sk)=1$
BUT $f_{gcd(v,u)}$ $=$ $gcd(f_{v},f_{u})$ = $k$ $\blacksquare$

This post has been edited 4 times. Last edited by Gaussian_cyber, Jul 28, 2020, 12:45 PM
Reason: hide

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

946 posts

Plops

#10 h Jul 28, 2020, 12:41 PM • 1 Y

Y by sabkx

This was my favorite problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1081 posts

#11 h Jul 28, 2020, 1:06 PM • 5 Y

Y by enzoP14, mijail, Mango247, Mango247, Mango247

Solution

This post has been edited 6 times. Last edited by blacksheep2003, Jul 28, 2020, 1:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

Eliot

#13 h Jul 28, 2020, 2:07 PM

Y by

$\mathrm{ }$

This post has been edited 1 time. Last edited by Eliot, Oct 1, 2020, 5:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4527 posts

#14 h Jul 28, 2020, 2:54 PM

Y by

If $F_{a-2}<k<F_{a-1}$ , there is a contradiction at $m=F_a$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#15 h Jul 28, 2020, 5:00 PM • 2 Y

Y by mijail, oceanxia

The answer is yes. We are given that for every $m\in \mathbb{N}$ , there exists a Fibonacci number that is $k\pmod m$ , with $k$ fixed. Consider the modulus $m=F_{2N}+F_{2N-2}$ for some $N$ . All equivalences that follow will be in mod $m$ .

Claim: $F_{2N+a} \equiv (-1)^{a+1}F_{2N-a-2}$ for all $a\ge 0$ .

Proof: This is easy to see by induction, base case $a=0$ obvious. We have
$\begin{align*} F_{2N+a+2}&=F_{2N+a+1}+F_{2N+a} \\ &\equiv (-1)^{a+2} F_{2N-a-3} + (-1)^{a+1} F_{2N-a-2} \\ &\equiv (-1)^a [F_{2N-a-3} - F_{2N-a-2}] \\ &\equiv (-1)^{a+3} F_{2N-a-4}. \end{align*}$ This completes the induction. $\square$

Now, the residues of $(F_0,\ldots,F_{4N-3})$ mod $m$ are
$(F_0, F_1,\ldots, F_{2N-1}, -F_{2N-2}, F_{2N-3}, -F_{2N-4}, F_{2N-5},\ldots, -F_2, F_1).$ Therefore, $F_{4N-2}\equiv F_0$ , $F_{4N-1} \equiv F_1$ . This means that the sequence $(F_i \mod m)$ for $i\ge 0$ is periodic with period $4N-2$ . So actually all the residues possible are in the list above.

Now, just take $N$ large enough so that $k+F_{2N-2} < m$ , i.e. $k<F_{2N}$ . Then, we can never have $k\equiv -F_{2N-2\ell}$ for any $\ell=1,\ldots,N-1$ since $k+F_{2N-2\ell} < m=F_{2N}+F_{2N-2}$ . This forces $k\equiv F_\ell$ for some $0\le \ell \le 2N-1$ . But since $F_{\ell},k < F_{2N} < m$ , this actually forces $k=F_{\ell}$ . The end.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10 posts

#16 h Jul 28, 2020, 5:53 PM

Y by

MarkBcc168 wrote:

Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\geq 3$ . Let $k$ be a positive integer. Suppose that for every positive integer m there exists a positive integer $n$ such that $m \mid F_n-k$ . Must $k$ be a Fibonacci number?

Proposed by Fedir Yudin.

We claim that the answer is $k = F_t$ for some $t \in \mathbb{N}$ .

Now, $a$ is a Fibonacci number if and only if either amongst $5a^2 \pm 4$ is a perfect square. So, $F_{t^\prime} \equiv k \pmod{p}$ for any prime $p$ which yields a contradiction as we can choose a large enough prime for which $k$ is not a quadratic residue (a lemma which states that given a natural number q, there exists a prime p such that $x^2 \equiv q \pmod{p}$ has no solutions.

Hence, it forces us to have that $k$ is a Fibonacci number.

Edit : Some people PMed me so here's the final conclusion logic : We have that $k \equiv F_{t^\prime} \equiv 5b^2 \pm 4 \pmod{p}$ . Now, we consider if $k \equiv 5b^2 + 4 \pmod{p}$ . Clearly, $b^2 \equiv \frac{k-4}{5} \pmod{p}$ and we can clearly choose a sufficiently large enough prime $p$ for which the fraction $\frac{k-4}{5}$ is not a quadratic residue using aforementioned lemma unless $k = 4, 9$ for which the given claim can be contradicted too and similarly we continue for $k \equiv 5b^2 -4$ .

This post has been edited 2 times. Last edited by babubhaiyya123, Jul 29, 2020, 7:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

109 posts

Eliot

#17 h Jul 28, 2020, 5:57 PM

Y by

babubhaiyya123 wrote:

We claim that the answer is $k = F_t$ for some $t \in \mathbb{N}$ .
Now, $a$ is a Fibonacci number if and only if either amongst $5a^2 \pm 4$ is a perfect square.

could you prove the second claim?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Imayormaynotknowcalculus

974 posts

Imayormaynotknowcalculus

#18 h Jul 28, 2020, 6:34 PM

Y by

Eliot wrote:

babubhaiyya123 wrote:

We claim that the answer is $k = F_t$ for some $t \in \mathbb{N}$ .
Now, $a$ is a Fibonacci number if and only if either amongst $5a^2 \pm 4$ is a perfect square.

could you prove the second claim?

This follows from the method of solving Pell's equation.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

132 posts

#19 h Jul 28, 2020, 9:19 PM • 22 Y

Y by Imayormaynotknowcalculus, rcorreaa, Loppukilpailija, Mathlete2017, Mathotsav, leibnitz, A-Thought-Of-God, achen29, CANBANKAN, Uagu, vwu, Juanscholtze, k12byda5h, ProblemSolver2048, TheBarioBario, Supercali, darkgreen-hand, 554183, CT17, puntre, centslordm, nguyenloc1712

Take the smallest $d>0$ such that $k|F_d$ . Hence there is $n$ such that
$F_d|F_n-k$ So $k|F_n$ . By $d$ 's minimality, $d|n$ and therefore $F_d |F_n$ , so $F_d|k$ , hence $k=F_d$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

330 posts

#20 h Jul 29, 2020, 1:02 PM

Y by

Gomes17 wrote:

Take the smallest $d>0$ such that $k|F_d$ . Hence there is $n$ such that
$F_d|F_n-k$ So $k|F_n$ . By $d$ 's minimality, $d|n$ and therefore $F_d |F_n$ , so $F_d|k$ , hence $k=F_d$ .

Wow this is nice

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

442 posts

#21 h Aug 3, 2020, 6:34 AM • 11 Y

Y by Mindstormer, Idio-logy, MarkBcc168, rocketscience, Imayormaynotknowcalculus, aops29, ghu2024, Supercali, MatBoy-123, bin_sherlo, L567

Take $m = F_s$ to be a fibonacci number divisible by $k^2$
Suppose $F_s \mid F_n - k$
We have $F_{\gcd(s,n)} = \gcd(F_n,F_s) = k$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

635 posts

#25 h Aug 5, 2020, 11:05 AM

Y by

We have $4$ lemmas from the problem

$F_{nk}$ is a multiple of $F_k \quad (\star)$
$F_{(m+n)}=F_mF_{(n+1)}+F_nF_{(m-1)} \quad (\bullet)$
$\sum_{i=0}^{2n+1}(2n+1i)F_i^2=5^n\cdot F_{(2n+1)}\quad (\square)$
$\gcd(F_m,F_n)=F_{(\gcd(m,n))}\quad(\diamondsuit)$

We will prove
Conjecture- For every prime $p,$ there exists a number $n$ such that $F_n=1\pmod{p}$ and $F_{n+1}=0\pmod{p}\implies F\,\text {is the periodic with the interval}=p.$
It can be solved by $(\bullet)$ and $(\square).$
This conjecture only $\implies (\square)$ when $p>5.$ We can verify that when
$p=2$
$F_{3\cdot 2^k}$ is divisible by $2^{k+1}.$

$p=3$
$F_{4\cdot 3^k}$ is divisible by $3^{k+1}$
$F_{5^k}$ is divisible by $5^k$

Factorisation

Conjecture 2- For prime $p$ and the number $k,$ if $n$ is the smallest number satisfies $F_n$ is divisible by $p\implies F_{n\cdot p^k}\,\text{is divisible by}\,p^{k+1}.$

This can be proved by induction, with the periodicity of $F$ in $\pmod{p}.$
From $(\star)$ and $(\diamondsuit)$ we can deduce that for every number $m,$ there exists index $n$ such that $F_n$ is the multiple of $m.$

There exists an index $n$ such that $p^k\mid F_n$ could be proved by applying pigeonhole theorem.
Proof- Assume at step $k,$ there exists an index $n$ such that $p^k\mid F_n.$ Consider all the values of $F_{nq}.$ There always exists $2$ values $q_1$ and $q_2$ such that $F_{nq_1}=F_{nq_2}(\pmod{p^{k+1}}).$
Applying $(\bullet)$ note that all $F_{nq+1}$ or $F_{nq-1}$ has the remainder $=1\text {modulo p},$ we obtain the desired index $q$ such that $F_{nq}=0 (\pmod {p^{k+1}}).$

Back to the main problem
For each number $k$ which is not a $\text{Fibonacci}$ number we take the smallest number $q$ such that $k\mid F_q.$ Choose $m=F_q.$
From this hypothesis $,F_n=k\pmod{F_q}$
We obtain $k\mid\gcd(F_n,F_q)=F_{\gcd(n,q)}$
combining with $q\implies q\mid\gcd(n,q)\implies q\mid n.$
So $F_q\mid k$ leads to a contradiction.
For the converse part $,$ if $k=F_q.$ For every number $m,$ there exists $r$ such that $F_r$ is divided by $m.$ Choose number $n$ such that $n=q\pmod{r}\implies F_n=F_q\pmod{F_r}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ProblemSolver2048

104 posts

ProblemSolver2048

#26 h Oct 1, 2020, 3:41 PM

Y by

Gomes17 wrote:

Take the smallest $d>0$ such that $k|F_d$ . Hence there is $n$ such that
$F_d|F_n-k$ So $k|F_n$ . By $d$ 's minimality, $d|n$ and therefore $F_d |F_n$ , so $F_d|k$ , hence $k=F_d$ .

how is it that nice

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ProblemSolver2048

104 posts

ProblemSolver2048

#27 h Oct 1, 2020, 3:52 PM

Y by

I think that all of these posts were quite similar though this one involved quadratic residues which was already mentioned though I mean there arent really that many solutions that you can think of, I edited this one a bit though.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#28 h Jun 29, 2021, 10:29 PM • 2 Y

Y by mathlete5451006, centslordm

The answer is yes.

Lemma: For all $k\ge 2$ , $F_k^2 + (-1)^k = F_{k-1}F_{k+1}$ .

Proof: We use induction. The base case is immediate. For $k\ge 3$ , write
$F_{k-1}F_{k+1} = F_{k-1}^2 + F_{k-1}F_k = F_{k-2}F_k - (-1)^{k-1} + F_{k-1}F_k = F_k^2 + (-1)^k$ by the inductive hypothesis.

This enables us to determine the residues of Fibonacci numbers modulo other Fibonacci numbers much more efficiently. In particular, note that as $F_k\equiv 0\pmod{F_k}$ and $F_{k+1} \equiv F_{k-1}\cdot 1\pmod{F_k}$ , we have $F_a \equiv F_{k-1} \cdot F_{a-k}\pmod{F_k}$ for all $a>k$ , and so $F_a\equiv F_{a-4k}\pmod{F_k}$ for all $a>4k$ .

Then for each $n$ , to check whether it is congruent to a Fibonacci number modulo $F_k$ it is sufficient to check the Fibonacci numbers $F_1, F_2, \dots, F_{4k}$ . It is well-known that every positive integer divides a Fibonacci number (use pigeonhole principle then work backwards), so we only need to worry about Fibonacci numbers anyway. In fact, every positive integer must divide a Fibonacci number of the form $F_{2k}$ . So consider some positive integer $n$ that is not a Fibonacci number but is congruent to Fibonacci numbers modulo $F_{2k}$ and $F_{2k-2}$ . Then by an analogous argument before, we can say $n\equiv F_{t_1}$ or $n\equiv F_{t_1}F_{2k-1}$ modulo $F_{2k}$ for some $1\le t_1\le 2k$ , and $n\equiv F_{t_2}$ or $n\equiv F_{t_2}F_{2k-1}$ modulo $F_{2k-2}$ for some $1\le t_2\le 2k-2$ . We check beforehand that $F_{2k-2} > n$ . Thus it is certainly not congruent to $F_{t_1}$ or $F_{t_2}$ modulo either. Moreover, this ensures $t_2\ne 2k-2$ and $t_1\ne 2k$ because otherwise $n$ is a Fibonacci number, contradicting the assumption. Observe that $t_1 = 2k-1$ would yield $n\equiv F_{2k-1}^2 \equiv F_{2k}F_{2k-2} + 1 \equiv 1\pmod{F_{2k}}$ . As $1$ is a Fibonacci number, this would also contradict the assumption. So $1\le t_1\le 2k-2$ . Analogously, $1\le t_2\le 2k-4$ . Let $n = F_{t_1}F_{2k-1} - aF_{2k}$ for some $a < F_{2k-1}$ and $n = F_{t_2}F_{2k-1} - bF_{2k-2}$ for some $b < F_{2k-1}$ . To see the inequalities, note
$aF_{2k} < F_{t_1}F_{2k-1} < F_{2k}F_{2k-1}, bF_{2k-2} < F_{t_2}F_{2k-1} < F_{2k-2}F_{2k-1}.$ Then
$(F_{t_1} - F_{t_2})F_{2k-1} = aF_{2k} - bF_{2k-2} = aF_{2k-1} + (a-b)F_{2k-2}.$ Modulo $F_{2k-1}$ , this implies $a=b$ because $\gcd(F_{2k-2},F_{2k-1}) = 1$ and $|a-b| < F_{2k-1}$ . Moreover, $b = a=F_{t_1} - F_{t_2}$ . So
$n = F_{t_1}F_{2k-1} - (F_{t_1} - F_{t_2})F_{2k} = F_{t_1}(F_{2k+1} - F_{2k}) - (F_{t_1} - F_{t_2})F_{2k} = F_{t_1}F_{2k+1} - (2F_{t_1}-F_{t_2})F_{2k}.$ But by an analogous argument, supposing $n$ is a Fibonacci number modulo $F_{2k+2}$ as well, we can also write this number as
$F_{t_4}F_{2k+1} - (F_{t_3} - F_{t_4})F_{2k}$ for some $t_3 \le 2k, t_4 \le 2k-2$ . Thus, we have
$(F_{t_4} - F_{t_1})F_{2k+1} = F_{2k}\cdot (F_{t_3} - F_{t_4} + F_{t_2} - 2F_{t_1}).$ It is clear that $\gcd(F_{2k}, F_{2k+1}) = 1$ , so because $F_{2k}\mid F_{t_4} - F_{t_1}$ , we must have $t_4 = t_1$ . Thus $F_{t_3} + F_{t_2} = 3F_{t_1}$ . As $F_{t_2} < F_{t_1}$ and $F_{t_3} > F_{t_4} = F_{t_1}$ , we must have $2F_{t_1} < F_{t_3} < 3F_{t_1}$ . This can only occur if $F_{t_3} = F_{t_1+2}$ . This is because $F_{t_1} < F_{t_1+1} < F_{t_1} + F_{t_1-1}$ and $F_{t_1+2} = F_{t_1} + F_{t_1} + F_{t_1-1}$ . So $t_1 + 2 = t_3$ and $t_1 - 2 = t_2$ . So the original formula was
$n = F_{t_1}F_{2k-1} - F_{t_1-1}F_{2k} = (F_{t_1-1}+F_{t_1-2})F_{2k-1} - F_{t_1-1}(F_{2k-1}+F_{2k-2}) = F_{t_1-2}F_{2k-1} - F_{t_1-1}F_{2k-2} =$ $F_{t_1-2}(F_{2k-2}+F_{2k-3}) - (F_{t_1-2}+F_{t_1-3})F_{2k-2} = F_{t_1-2}F_{2k-3} - F_{t_1-3}F_{2k-2}.$ Iterating, we eventually get that for some $x$ , either $n = 2F_{2x-1} - F_{2x} = F_{2x-1} - F_{2x-2} = F_{2x-3}$ or $n = F_{2x-1} - F_{2x} = -F_{2x-2}$ . Either way, we get a contradiction, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#29 h Aug 11, 2023, 1:46 PM • 1 Y

Y by centslordm

The answer is yes. Let $\alpha=\tfrac{1+\sqrt{5}}{2}$ , so $F_n=\tfrac{\alpha^n-(-\alpha)^{-n}}{\sqrt{5}}$ . It is well-known that $k$ is a Fibonacci number iff at least one of $5k^2-4$ and $5k^2+4$ is a perfect square.

Suppose that $k$ was not a Fibonacci number, so neither $5k^2-4$ nor $5k^2+4$ are squares. Let $p_1,\ldots,p_a$ be the odd primes dividing $5k^2-4$ with $\nu_{p_i}(5k^2-4)$ odd, and $q_1,\ldots,q_b$ be the odd primes dividing $5k^2+4$ with $\nu_{q_i}(5k^2+4)$ . Note that these are all distinct, since $\gcd(5k^2-4,5k^2+4) \mid 8$ , and none of these can be $5$ . If both $a \geq 1$ and $b \geq 1$ , then by Dirichlet pick some prime $p \equiv 1 \pmod{8}$ , $p \equiv 1 \pmod{5}$ , $p \equiv 1 \pmod{p_i}$ and $p \equiv 1 \pmod{q_i}$ for $i \geq 2$ , and $p$ equivalent to non-quadratic residues modulo $p_1$ and $q_1$ . Because $p \equiv 1 \pmod{8}$ , we have $(\tfrac{p}{q})(\tfrac{q}{p})=1$ for any odd prime $q$ , and $(\tfrac{2}{p})=1$ . Then,
$\left(\frac{5k^2-4}{p}\right)=\left(\frac{\varepsilon p_1\ldots p_a}{p}\right)=\left(\frac{\varepsilon}{p}\right)\left(\frac{p_1}{p}\right)\ldots\left(\frac{p_a}{p}\right)=\left(\frac{p}{p_1}\right)\ldots\left(\frac{p}{p_a}\right)=-1,$ where $\varepsilon \in \{1,2\}$ based on the parity of $\nu_2(5k^2-4)$ . Likewise, $(\tfrac{5k^2+4}{p})=-1$ . If $\min\{a,b\}=0$ , i.e. one of $5k^2-4$ and $5k^2+4$ is twice a perfect square, then the another one cannot be by looking at $\nu_2$ , so WLOG let $a=0$ and $b \geq 1$ . Then pick some prime $p \equiv 5 \pmod{8}$ , $p \equiv 1 \pmod{5}$ , $p \equiv 1 \pmod{q_i}$ for $i \geq 2$ , and $p$ equivalent to a non-quadratic residue modulo $q_1$ . We still have $(\tfrac{p}{q})(\tfrac{q}{p})=1$ , but now $(\tfrac{2}{p})=-1$ . For a similar reason to before, $(\tfrac{5k^2+4}{p})=-1$ , and $(\tfrac{5k^2-4}{p})=(\tfrac{2}{p})=-1$ .
Furthermore, for this value of $p$ , since $(\tfrac{5}{p})=(\tfrac{p}{5})=1$ , $\sqrt{5} \in \mathbb{F}_p \implies \alpha \in \mathbb{F}_p \implies \alpha^n \in \mathbb{F}_p$ . Therefore, one of the following equations must have a root in $\mathbb{F}_p$ :
$x+\frac{1}{x}=k\sqrt{5} \iff x^2-k\sqrt{5}+1=0 \text{ or } x-\frac{1}{x}=k\sqrt{5} \iff x^2-k\sqrt{5}-1=0.$ By using the quadratic formula, this means that either $5k^2-4$ or $5k^2+4$ is a square in $\mathbb{F}_p$ , but this contradicts the construction of $p$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#30 h Feb 28, 2025, 12:58 AM

Y by

First, we prove the results
$\begin{align*} F_{4n+2} &= F_{2n+1}(F_{2n+2}+F_{2n}) \\ F_{4n+3} &= F_{2n+2}(F_{2n+2}+F_{2n}) + 1 \end{align*}$ Therefore, taking the fibonacci sequence $\pmod {F_{2n+2}+F_{2n}}$ loops very quickly, specifically with period $4n+2$ . Therefore, the sequence will loop in the following way: first the $2n+1$ fibonacci numbers, then the reverse fibonacci sequence $F_{-1}$ , $F_{-2}$ , $F_{-3}$ , $\dots$ , which is just the fibonacci numbers times $(-1)^n$ , so as long as $k$ , the non-fibonacci number, is less than the $2n+1$ th fibonacci number, $k$ does not appear as a residue class. Pick $n$ as large as needed, proving that $k$ must be a fibonacci number.

Here is an example visualizing this, with $F_6+F_8=29$ :
$0,1,1,2,3,5,8,13,21\text{ or }-8,5,26\text{ or }-3,2,28\text{ or }-1,1,0$ All non-fibonacci numbers less than $13$ are immediately ruled out.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3363 posts

#31 h Mar 18, 2025, 5:53 PM

Y by

The answer is yes. For contradiction, assume that there exists a $k$ that satisfies the condition and is not a Fibonacci number. Recall that $F_n$ is always periodic $(\text{mod }k)$ , so we can find some $\ell$ such that $k \mid F_{\ell}$ . Also, recall the well-known fact that $\operatorname{gcd}(F_k, F_\ell) = F_{\operatorname{gcd}(k, \ell)}$ . Setting $m = F_\ell$ , we have that $\begin{align*} k = \operatorname{gcd}(F_n, F_\ell) = F_{\operatorname{gcd}(n, \ell)}\end{align*}$ which gives us the desired contradiction. $\square$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a