Since $(a_n)$ satisfies the linear recurrence $a_{n+1} = 2(a_n - a_{n-1})$, an explicit formula for $a_n$ can be determined in the usual manner. Formally replacing $a_k$ in the recurrence by $x^k$, we obtain $x^{n+1} = 2(x^n - x^{n-1})$ and solving for nonzero $x$, we get $x^2 = 2(x-1)$ and $x = 1 \pm i$, where $i = \sqrt{-1}$.
Let $\alpha = 1+i$, $\beta = 1-i$. Then $a_n = A\alpha^n + B\beta^n$, where $A$ and $B$ are constants to be determined from the initial conditions $a_0 = 1$, $a_1 = 1$. Thus
$$A+B=1, \quad A\alpha+B\beta=1,$$
and so $A = B = 1/2$. Therefore $a_n = \frac{1}{2}((1+i)^n + (1-i)^n)$, for all positive integers $n$.

Note that $(1+i)^2 = 2i$, $(1+i)^4 = -4$ and $(1+i)^8 = 16$, and similarly $(1-i)^8 = 16$. Now, $2016 = 2^5 \times 3^2 \times 7$, so
$$(1 \pm i)^{2016} = (1 \pm i)^{8 \times 4 \times 63} = 2^{4 \times 4 \times 63} = 2^{1008}.$$
Hence
$$a_{2016} = \frac{1}{2}(2^{1008} + 2^{1008}) = 2^{1008}.$$
Next, we show that $2017$ is a prime number. Since $45^2 = 2025 > 2017$ and so $\sqrt{2045} < 45$, if $2017$ is not prime, it must have a prime divisor less than $45$, i.e. one of the following: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43$. As already noted, $2016$ is divisible by $2, 3$ and $7$, so these primes can be eliminated from the list. Also, it is simple to check that $2015 = 5 \times 13 \times 31$, so $5, 13$ and $31$ can also be eliminated.
The remaining possibilities are: $11, 17, 19, 23, 29, 37, 41, 43$, and one checks by long division that none of these divide $2017$. Hence $2017$ is prime. Since $p=2017$ is congruent to $1$ (mod $4$), there is an integer $y$ such that $p$ divides $1+y^2$. For example, using Wilson's Theorem combined with $((p-1)! \equiv ((\frac{p-1}{2})!)^2 \pmod{p})$, we see that we can take $y = (\frac{p-1}{2})!$. Consider $(1+y)^2 = 1+2y+y^2 \equiv 2y \pmod{p}$. By Fermat's little theorem,
$$(1+y)^{2016} \equiv (1+y)^{p-1} \equiv 1 \pmod{p}, \quad \text{so} \\ (2y)^{1008} \equiv 1 \pmod{p}.$$
Since $y^4 \equiv 1 \pmod{p}$ and $4$ divides $1008$, it follows that $2^{1008} \equiv 1 \pmod{p}$. This shows that the remainder of $a_{2016}$ on division by $2017$ is $1$.