◀ ▲ ▶Branches / Number-theory / Proof: By Induction

Proof: By Induction

(related to Proposition: Existence of Solutions of an LDE With More Variables)

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

"$\Rightarrow$"

• Assume, the LDE (linear Diophantine equation) with $r$ variables $a_1x_1+\ldots+a_rx_r=b$ is solvable.
  • Let $d:=\gcd(a_1,\ldots,a_r)$ be the greatest common divisor of the $r$ numbers of $a_1,\ldots,a_r.$
  • From the divisibility law no. 9, it follows by induction that $d\mid (a_1x_1+\ldots+a_rx_r)$.
  • Since $a_1x_1+\ldots+a_rx_r=b,$ it follows that $d$ is also a divisor of $b.$

"$\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 solve¹ 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