◀ ▲ ▶Branches / Numbertheory / Proposition: Existence of Solutions of an LDE With More Variables
Proposition: Existence of Solutions of an LDE With More Variables
For a given positive integer $m > 0$ and given integers $a_1,\ldots,a_r,b$, the LDE (linear Diophantine equation) with $r$ variables $$a_1x_1+\ldots+a_rx_r=b$$ is solvable, if and only if $\gcd(a_1,\ldots,a_r)\mid b,$ i.e. if and only if the greatest common divisor of the $r$ numbers of $a_1,\ldots,a_r$ is also a divisor of $b.$
Notes
 The existence of a solution for two positive integers was first proven in 1624 by Claude Bachet (1581  1638).
 See also extended greatest common divisor algorithm for the calculation of $a_1x_1+a_2x_2=\gcd(a_1,a_2).$ By multiplying the solutions $x_1,x_2$ with $\frac{b}{\gcd(a_1,a_1)}$ and by induction, this algorithm can be used to solve the general case.
Table of Contents
Proofs: 1
Mentioned in:
Proofs: 1 2
Propositions: 3
Thank you to the contributors under CC BYSA 4.0!
 Github:

References
Bibliography
 Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
 Hermann, D.: "Algorithmen Arbeitsbuch", AddisonWesley Publishing Company, 1992
 Jones G., Jones M.: "Elementary Number Theory (Undergraduate Series)", Springer, 1998