2
$\begingroup$

Recently I've started to take interest in linear diophantine equations (they play a key role in a math puzzle I stumbled upon).

I don't have a strong math background, and at first I had no clue how to solve an equation like $ax+by=c$ over the integers. After playing with it for a while I realized some things about the solutions (namely, if $(g,h)$ is a solution, then so will be $(g+b,h-a)$). However, I wasn't able to find a solution to the general case. Eventually I gave up trying on my own and started researching (including here on math.se) for how to solve diophantine equations (I became acquainted with the terminology in this step).

I've learned two things:

  • For an equation like this to have integer solutions, $c$ must be divisible by $gcd(a,b)$.
  • Provided the solutions exist, there exists an algorithm to find them, and it has a connection with Euclid's algorithm for finding the greatest common divisor of two numbers.

As it is now, I'm able to tell if an equation like this has integer solutions and I'm even able to execute the steps needed to find all of its solutions. For all it matters, I can solve linear diophantine equations in two variables.

However, I really would like to know why those two things are true, and moreover, what is the connection between Euclid's algorithm and the algorithm for finding the roots (I can see the similarity in the coefficients involved, but I feel like there's a more meaningful reason for the connection, a reason which I didn't yet fully grasped).

So I guess the question is:

How can I intuitively understand the algorithm for finding the integer solutions to $ax+by=c$?


I hope I made myself clear. If more clarification is needed, please ask. Thank's in advance.

$\endgroup$
  • $\begingroup$ Are you familiar with Bézout's identity? It's basically what the algorithm/solutions are all about in this case. $\endgroup$ – Fizz Mar 6 '15 at 3:23
  • $\begingroup$ Never heard of it. The link seems a bit technical, but I'll investigate ;) $\endgroup$ – JLagana Mar 6 '15 at 3:33
  • $\begingroup$ This answer describes one nice way to view the Extended Euclidean algorithm. The underlying theory is described here. $\endgroup$ – Bill Dubuque Mar 6 '15 at 4:39
  • $\begingroup$ @JLagana There is much linearity (ideals) at the heart of the matter. Do you know any linear algebra, e.g. do you know how to solve systems of linear equations by using Gaussian elimination (row reduction) to achieve triangularization? Are you familiar with modular arithmetic (congruences)? Do you know anything about rings or ideals? The more you say about your knowledge level, the more hope that you'll get a comprehensible answer. $\endgroup$ – Bill Dubuque Mar 7 '15 at 15:18
  • $\begingroup$ @BillDubuque I know linear algebra only. $\endgroup$ – JLagana Mar 7 '15 at 19:25
1
$\begingroup$

A request for "intuitive understanding" is always tricky, but see if this helps.

For simplicity of explanation we shall assume that $a,b$ are positive integers with no common factor - it's not too hard to amend things so as to cover other cases. Looking at the equation $$ax+by=c\ ,$$ we might have the idea that this would be very easy to solve if $a$ were small. For example, in the extreme case, if $a=1$ then we have $x+by=c$ and the solution is clearly $$y=\langle\hbox{anything}\rangle\ ,\quad x=c-by\ .$$ If $a=2$ it's not too much harder: $b$ must be odd, so we choose $y$ to be the same parity (odd or even) as $c$ and then take $$x=\frac{c-by}{2}\ .$$

So we could then think: is there any way to rearrange the original equation in such a way that $a$ is reduced? Well, if we split $a$ into a multiple of $b$ plus a remainder, then the multiple of $b$ in the term $ax$ could be included with the $by$ term. That's probably pretty confusing in words, hopefully it's easier in symbols: if $$a=bq+r$$ then the equation becomes $(bq+r)x+by=c$, that is, $$b(qx+y)+rx=c\ .$$ If we can solve this to find values for our "new variables" $qx+y$ and $x$, then we easily get the values of $x$ and $y$. If $b$ and $r$ are still too big to solve easily, we can repeat the procedure, writing $b$ as a multiple of $r$ plus another remainder, $$b=q'r+r'\ .$$ I expect you can see that we have just computed the second step of a Euclidean algorith which started with $a$ and $b$, and perhaps this is sufficient to explain the connection.

Hope this helps!

$\endgroup$
  • $\begingroup$ I'm very thankful for your time David. However, this is not what I'm looking for. You answered precisely what I asked: "how can I intuitively understand the algorithm (...)", but your answer made me realize that intuitively understanding this algorithm doesn't explain me why it must work (I think I should change the question title). I'm not sure if I'm being clear here, so I'll try to clarify. To me, your answer demonstrates a reasoning that explains how a human could discover this algorithm naturally (without any "rabbit-out-of-the-hat" steps). This is a very important information for me, $\endgroup$ – JLagana Mar 6 '15 at 22:35
  • $\begingroup$ but it doesn't really answer my question of why this works. Of course, you could say that it works because it gives you the correct solutions, but to me it feels like something is missing. $\endgroup$ – JLagana Mar 6 '15 at 22:43
  • $\begingroup$ Maybe it's clearer this way: I understand that executing this algorithm gives me a generating rule for the x's and y's (e.g. x=1+k , y = 2k), and (thank's to your answer) I also have a good explanation to why I'm doing each step of it. However, once I take a look at the solutions, I'm still completely ignorant of why these are the solutions, not any other numbers. $\endgroup$ – JLagana Mar 6 '15 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.