正の整数 $x$ を素因数分解したときに現れるすべての素数を一度ずつ掛け合わせて得られる積を $\text{rad}(x)$ で表す。例えば、$\text{rad}(12) = 6$, $\text{rad}(32) = 2$ である。また、$\text{rad}(1) = 1$ とする。数列 $\{a_n\}$ を $a_1 = 1$, $a_{n+1} = a_n + \text{rad}(a_n)$ ($n = 1, 2, 3, \dots$) で定義する。このとき、$a_{100}$ を 29 で割った余りを求めよ。

1. 問題の内容

正の整数 $x$ を素因数分解したときに現れるすべての素数を一度ずつ掛け合わせて得られる積を $\text{rad}(x)$ で表す。例えば、$\text{rad}(12) = 6$, $\text{rad}(32) = 2$ である。また、$\text{rad}(1) = 1$ とする。数列 $\{a_n\}$ を $a_1 = 1$, $a_{n+1} = a_n + \text{rad}(a_n)$ ($n = 1, 2, 3, \dots$) で定義する。このとき、$a_{100}$ を 29 で割った余りを求めよ。

2. 解き方の手順

まず、数列 $\{a_n\}$ の最初のいくつかの項を計算してみる。

$a_1 = 1$

$a_2 = a_1 + \text{rad}(a_1) = 1 + \text{rad}(1) = 1 + 1 = 2$

$a_3 = a_2 + \text{rad}(a_2) = 2 + \text{rad}(2) = 2 + 2 = 4$

$a_4 = a_3 + \text{rad}(a_3) = 4 + \text{rad}(4) = 4 + 2 = 6$

$a_5 = a_4 + \text{rad}(a_4) = 6 + \text{rad}(6) = 6 + 6 = 12$

$a_6 = a_5 + \text{rad}(a_5) = 12 + \text{rad}(12) = 12 + 6 = 18$

$a_7 = a_6 + \text{rad}(a_6) = 18 + \text{rad}(18) = 18 + 6 = 24$

$a_8 = a_7 + \text{rad}(a_7) = 24 + \text{rad}(24) = 24 + 6 = 30$

数列の各項を 29 で割った余りを計算する。

$a_1 \equiv 1 \pmod{29}$

$a_2 \equiv 2 \pmod{29}$

$a_3 \equiv 4 \pmod{29}$

$a_4 \equiv 6 \pmod{29}$

$a_5 \equiv 12 \pmod{29}$

$a_6 \equiv 18 \pmod{29}$

$a_7 \equiv 24 \pmod{29}$

$a_8 \equiv 30 \equiv 1 \pmod{29}$

ここで、$a_8 \equiv a_1 \pmod{29}$ であることに注意する。また、$\text{rad}(x)$ の値も $x$ を 29 で割った余りによって決まるため、$a_n \pmod{29}$ が同じ値をとれば、それ以降の項も同じように繰り返すと考えられる。

数列 $\{a_n \pmod{29}\}$ は周期 7 で繰り返すことが予想される。したがって、$a_{n+7} \equiv a_n \pmod{29}$ である。

$100 = 7 \times 14 + 2$ なので、$a_{100} \equiv a_2 \pmod{29}$ となる。

$a_{100} \equiv a_2 \equiv 2 \pmod{29}$

3. 最終的な答え

2