Fundamental solutions to linear Diophantine equations and their existence and computation

Question

$T>0$ is a parameter.

Consider the linear Diophantine equation $ax+by=c$ where $a,b$ are coprime.

Suppose $a,b$ are of magnitude $T^{1+\epsilon}$ and $c$ is of magnitude $T^2$.

1. For how many such equations we can expect $x,y$ to be of magnitude $T^{1+\epsilon}$ for a fixed $c$ and we vary $a,b$ coprime of magnitude $T^{1+\epsilon}$? Call such solutions Fundamental.

Such solutions are also mininum normed.

2. The usual way of solving such equations is to solve $ax'+by'=1$ and choose $x=x'c$ and $y=y'c$. But this does not provide a polynomial time algorithm to find $x,y$ of magnitude $T^{1+\epsilon}$ if there exists one. How do we find such solutions when they exist without using integer programming and directly using number theory?

Answer 1

Solve $ax'+by'=1$, then take $$x = x'c - b \left\lfloor \frac{x'c}{ b} \right\rfloor$$ $$y = y'c +a\left\lfloor \frac{x'c}{ b} \right\rfloor$$

then we have $ax+by= ax'c +by'c = c$ and (if $b>0$ for simplicity) $0 \leq x < b$ so $$|x| < b$$ and $$|y| = \left| \frac{c-ax}{b} \right| \leq \frac{|c|}{|b|} + \frac{|a||x|}{|b|}< \frac{|c|}{|b|}+a\leq T^{1-\epsilon} + T^{1+\epsilon}.$$ So there is always a solution, and the algorithm to find it is clearly polynomial time.

We can optimize the norm by subtract one more copy of $b$ from $x$ if it helps.