今日の一問 #3──漸化式のどこかで必ず割り切れる？

問題

互いに素な3以上の整数の組$${(p, q)}$$があり、数列$${\{a_n\}}$$を

$$
\begin{cases} a_1=1 \\ a_{n+1}=pa_{n}+1 \end{cases}
$$

で定める。このとき、この数列のどこかに$${q}$$の倍数があることを示してください。
（オリジナル）

解答例

もちろん色々な解答があると思いますが。私が一番シンプルだと思ったのはこんな感じ。
（字の汚さはゴメンネ！）

n進法の話と鳩の巣原理を組み合わせた感じの問題です。

多分フェルマーの小定理とか使えばもっと早いのだと思いますがこの試行錯誤している感じが私は好きです😊

これからもおもしろい問題を探したいと思います！

この記事を面白いと思ってくれた方は、❤️とコメントをお願いいたします🙇‍♂️

▼おすすめ記事