# Proof: By Induction

By hypothesis, $m > 0$ is a given positive integer $a_1,\ldots,a_r,b$ are given integers.

### "$\Leftarrow$"

• Now, assume that $d\mid b.$
• Case $r=1$: All except one coefficient $a_i$ equal zero, without loss of generality $a_1\neq 0$ i.e. $a_1x_1+0x_2+\ldots+0x_r=b.$ * Then, obviously, $d=\gcd(a_1,0,\ldots,0)=a_i\mid b$ and we have that the equation is solvable.
• Case $r=2$: All except two coefficients $a_i$ equal zero, without loss of generality $a_1\neq 0,a_2\neq 0$ i.e. $a_1x_1+a_2x_2+0x_3+\ldots+0x_r=b.$ * Note that from the existence and number of solutions of an LDE with one variable, it follows that the linear Diophantine equation of congrences $(a_1x_1)(a_2)\equiv b(a_2)$ is solvable for the module $a_2$ if and only if $\gcd(a_1,a_2)\mid b.$ * With this solution, we can also solve1 the above equation $a_1x_1+a_2x_2=b.$
• Case $r > 2$: * Assume, the claim is correct for the cases $2,\ldots,r-1$ (base case). By induction: * Set $a:=\gcd(a_1,\ldots,a_{r-1}),$ then we have $\gcd(a,a_r)=d$ by definition of the greatest common divisor of more than two numbers. * According to the case $r=2,$ the equation $ax+a_rx_r=b$ is solvable, for some suitable integers $x, x_r.$ * Since $a\mid ax$ we have also that the equation $a_1x_1+\ldots+a_{r-1}x_{r-1}=ax$ is solvable, for some suitable integers $x_1,\ldots,x_{r-1},$ by the base case. * Therefore, the equation $a_1x_1+\ldots+a_rx_r=b$ is solvable for some suitable integers $x_1,\ldots,x_{r}.$

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

#### Footnotes

1. Take for $x_1$ any integer representing the congruence class $x(a_2)$ solving the congruence $(a_1x_1)(a_2)\equiv b(a_2)$ and solve the equation for $a_1x_1+a_2x_2=b$ for $x_2.$