I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$.
We know that $(w|N)=-1$ and $(a^2|N)=1$ from basic facts of the Legendre symbol.
I feel like the answer should be yes (heuristically), as $(b|N)=\pm 1$, and one can choose any $a$, or for that matter, any primitive root $w$, for which there are $\phi(N-1)$ of them, but I don't currently know how to approach the question.
Thanks :)
I assume you mean $N=p$ where $p$ is an odd prime, since for $p=2$ no integer $b$ satisfies $\left(\frac b2\right)=-1$.
Now notice that the set $S=\left\{w^{2k}\mid k=1,\cdots\right\}$ of quadratic residues of $p$ has cardinality $\frac{p-1}2$ and does not contain $0$. Hence the set $S+1:=\left\{w^{2k}+1\mid k=1,\cdots\right\}$ of cardinality $\frac{p-1}2$ must contain a quadratic non-residue (since it does not contain $1$ while $1\in S$), say $1+w^{2k}=w^{2l-1}$. Then, multiplying this equation by $w$, we see $w=w^{2l}-w^{2k+1}$, as required.
Therefore under the assumption that $N$ is an odd prime the statement holds true.
Hope this helps.