Clearly, using CRT, it suffices to prove the problem statement is true for prime powers. So suppose $n=p^e$ for some prime $p$, and positive integer $e$. If $p$ is odd, then take $$(a,b)=\left(\frac{p^e-1}{2},p^e \right)$$Else if $p=2$, then put $$(a,b)=\left(2^e,\frac{4^e-1}{3} \right)$$

$ 4a^{2}+9b^{2}-1 = (2a+3b)^{2} - 12ab -1 $ Suppose $ n = 2^{r}m $ such that $ gcd(m,2)=1 $ Put $ a= 2^{r}a^{'} $ and $ b=mb^{'} $ now we want $ 2^{r}m $ $\mid$ $ (2^{r+1}a^{'} + 3mb^{'})^{2} -12(2^{r}a^{'})(mb^{'}) -1 $ So $ 2^{r}m \mid (2^{r+1}a^{'} + 3mb^{'})^{2} -1 $ Now $ gcd(2^{r+1}, 3m)=1 $ so according to bézout theorem there exist $ a^{'} $ and $ b^{'} $ (mod n) such that $ (2^{r+1}a^{'}+3mb^{'})=1 $ So we are done.

Assume that we have $2a=X,3b=Y$ By chinese remiander Theorem it is easy to see that we only need to prove the result for $n=p^\alpha$ where $p$ is a prime number and alpha is nonnegative integer. For the case $p=2$ consider $2^\alpha\mid X,Y-1\implies 2^\alpha\mid X^2+(Y-1)(Y+1)$ Now assume that $p$ is odd and we have $v_p(X^2+Y^2-1)=\alpha$ (Essentially write $X^2+Y^2-1=rp^\alpha$ with $r$ not divisible by $p$) we shall prove that there exist $X',Y'$ such that $v_p(X'^2+Y'^2-1)>\alpha$. Let $X'=X+sp^\alpha$ hence we have $$X'^2+Y^2-1\equiv X^2+Y^2-1+2Xsp^\alpha=rp^\alpha+2Xsp^\alpha=p^\alpha(r+2Xs) \pmod{p^{\alpha+1}}$$Since $X$ is not divisible by $p$, we know that there exists such a unique $s\pmod{p}$ and the result follows with $Y'=Y$. Thus we only need to prove the result for $n=p$ For this part we only need to note that the sets $A=\{X^2\mid0\leq X\leq \frac{p-1}{2}\}$ and $B=\{1-Y^2\mid0\leq Y\leq \frac{p-1}{2}\}$ both have $\frac{p+1}{2}$ distinct remainders $\pmod{p}$ thus $A\cap B\neq\emptyset$ Thus there exist $X,Y$ such that $p\mid X^2+Y^2-1$ We are done!