Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.

If we already know the numbers $a,q$ are coprime then do we know any better way to compute $a^{-1}\bmod q$ without Euclidean algorithm?

Essentially can we solve the integer program:

\begin{gather*} \exists u,v\in\mathbb Z \\ -q/2<u<q/2 \\ -a/2<v<a/2 \\ au+qv=1 \end{gather*}

without LLL algorithm?

Why cannot we think differently than the Euclidean algorithm? Is there any barrier?

Implicit in the question is why cannot we NC reduce Extended GCD algorithm to GCD computation itself as we can replace last constraint by $$au+qv=g$$ where $g$ now is $\operatorname{GCD}(a,q)$ (now assumed may not be coprime)?