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 必须为整数且分数已约分，其分母为一。因此 2^k 模 2015 同余于一。