Solve by using modulo. Or something else

Question

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?

Answer 1

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.

Answer 2

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.