MathLabs

第3問

実数列 a0,a1,…a_0,a_1,\ldots が良い列であるとは、(i) a0a_0 が正整数、(ii) 任意の非負整数 ii で ai+1=2ai+1a_{i+1}=2a_i+1 または ai+1=aiai+2a_{i+1}=\frac{a_i}{a_i+2}、(iii) ある正整数 kk で ak=2014a_k=2014 となることをいう。an=2014a_n=2014 となる良い列が存在するような最小の正整数 nn を求めよ。
ステップ 3/4: 合同式の不変量を使う
前のステップ次のステップ
(mi,ni)≡(−2i,2i)(mod2015)(m_i,n_i)\equiv(-2^i,2^i)\pmod{2015}
詳しい解説

二つの逆更新はいずれも帰納的に表示の合同式を保つ。a_0 は整数で既約分数なので分母は1である。従って 2^k は2015を法として1に合同である。