Existence, Uniqueness and Counterexamples · Hard problem

Claim: if $n$ is a positive integer and $8 \mid n^2 - 1$, then $n$ is prime. What is the smallest counterexample?