# Euclidean Algorithm

Let $A,B$ be a $\gamma$-bit integer and relatively prime. $\gcd(A,B)=1$. Also, $A-B \ge 2^{\gamma -2}$

Then, by the Euclidean Algorithm, there exist integers $x$ and $y$ such that

$Ax-By = 1$. After then, what is the size of $T=|y A -x B|$? Can we find upper bound of T?

• These $x$ and $y$ are not unique. Depending on which ones you choose, the answer might vary. Do you want $x+y$ to be minimal, $y-x$ minimal,...? – Dirk May 10 '17 at 11:25
• @Bemte. um.. I just want to minimize a T. Is it dependency to $y-x$? – PiggyJin May 10 '17 at 11:26
• How to minimize $x+y$? – PiggyJin May 10 '17 at 12:10

By this we know $|x|\leq B$ and $|y|\leq A$
Now we know for two reals c,d we have $|c-d|\geq {\bigg |}|c|-|d|{\bigg |}$.
so you can find a lower bound of $|yA−xB|$ using the above inequality and as of the upper bound it is clearly less than or equal to $A^2+B^2$ (As we know the bounds of $x$ and $y$)