Number theoryDifficulty 5.5AIME, harderProve itSaudi Arabia
Let (Fn)n≥0 be the sequence of Fibonacci numbers: F0=0, F1=1 and Fn+2=Fn+1+Fn, for every n≥0. Prove that for any prime p≥3, p divides F2p−Fp.
Solution
Observe that F2p=51(21+5)2p−(21−5)2p=51[(21+5)p−(21−5)p][(21+5)p+(21−5)p]=FpLp where Ln is the Lucas number, that is Ln=(21+5)n+(21−5)n,n=0,1,… it follows F2p−Fp=FpLp−Fp=Fp(Lp−1). Now =Lp−1=(21+5)p+(21−5)p−12p−11[(0p)+(2p)5+…+(p−1p)52p−1]−1 =2p−11[(2p)5+(4p)52+…+(p−1p)52p−1−(2p−1−1)], hence p∣Lp−1, since p divides (2p),(4p),…,(p−1p), and 2p−1−1, and 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.