Lemma Using Proth's Theorem ${(a, a+1)}^{(p-1)/2}$ $=$ $-1$ $\pmod p$ and $p$ is composite?

Question

Proth's Theorem:

Let $p=k*2^n + 1$ where $k$ $<$ $2^n$. If there is any integer $a$ such that

$a^{(p-1)/2}$ $=$ $-1$ $\pmod p$, then $p$ is prime.

Can anyone please find a counterexample (composite $p$) with removing the restriction that $k$ $<$ $2^n$, but instead satisfying both:

$a^{(p-1)/2}$ $=$ $-1$ $\pmod p$

${(a+1)}^{(p-1)/2}$ $=$ $-1$ $\pmod p$

for some integer $a$, or else prove that none should exist? I wasn't able to spot any myself for $p$ $<$ $500$. Thanks.

Answer 1

One counterexample is $p=703=19\times37$ and $a=40$. (There are eight values of $a$ that are counterexamples for this $p$.) The next counterexample is $p=1387=19\times73$ and $a=71$ (or three other values of $a$). I found these just by brute force.