1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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,...? $\endgroup$ – Dirk May 10 '17 at 11:25
  • $\begingroup$ @Bemte. um.. I just want to minimize a T. Is it dependency to $y-x$? $\endgroup$ – PiggyJin May 10 '17 at 11:26
  • $\begingroup$ How to minimize $x+y$? $\endgroup$ – PiggyJin May 10 '17 at 12:10
0
$\begingroup$

https://mathoverflow.net/questions/108601/estimates-for-bezout-coefficients

See the above link

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

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks you, but it would be a rough bound. $\endgroup$ – PiggyJin May 10 '17 at 11:39
  • $\begingroup$ Yep, i don't think explicit bounds is easy to find, i think you might find the order of the bounds $\endgroup$ – Arpan1729 May 10 '17 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.