How do we solve
$$g=\gcd(a_0+A v,b_0+B u,n) \tag 1$$
where $a_0, b_0, A, B, n$ are given and $v, u, g \notin \{1, n\}$ are unknown? We may assume $\gcd(A, B) = 1$.
We can factor $n$ and then solve for $u, v$ using the divisors of $n$. Are there any other ways?
Context: This came about as a subproblem related to this question on Reversing Karatsuba Multiplication for Integer Factoring.
Note: Does $A = \alpha^k, B = \beta^m$ help with Eqn. (1)? The linked question gives $A, B$ in this structure, so if this somehow helps obtain $g$, that is sufficient.
My method:
$$\begin{align} \exists r,s,t \in \mathbb{Z} & \text{ such that} \\ gr & = a_0 + \alpha^k v, \\ gs & = b_0 + \beta^m u, \\ gt & = n \end{align}$$
Let $\gcd(n, \alpha - 1) \ne 1$. If not, we have a trivial divisor of $n$.
$$ \therefore (a_0 + \alpha^k v)s = (b_0 + \beta^m u)t \\ \implies a_0 s - b_0 t = \beta^m ut - \alpha^k vs \tag 2 $$
Suppose these two quantities on either side of Eqn. (2) equal $\delta \in \mathbb{Z}$
$$ a_0 s - b_0 t = \beta^m ut - \alpha^k vs = \delta \tag 3 $$
Such a solution is possible iff $\gcd(a_0, b_0)|\delta$ and $\gcd(\beta, \alpha)|\delta$. $\gcd(\beta, \alpha) = 1$ since we can assume $\gcd(A,B) = 1$ as given in the problem. Also, $\gcd(a_0, b_0) = 1$ because if it is not $1$ then we can take $(v,u)=(0,0)$ to solve $g = \gcd(a_0, b_0)$. So, we will assume the $\gcd(a_0, b_0)=1$.
Therefore, we may divide Eqn. (3) by $\delta$ to get:
$$\begin{align} a_0 \bigg({s \over \delta}\bigg) - b_0 \bigg({t \over \delta}\bigg) = \beta^m \bigg({ut \over \delta}\bigg) - \alpha^k \bigg({vs \over \delta}\bigg) = 1 \tag 4 \end{align}$$
and with a variable substitution $S = {s \over \delta}, T = {t \over \delta}, U = uT, V = vS$
$$ a_0 S - b_0 T = \beta^m U - \alpha^k V = 1 \tag 5 $$
We then solve
$$ a_0 S - b_0 T = 1 \tag {6.a} $$
and then substitute in
$$ (\beta^m T)u - (\alpha^k S)v = 1 \tag {6.b} $$
We can then put the solutions $(u,v)$ in Eqn. (1) and compute the non-trivial GCD, $g$.
Is this right?