6
$\begingroup$

Suppose I have integers $a_1, \dots, a_n$ which are coprime, meaning that

$$a_1 b_1 + \dots + a_n b_n = 1$$

has a solution in integers $b_1, \dots, b_n$.

I would like to get a bound saying something like:

There exists a solution with $\sum_i |b_i| < \sum_i |a_i|$

(except in the degenerate case where $a_j = 1$, $a_i = 0$ for $i \neq j$)

Presumably such things (and probably much stronger bounds) are known. Does anyone know a reference for these kinds of results?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Not an answer, but this reminded me of Siegel's lemma. $\endgroup$
    – Wojowu
    Mar 19, 2019 at 15:20
  • 1
    $\begingroup$ You should be careful to distinguish coprime from mutually coprime (so that three numbers may be coprime without any two being coprime = two being mutually coprime). By doing something similar to row reduction, you should be able to come up with such a bound. Gerhard "Considering A Proof By Induction" Paseman, 2019.03.19. $\endgroup$
    – Gerhard Paseman
    Mar 19, 2019 at 15:44
  • 1
    $\begingroup$ Using the argument in math.stackexchange.com/questions/2436387/…, you can find a solution where $\sum_i|a_ib_i|$ is bounded by roughly $\frac12\bigl(\max_i|a_i|\bigr)^2$. $\endgroup$
    – Emil Jeřábek
    Mar 19, 2019 at 17:28
  • $\begingroup$ Yes, you can guarantee a solution with $\sum|b_i|<\sum|a_i|$: mathoverflow.net/a/108723/9924 $\endgroup$
    – Seva
    Mar 20, 2019 at 20:52
  • 4
    $\begingroup$ Possible duplicate of Estimates for Bezout coefficients $\endgroup$
    – Max Alekseyev
    Jul 3, 2019 at 18:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.