If $q$ is coprime to $a$ then $a\mid nq-1,\,$ so $q$ is invertible mod $a$

[Note: this applies to the initial version of the question where prime $\,q\nmid a\ $]

If $q\not\mid a$, then $a^{q-1}\equiv1$ mod $q$, by Fermat's little theorem. Writing this as $a^{q-1}=1-nq$ with $n\in\mathbb{Z}$, then $q\ge2$ implies $a\mid a^{q-1}$, which means $a\mid(nq-1)$.

Below are a few ways to prove the gcd $\rm \,(c,m) = 1\iff c\,$ is invertible $\!\!\rm \pmod{\! m}$

By Euler's Theorem $\rm \,(c,m)=1\,\Rightarrow\,c^{\varphi(m)}\equiv 1\pmod m.\,$ Or use Bezout as below (for $\rm b\!=\!1)$

$$\rm \exists\, x\in\Bbb Z\!:\ cx\equiv b\!\!\!\pmod{\! m}\!\iff\! \exists\, x,y\in\Bbb Z\!:\ cx\!+\!my = b\!\overset{\rm\ Bezout}\iff\!\gcd(c,m)\mid b\qquad$$

Or use the following

Theorem $\ $ The following are equivalent for integers $\rm\:c,\, m.$

$(1)\rm\ \ \ gcd(c,m) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ m)$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(c,m)\! =\! 1\Rightarrow cd\!+\!km =\! 1\,$ for $\rm\,d,k\in\Bbb Z\,$ $\rm\Rightarrow cd\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm cx\!+\!d \equiv cy\!+\!d\,\Rightarrow\,c(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ by multiplying by $\rm\,c^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to cx\,$ is onto, so $\rm\,cd\equiv 1,\,$ some $\rm\,d,\,$ i.e. $\rm\, cd+km = 1,\,$ some $\rm\,k,\,$ so $\rm\gcd(c,m)=1$

See here for a conceptual proof of said Bezout identity for the gcd.

Because $\gcd(q,a)=1$ Euler's theorem applies $$q^{\varphi(a)} \equiv 1 \pmod{a}$$ and $n=q^{\varphi(a)-1}$.