If $q$ is coprime to $a$ then $a\mid nq-1,\,$ so $q$ is invertible mod $a$ I think the following is true:
If $q$ is coprime to $a$ then $a\mid (nq-1)$ for some $n\in\mathbb Z$.
I have started to first reducing $n\in\mathbb Z$ to $n\in\{1,\ldots,a-1\}$ and then considering all the cases $q = ka + j$ for $j=1,2,3,\ldots,a-1$. I stopped at $j=3$ and found that this is kinda messy. Does anyone have an elegant proof for this (maybe using some results from number theory)?
[Note: question has been generalized from prime $q\nmid a$ to $\,q$ coprime to $a$]
 A: 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.
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)$.
A: Because $\gcd(q,a)=1$ Euler's theorem applies
$$q^{\varphi(a)} \equiv 1 \pmod{a}$$
and $n=q^{\varphi(a)-1}$.
