• $a_{4k}$ has a formula in terms of $k$ when $k$ is integer. (So does $a_{4k+1}, a_{4k+2}, a_{4k+3}$)
• $a_{4k}=a_{4k+1}$
• The formula is $a_{4k}=a_{4k+1}=(-1)^k\cdot2^{2k}$
• $2^{1008}=2^{\frac{2017-1}{2}}$ which is 1 or -1 modulo 2017.
• Use quadratic reciprocity law for 2.

The solution requires a understanding about quadratic reciprocity. There is a short scheme about it after the solution.

Claim: $a_{4k}=a_{4k+1}=(-1)^k\cdot2^{2k}$ 

Proof: We prove this inductively.

Base case is given.

Inductive step: 

Given that $a_{4k}=a_{4k+1}=(-1)^k\cdot2^{2k}$ prove that $a_{4k+4}=a_{4k+5}=(-1)^{k+1}\cdot2^{2k+2}$.

Proof: 

• $a_{4k+2}=2(a_{4k+1}-a_{4k})=0$
• $a_{4k+3}=2(a_{4k+2}-a_{4k+1})=-2a_{4k}$
• $a_{4k+4}=2(a_{4k+3}-a_{4k+2})=2a_{4k+3}=-4a_{4k}$
• $a_{4k+5}=2(a_{4k+4}- a_{4k+3})=2(-4a_{4k}+2a_{4k})=-4a_{4k}$
• $a_{4k+4}=a_{4k+5}=-4a_{4k}=-1\cdot(-1)^k\cdot4\cdot2^{2k}=(-1)^{k+1}\cdot2^{2k+2}$

Now, $a_{2016}=a_{4\cdot 504}=(-1)^{504}\cdot2^{2\cdot504}=2^{1008}$

We want $2^{\frac{2017-1}{2}}\pmod{2017}$.

2017 is a prime number.

Using the special case of quadratic residue modulo $p$ for 2, we see that $2$ is a quadratic residue if and only if $p\equiv \pm 1\pmod 8$.

$2017 \equiv 1 \pmod{8} \implies$ 2 is a quadratic residue modulo $2017$.

Let $a^2 \equiv 2 \pmod{2017}$

$2^{\frac{2017-1}{2}} \equiv a^{2017-1} \equiv 1 \pmod {2017}$

So, the answer is 1.

Quadratic Reciprocity:

No proof is shown here, you can check the proofs in the book $Modern~olympiad~number~theory$.

Modulo $p$, an integer $a$ is called a quadratic residue if and only if there is an integer $x$ such that

\[x^2 \equiv a\pmod p\]

In the legendre symbol,

\[\left( \frac{a}{p} \right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0 \pmod{p}, \\ -1 & \text{if } a \text{ is a quadratic non-residue modulo } p, \\ 0 & \text{if } a \equiv 0 \pmod{p}. \end{cases}\]

The quadratic reciprocity law states:

\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}\]

for odd primes $p, q$.

But, for the case of 2, it is:

\[\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\]

for an odd prime $p$.