Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

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