最大公約数を含む漸化式

今回は、一般項を表すことができない数列について考えてみます。それでは、よろしくお願いします。

問題

解答

数列を観察してみると、\(a_n = 3\) となるような \(n\) が多いことがわかる。特に、\(\gcd(a_{n-1},n-1) = 1\) の場合に \(3\) となっていることがわかる。 このことから、逆に、\(a_{k}=2m+1\) となるためには、\(\gcd(a_{k-1},k-1) = 2m-1\) が必要であることがわかる。 ここで、\(a_{k-1}\) は \(2m-1\) しかあり得ないため、\(k-1\) が \(2m-1\) の倍数であればよいことがわかる。同様にして、\(k-2,k-3, \cdots \) がそれぞれ \(2m-3,2m-5, \cdots \) の倍数であれば良いことがわかる。 これらをまとめると、 \begin{align*} k & \equiv 1 \pmod {15} \\ k & \equiv 2 \pmod {13} \\ k & \equiv 3 \pmod {11} \\ k & \equiv 4 \pmod {9} \\ k & \equiv 5 \pmod {7} \\ k & \equiv 6 \pmod {5} \\ k & \equiv 7 \pmod {3} \\ \end{align*} となる。これを整理して、 \begin{align*} k & \equiv 1 \pmod {15} \\ k & \equiv 2 \pmod {13} \\ k & \equiv 3 \pmod {11} \\ k & \equiv 4 \pmod {9} \\ k & \equiv 5 \pmod {7} \\ \end{align*} ここで、中国剰余定理より、\(k \equiv 22531 \pmod{45045}\) を得る。 逆に、\(k = 45045l + 22531\) とすれば題意を満たし、このような正整数は無限に存在することから題意は示された。