$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?



Fundamental solutions to linear Diophantine equations and their existence and computation
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.


