Question

The sequence $(a_n)$ is defined recursively by $a_0=1,$ $a_1=\sqrt[19]{2},$ and $a_n=a_{n-1}a_{n-2}^2$ for $n\ge2.$ What is the smallest positive integer $k$ such that the product $a_1a_2\cdots a_k$ is an integer?

$17$

$18$

$19$

$20$

$21$

Answer: A

Concepts:recursion modular arithmetic multiplicative order

Difficulty rating: 2650

Solution:

Write $a_n=2^{b_n/19}.$ The recursion becomes $b_0=0,$ $b_1=1,$ $b_n=b_{n-1}+2b_{n-2},$ solved by $b_n=\tfrac13\bigl(2^n-(-1)^n\bigr).$ The product $a_1\cdots a_k$ is an integer exactly when $19\mid b_1+\cdots+b_k.$ Summing the formula for $b_n$ gives $b_1+\cdots+b_k=\dfrac{2^{k+1}-1}{3}$ when $k$ is odd, and $b_1+\cdots+b_k=\dfrac{2^{k+1}-2}{3}$ when $k$ is even.

The order of $2$ modulo $19$ is $18$ because $2^9\equiv-1\pmod{19}$ and $2^6\not\equiv1\pmod{19}.$ For odd $k,$ divisibility therefore requires $18\mid k+1,$ first occurring at $k=17.$ For even $k,$ it requires $18\mid k,$ first occurring at $k=18.$ Hence the smallest positive $k$ is $17.$

Thus, the correct answer is A.

2016 AMC 12B Problem 25

Answer: A

Difficulty rating: 2650

Solution:

Problem 25 in Other Years