Solve by using modulo. Or something else An infinite sequence of positive integers $a_1, a_2,\ldots$ has the properties that for $k\geq2$, the $k^\text{th}$ element is equal to $k$ plus the product of the first $k-1$ elements of the sequence. Suppose $a_1 =1$. what is the smallest prime number that does not divide $a_{2010}$?
I have a feeling you have to use mod? But how do you find the twenty tenth number of the sequence?
 A: I believe the answer is $5$. Here's why. First of all the answer can't be $2$ or $3$. It's easy enough to see why (hint: 2010 is divisible by 2 and 3). Now generate the series modulo $5$.


*

*$a_1=1$

*$a_2=3$

*$a_3=1$

*$a_4=2$

*$a_5=1$

*$a_6=2$

*$a_7=4$

*$a_8=1$


Notice that $a_3=a_8$. Also the fact that $$8 \equiv 3 \mod 5$$. I claim that the numbers will cycle from here onwards. Here's why:
The recurrence form of this relation is $$a(n+1)=a(n)^2-n\cdot a(n) + (n+1) \mod 5\ \ \ n \geq2 $$ Now all of these operations are preserved modulo $5$
. Hence if $a_3=a_8$,$$a_n=a_{5k+n}$$ Using this, you can predict the remainder that $a_{2010}$ leaves when divided by $5$ (it's $1$). Hence the smallest required prime number is 5.
A: Modular arithmetic is congruent under multiplication, so we can define sequences $a_k^{(2)}$, $a_k^{(3)}$, $a_k^{(5)}$, etc. to represent the sequences modulo 2, 3, and 5 respectively.
Thanks to congruency we still have the recurrence:
$$a_k^{(p)} \equiv \prod_{i=1}^{k-1}a_i^{(p)} + k \mod p$$
Now it remains to look at patterns in sequences $a^{(p)}_k$.
Modulo 2:
Note:
$$a_3^{(2)} \equiv 6 \equiv 0 \mod 2$$
So for any $k>3$, the product term is zero mod 2. Hence we simplify for large $k$ to:
$$a_k^{(2)} \equiv k \mod 2$$
So 2 divides $a_{2010}$ since $2010 \equiv 0 \mod 2$.
Mod 3:
Same approach:
$$a_3^{(3)} \equiv 6 \equiv 0 \mod 3$$
Hence, with the same reasoning,
$$a_{2010}^{(3)} \equiv 2010 \equiv 0 \mod 3$$
So 3 is not the factor we are looking for.
Mod 5:
First notice:
$$a_1^{(5)} a_2^{(5)} \equiv 1 \times 3 \equiv 3 \mod 5$$
Let's list out the next few terms:
$$
\begin{split}
a_3^{(5)} &\equiv 3 + 3 \equiv 1 &\mod 5 \newline
a_4^{(5)} &\equiv 3 \cdot 1 + 4 \equiv 2 &\mod 5 \newline
a_5^{(5)} &\equiv 3 \cdot 1 \cdot 2 + 5 \equiv 1 &\mod 5 \newline
a_6^{(5)} &\equiv 3 \cdot 1 \cdot 2 \cdot 1 + 6 \equiv 2 &\mod 5 \newline
a_7^{(5)} &\equiv 3 \cdot 1 \cdot 2 \cdot 1 \cdot 2 + 7 \equiv 4 &\mod 5
\end{split}
$$
Now let's look at $a_8^{(5)}$.
$$a_8^{(5)} \equiv 3 \cdot 1 \cdot 2 \cdot 1 \cdot 2 \cdot 4 + 8 \equiv 3 + 3 \mod 5$$
Note how the product term has reset itself to 3 mod 5! This means we have entered into a cycle, since the recurrence into $a_9^{(5)}$ will be like the recurrence into $a_4^{(5)}$, and so on. Indeed, $a_{k+5}^{(5)} = a_{k}^{(5)}$ for all sufficiently large $k$. Notice how the remainder never reaches 0, so 5 is our final answer.
