Ireland_2017

The equation $x^2-2x-41=0$ has roots $\alpha =1+\sqrt{42}$ and $\beta =1-\sqrt{42}$. Using $a_0=0$ and $a_1=2$, we obtain $$a_n=\frac{{\alpha }^n-{\beta }^n}{\sqrt{42}}\text{for all }n\ge 0.(2)$$ Note that if $h$ and $k$ are positive integers, then $${\alpha }^{h(k-1)}+{\alpha }^{h(k-2)}{\beta }^h+{\alpha }^{h(k-3)}{\beta }^{2h}+\cdots +{\beta }^{(k-1)h}$$ is an integer. Since $\alpha \beta =-41$, this result follows once we show that ${\alpha }^m+{\beta }^m$ is an integer for every positive integer $m$. Now $\alpha +\beta =2$ and $${\alpha }^{h+1}+{\beta }^{h+1}=(\alpha +\beta )({\alpha }^h+{\beta }^h)-\alpha \beta ({\alpha }^{h-1}+{\beta }^{h-1}),$$ so the integrality of ${\alpha }^m+{\beta }^m$ follows using induction. Next $${\alpha }^8-{\beta }^8=(\alpha -\beta )(\alpha +\beta )({\alpha }^2+{\beta }^2)({\alpha }^4+{\beta }^4)=2\sqrt{42}\cdot 2\cdot 2\cdot 43\cdot 2\cdot 2017.$$ Now $2016=8\cdot 252$ and $$\begin{gathered} a_{2016}=\frac{{\alpha }^{8\cdot 252}-{\beta }^{8\cdot 252}}{\sqrt{42}} \\ =\frac{{\alpha }^8-{\beta }^8}{\sqrt{42}}\cdot \frac{{\alpha }^{8\cdot 252}-{\beta }^{8\cdot 252}}{{\alpha }^8-{\beta }^8} \end{gathered}$$ The second factor is an integer, on applying the result above with $k=252$, $h=8$, and the first factor is an integral multiple of $2017$. Hence $2017$ divides $a_{2016}$, as claimed.

---

Alternative solution.

We start in a similar manner to Solution 1 to obtain the formula (2). The binomial theorem then gives $$a_{2016}=\frac{1}{\sqrt{42}}\left((1+\sqrt{42}{)}^{2016}-(1-\sqrt{42}{)}^{2016}\right)=2\sum _{k=0}^{1007}\left(\genfrac{}{}{0ex}{}{2016}{2k+1}\right)42^k$$ The key observation is that for any prime number $p$ and $1\le m<p$ we have $(p-1)(p-2)\cdots (p-m)\equiv (-1{)}^{m}m!(\mathrm{mod}p)$ and because $\gcd (p,m)=1$ this implies that $$\left(\genfrac{}{}{0ex}{}{p-1}{m}\right)=\frac{(p-1)(p-2)\cdots (p-m)}{m!}\equiv (-1{)}^m(\mathrm{mod}p).$$ Because $2017$ is a prime number, we see now that $$\left(\genfrac{}{}{0ex}{}{2016}{2k+1}\right)\equiv -1(\mathrm{mod}2017)$$ for all $0\le k\le 1007$. Hence, $$a_{2016}\equiv -2\sum _{k=0}^{1007}42^k\equiv -\frac{2}{41}(42^{1008}-1)(\mathrm{mod}2017)$$ and so $a_{2016}$ is divisible by $2017$ iff $42^{1008}\equiv 1(\mathrm{mod}2017)$. This could be checked by a tedious calculation, but can also be seen with the aid of Legendre symbols and quadratic reciprocity as follows. By Euler's criterion, we have $42^{1008}\equiv (2017^{42})(\mathrm{mod}2017)$. Next, we compute the Legendre symbol $(2017^{42})$ via $$\begin{array}{rl}\left(\frac{42}{2017}\right)& =\left(\frac{2}{2017}\right)\left(\frac{3}{2017}\right)\left(\frac{7}{2017}\right)\\ & =\left(\frac{3}{2017}\right)\left(\frac{7}{2017}\right)\\ & =\left(\frac{2017}{3}\right)\left(\frac{2017}{7}\right)\\ & =\left(\frac{1}{3}\right)\left(\frac{1}{7}\right)=1,\end{array}$$ where in the second line we have used the fact that $\left(\frac{2}{2017}\right)=1$ since $2017\equiv 1(\mathrm{mod}8)$, and the third line follows from the fact that $2017\equiv 1(\mathrm{mod}4)$. This gives the desired result that $42^{1008}\equiv 1(\mathrm{mod}2017)$.

---

Alternative solution.

We start in a similar manner to Solution 1 to obtain the formula (2). Note that $p=2017$ is prime. Next we show that $42$ is a quadratic residue mod $2017$ (either by observing that $119^2\equiv 42(\mathrm{mod}2017)$, by using the argument in Solution 2, or otherwise). Finally, letting $r^2\equiv 42(\mathrm{mod}2017)$, we interpret the formula (2) over the field of integers mod $2017$ to obtain $$a_{p-1}\equiv \frac{(1+r{)}^{p-1}-(1-r{)}^{p-1}}{r}(\mathrm{mod}2017).$$ By Fermat's little theorem, $p$ divides $((1+r{)}^{p-1}-1)-((1-r{)}^{p-1}-1)$, and so $p$ divides $r_{p-1}$. Thus $p$ divides $a_{p-1}$, i.e., $2017$ divides $a_{2016}$.

---

Alternative solution.

Consider the recursion modulo $2017$ and go back eight steps $$\begin{array}{rl}{a}_{8k+8}& =2a_{8k+7}+41a_{8k+6}\\ & =45a_{8k+6}+82a_{8k+5}\\ & =172a_{8k+5}+1845a_{8k+4}\\ & \equiv 172a_{8k+4}+1001a_{8k+3}(\mathrm{mod}2017)\\ & \equiv 1345a_{8k+3}+1001a_{8k+2}(\mathrm{mod}2017)\\ & \equiv 1674a_{8k+2}+686a_{8k+1}(\mathrm{mod}2017)\\ & \equiv 56a_{8k}(\mathrm{mod}2017).\end{array}$$ Because $a_0=0$ it now follows by induction that $2017$ divides $a_{8k}$ for every non-negative integer $k$. As $2016$ is divisible by $8$, the result follows.