From the assumptions above, I am trying to prove that $q=1+kp$ for some integer $k$ and that $k$ is even.
My thoughts thus far: Since $a^p\equiv 1$ mod $q$, I know that by a corollary of Fermat's little theorem that $a^p\equiv a$ mod $q$. So $q|a$ or $q|a^{p-1}-1$, but $q\nmid a$, so $q|a^{p-1}-1$.
And this is where I'm not sure where to go. If I can prove that $q\equiv 1$ mod $p$, then the conclusion would follow, and hopefully $k$ being even would follow as well. But I'm not sure.
Thoughts are greatly appreciated!