Maths Olympiad Prep

Library / /77 of 120

Number theory Difficulty 5.5 AIME, harder Prove it Saudi Arabia

Let (Fn)n0\left(F_{n}\right)_{n \geq 0} be the sequence of Fibonacci numbers: F0=0F_{0}=0, F1=1F_{1}=1 and Fn+2=Fn+1+FnF_{n+2}=F_{n+1}+F_{n}, for every n0n \geq 0. Prove that for any prime p3p \geq 3, pp divides F2pFpF_{2p}-F_{p}.

Solution

Observe that
F2p=15[(1+52)2p(152)2p]=15[(1+52)p(152)p][(1+52)p+(152)p]=FpLp \begin{gathered} F_{2p} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{2p} - \left( \frac{1-\sqrt{5}}{2} \right)^{2p} \right] \\ = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^p - \left( \frac{1-\sqrt{5}}{2} \right)^p \right] \left[ \left( \frac{1+\sqrt{5}}{2} \right)^p + \left( \frac{1-\sqrt{5}}{2} \right)^p \right] \\ = F_p L_p \end{gathered}
where LnL_n is the Lucas number, that is
Ln=(1+52)n+(152)n,n=0,1, L_n = \left( \frac{1+\sqrt{5}}{2} \right)^n + \left( \frac{1-\sqrt{5}}{2} \right)^n, \quad n=0,1, \ldots
it follows F2pFp=FpLpFp=Fp(Lp1)F_{2p} - F_p = F_p L_p - F_p = F_p (L_p - 1). Now
Lp1=(1+52)p+(152)p1=12p1[(p0)+(p2)5++(pp1)5p12]1 \begin{aligned} & L_p - 1 = \left( \frac{1+\sqrt{5}}{2} \right)^p + \left( \frac{1-\sqrt{5}}{2} \right)^p - 1 \\ = & \frac{1}{2^{p-1}} \left[ \binom{p}{0} + \binom{p}{2} 5 + \ldots + \binom{p}{p-1} 5^{\frac{p-1}{2}} \right] - 1 \end{aligned}
=12p1[(p2)5+(p4)52++(pp1)5p12(2p11)], = \frac{1}{2^{p-1}} \left[ \binom{p}{2} 5 + \binom{p}{4} 5^{2} + \ldots + \binom{p}{p-1} 5^{\frac{p-1}{2}} - \left(2^{p-1} - 1\right) \right],
hence pLp1p \mid L_p - 1, since pp divides (p2),(p4),,(pp1)\binom{p}{2}, \binom{p}{4}, \ldots, \binom{p}{p-1}, and 2p112^{p-1} - 1, and gcd(p,2)=1\gcd(p, 2) = 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.