Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in functional $NC$ does it follow the other is in functional $NC$?
Is there a variant of $1$ or $2$ which is $P$-complete? Ideally I would like the involved Diophantine equations to be of constant number of variables and constant degree.
