Odd Prime Factor of \( a_{2015} \)?

[Ackbach]

Here is this week's POTW:

-----

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}$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to castor28 for his correct solution to this week's POTW, which was Problem A-2 in the 2015 Putnam archive. His solution follows:

[sp]
The characteristic polynomial of the sequence is $f(x)=x^2 -4x + 1$. We will study that sequence modulo various odd primes, to determine the position of 0's in the sequence.

Since the discriminant of $f(x)$ is 12, $p=3$ is a special case. Modulo 3, the sequence starts with $(1,2,1,2,\ldots)$. As the sequence is determined by two consecutive values, this shows that the period is 2, and that the sequence does not contain any 0.

From now on, we look at the sequence in $\mathrm{GF}(p)$, for a prime $p>3$. The general term of the sequence is given by $a_n=A\,\alpha^n + B\,\beta^n$, where $\alpha$ and $\beta$ are the roots of $f(x)$, and $A$ and $B$ depend on the initial values. If $(3/p)=1$ (the Legendre symbol), these roots lie in $\mathrm{GF}(p)$ (this is the case if $p\equiv\pm1\pmod{12}$); otherwise, the roots are in $\mathrm{GF}(p^2)$.

As $\alpha$ and $\beta$ are inverses of each other, they have the same multiplicative order modulo $p$; this is the period $T$ of the sequence. Depending on $(3/p)$, this period divides $p-1$ or $p^2-1$.

Since $\alpha^{T/2}=\beta^{T/2}=-1$, we have $a_{i+T/2}=-a_i$. This shows that, if the sequence contains any 0's, these are spaced $T/2$ apart (this is somewhat similar to what happens with trigonometric functions).

The strategy is as follows. We look for prime factors of the first few terms of the sequence. For such a prime $p$, let $i_0$ be the first index with $a_{i_0}=0$. To have $a_{2015}=0$, the half-period $T/2$ must divide $2015-i_0$. We compute $S=\gcd((p-1)/2,2015-i_0)$ or $\gcd((p^2-1)/2,2015-i_0)$ (depending on $(3/p)$), to get an upper bound on $T/2$. If $S$ is not too large, we compute a few terms of the sequence to find if $T/2$ is equal to a divisor of $S$.

The first terms of the sequence (in $\mathbb{Z}$) are $(1, 2, 7, 26, 97, 362)$, giving the prime factors $\{7,13,97,181\}$.

For $p=7$, we have $(3/p)=-1$, $i_0 = 2$, $\gcd(24,2013)=3$. As $a_3\equiv5\not\equiv\pm a_0\pmod7$, this prime is excluded.

For $p=13$, we have $(3/p)=1$, $i_0=3$, $\gcd(6,2012)=2$. As $a_2\equiv2\not\equiv\pm a_0\pmod{13}$ , 13 is also excluded.

For $p=97$, we have $(3/p)=1$, $i_0=4$, $\gcd(48,2011)=1$, and we exclude 97, since the sequence is not constant.

For $p=181$, we have $(3/p)=1$, $i_0=5$, $\gcd(90,2010)=30$. We start computing the sequence modulo 181 until we find a term equal to $-a_0=180$. The first 12 terms are:

$$(1, 2, 7, 26, 97, 0, 84, 155, 174, 179, 180, 179, \ldots)$$
​

As we have $(a_{10},a_{11})=-(a_0,a_1)$, the half period is 10, which divides $2015-i_0=2010$. This shows that 181 divides $a_{2015}$.
[/sp]

An alternative solution, attributed to Kiran Kedlaya and associates, follows:

[sp]
One possible answer is $181$.
By induction, we have $a_n = ((2+\sqrt{3})^n+(2-\sqrt{3})^n)/2 = (\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$.
[/sp]