Problem 3

A sequence of real numbers

a_0,a_1,\ldots

is said to be good if: (i)

a_0

is a positive integer; (ii) for each non-negative integer

i

a_{i+1}=2a_i+1

a_{i+1}=\frac{a_i}{a_i+2}

; (iii) there exists a positive integer

k

such that

a_k=2014

. Find the smallest positive integer

n

such that there exists a good sequence with

a_n=2014

Step 3 of 4: Use the modular invariant

Previous step Next step

(m_i,n_i)\equiv(-2^i,2^i)\pmod{2015}

Detailed analysis

The two inverse updates preserve the displayed congruence by induction. Since a_0 must be an integer and the fraction is reduced, its denominator is one. Thus 2^k is congruent to one modulo 2015.