3

When I was trying to prove a relation from solid state physics, I reached this mathematical problem. In the equation

$$\sum_{i=1}^Nm_ix_i=n$$

$m_i$ and $n$ are known integers, $N=3$, and $x_i$ are unknown integers. Also we know that the greatest common factor of $\left\{m_i\right\}$ is 1. I don't need to find the solution; I must just show/state that the answer exists.

apadana
  • 191

2 Answers2

6

If the greatest common divisor of $m_1, \dots, m_N$ divides $n$, then this has a solution, by Bézout's identity. If not, there is no solution, since the gcd will divide the left for any choice of $x_i$, but will never divide the right.

B. Mehta
  • 12,774
  • In this example, the greatest factor is 2 and it doesn't divide 13, but you still get a plane where the equation holds: https://www.wolframalpha.com/input/?i=10x%2B14y%2B22z%3D13 I may be misunderstanding your answer – Srini Oct 09 '17 at 18:03
  • In your example, there are no integer solutions, which OP was looking for. Of course if you relax to non-integer solutions there are many more :) https://www.wolframalpha.com/input/?i=integer+solutions+10x%2B14y%2B22z%3D13 – B. Mehta Oct 09 '17 at 18:04
  • Ah right, didn't notice that :) – Srini Oct 09 '17 at 18:09
  • Just to be sure I understand the English language well enough: 1 divides any integer. Am I right? – apadana Oct 09 '17 at 18:53
  • Yes! If the greatest common divisor of the integers is 1, then your equation has a solution for any $n$. – B. Mehta Oct 09 '17 at 18:54
0

It's a standard result from Arithmetic:

The ideal $\;(x_1,\dots , x_N)\subset\mathbf Z$ generated by $x_1, \dots, x_n$, i.e. the set of linear combinations of $x_1,\dots, x_N$ with integer coefficients is the principal ideal generated by $\gcd(x_1,\dots,x_N)$.

Hence, if the generators are coprime, this ideal is $\mathbf Z$, generated by $1$, and any multiple of the g.c.d., i.e. any integer is attained.

Bernard
  • 175,478