MathDB
k and k(m)

Source: 2022 Viet Nam math olympiad for high school students D2 P2

March 21, 2023
algebra

Problem Statement

Given Fibonacci sequence (Fn),(F_n), and a positive integer mm. a) Prove that: there exists integers 0≤i<j≤m20\le i<j\le m^2 such that Fi≡Fj( mod m)F_i\equiv F_j (\bmod m) and Fi+1≡Fj+1( mod m)F_{i+1}\equiv F_{j+1}(\bmod m).
b) Prove that: there exists a positive integer kk such that Fn+k≡Fn( mod m),F_{n+k}\equiv F_n(\bmod m), for all natural numbers nn.
*Denote k(m)k(m) by the smallest positive integer satisfying Fn+k(m)≡Fn( mod m),F_{n+k(m)}\equiv F_n(\bmod m), for all natural numbers nn*. c) Prove that: k(m)k(m) is the smallest positive integer such that Fk(m)≡0( mod m)F_{k(m)}\equiv 0(\bmod m) and Fk(m)+1≡1( mod m)F_{k(m)+1}\equiv 1(\bmod m).
d) Given a positive integer kk. Prove that: Fn+k≡Fn( mod m)F_{n+k}\equiv F_n(\bmod m) for all natural numbers nn iff k⋮k(m)k\vdots k(m).
Back to ProblemsView on AoPS