◀ ▲ ▶Branches / Number-theory / 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 BY-SA 4.0!

Github:

References

Bibliography

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