Just a tiny, tiny remark; no need for the contrapositive. Getting from $a^2+k\mid a^3-a$, $a^2+k\mid a(a^2+k)$ the relation $a^2+k\mid a(a^2+k) - (a^3-a) = ak+a$, leads to $a^2+k \leq ak+a$, so $(a-1)(k-a) \geq 0$, thus $k\geq a$, unless $a=1$, but then $k$ being a positive integer, we again have $k\geq a$.

$\gcd(a,k)=p$ $k=px;a=py$ Let's $y>x$ $py^2+x | y(py-1)(py+1)$ $p^2y^2=kpy^2+kx+1$ $p>k $ $ py^2(p-k)=kx+1$ $kx+1>py^2>kx^2$ Them $x=1$ $k+1>py^2>ky^2$ contradicition. So $x \geq y$ otherwise $k \geq a$