Putnam 2015, Problem A-2

Let $a_0 = 1$, $a_1 = 2$, and $a_n = 4a_{n-1} - a_{n-2}$ for $n \geq 2$. Find an odd prime factor of $a_{2015}$.

Solution:
First solution: One possible answer is 181. By induction, we have \(a_n = \frac{(2 + \sqrt{3})^n + (2 - \sqrt{3})^n}{2} = \frac{\alpha^n + \beta^n}{2}\) for all \(n\), where \(\alpha = 2 + \sqrt{3}\) and \(\beta = 2 - \sqrt{3}\). Now note that if \(k\) is an odd positive integer and \(a_n \neq 0\), then \(\frac{a_{kn}}{a_n} = \frac{\alpha^{kn} + \beta^{kn}}{\alpha^n + \beta^n} = \alpha^{(k-1)n} - \alpha^{(k-2)n}\beta^n + \cdots - \alpha^n\beta^{(k-2)n} + \beta^{(k-1)n}\). This expression is both rational (because \(a_n\) and \(a_{kn}\) are integers) and of the form \(a + b\sqrt{3}\) for some integers \(a, b\) by the expressions for \(\alpha, \beta\); it follows that it must be an integer, and so \(a_{kn}\) is divisible by \(a_n\). Applying this to \(n = 5\) and \(k = 403\), we find that \(a_{2015}\) is divisible by \(a_5 = 362\) and thus by 181.

Second solution: By rewriting the formula for \(a_n\) as \(a_{n-2} = 4a_{n-1} - a_n\), we may extend the sequence backwards to define \(a_n\) for all integers \(n\). Since \(a_{-1} = 2\), we may see by induction that \(a_{-n} = a_n\) for all \(n\). For any integer \(m\) and any prime \(p\) dividing \(a_m\), \(p\) also divides \(a_{-m}\); on the other hand, \(p\) cannot divide \(a_{-m+1}\), as otherwise \(p\) would also divide \(a_{-m+2}, \ldots, a_0 = 1\), a contradiction. We can thus find an integer \(k\) such that \(a_{m+1} \equiv ka_{-m+1} \pmod{p}\); by induction on \(n\), we see that \(a_n \equiv ka_{n-2m} \pmod{p}\) for all \(n\). In particular, if \(k\) is odd, then \(p\) also divides \(a_{km}\); we thus conclude (again) that \(a_{2015}\) is divisible by \(a_5 = 362\) and thus by 181.

Remark: Although it was not needed in the solution, we note in passing that if \(a_n \equiv 0 \pmod{p}\), then \(a_{2n+k} \equiv -a_k \pmod{p}\) for all \(k\).

Remark: One can find other odd prime factors of \(a_{2015}\) in the same manner. For example, \(a_{2015}\) is divisible by each of the following quantities. (The prime factorizations were computed using the Magma computer algebra system.)
\[
\begin{align*}
a_{13} &= 2 \times 6811741 \\
a_{31} &= 2 \times 373 \times 360250962984637 \\
a_{5 \cdot 13} &= 2 \times 181 \times 6811741 \\
&\quad \times 3045046274679316654761356161 \\
a_{5 \cdot 31} &= 1215497709121 \times 28572709494917432101 \\
&\quad \times 13277360555506179816997827126375881581 \\
a_{13 \cdot 31} &= 2 \times 373 \times 193441 \times 6811741 \times 360250962984637 \\
&\quad \times 16866100753000669 \\
&\quad \times 79988387992470656916594531961 \times p_{156}
\end{align*}
\]
where \(p_{156}\) is a prime of 156 decimal digits. Dividing \(a_{2015}\) by the product of the primes appearing in this list yields a number \(N\) of 824 decimal digits which is definitely not prime, because \(2^N \not\equiv 2 \pmod{N}\), but whose prime factorization we have been unable to establish. Note that \(N\) is larger than a 2048-bit RSA modulus, so the difficulty of factoring it is not surprising.

One thing we can show is that each prime factor of \(N\) is congruent to 1 modulo \(6 \times 2015 = 12090\), thanks to the following lemma.

Lemma. Let \(n\) be an odd integer. Then any odd prime factor \(p\) of \(a_n\) which does not divide \(a_m\) for any divisor \(m\) of \(n\) is congruent to 1 modulo \(\operatorname{lcm}(6, n)\). (By either solution of the original problem, \(p\) also does not divide \(a_m\) for any positive integer \(m < n\).)

Proof. We first check that \(p \equiv 1 \pmod{3}\). In \(\mathbb{F}_q = \mathbb{F}_p(\sqrt{3})\) we have \((\alpha/\beta)^n \equiv -1\). If \(p \equiv 2 \pmod{3}\), then \(q = p^2\) and \(\alpha\) and \(\beta\) are conjugate in \(p\); consequently, the equality \(\alpha^n = -\beta^n\) in \(\mathbb{F}_{q^2}\) means that \(\alpha^n = c\sqrt{3}\), \(\beta^n = -c\sqrt{3}\) for some \(c \in \mathbb{F}_p\). But then \(-3c^2 = \alpha^n\beta^n = 1\) in \(\mathbb{F}_q\) and hence in \(\mathbb{F}_p\), which contradicts \(p \equiv 2 \pmod{3}\) by quadratic reciprocity.