2
$\begingroup$

Given positive integers a,b,c, how to find all positive integers m,n such that $an+b=cm$?

Is there always infinitely many m,n for all a,b,c?

If $(n_0, m_0)$ is the smallest solution, are all other solutions of the form $(n_0+ct, m_0+at)$ for some positive integer t?

  • 1
    [Bezout's Identity](http://en.wikipedia.or$g$/wiki/Linear_Diophantine_equation)2012-02-08

1 Answers 1

3

How: For how to do it, look for the Extended Euclidean Algorithm. It is not particularly hard to carry out, but a proper description would be quite lengthy. The Extended Euclidean Algorithm is also described in most books on Elementary Number Theory. There are many computer implementations, but for $a$ and $c$ of modst size, the procedure can be easily carried out by hand.

If $d$ is the greatest common divisor of $a$ and $c$, the Extended euclidean algorithm produces integers $x$ and $y$ such that $ax+d=cy$. But from that one can solve your more general problem.

Existence of solution: Certainly there do not always exist such $m$ and $n$. For example, let $a=2$, $b=1$, $c=2$. Then $an+b$ (that is, $2n+1$) is always odd, and $cm$ (that is, 2m) is always even, so they can never be equal.

In general, if the greatest common divisor of a$ and $c$ divides $b$, there always is a solution. If the greatest common divisor of $a$ and $c$ does not divide $b, there is no solution.

Infinitely many solutions: If there is a solution (n_0,m_0)$, then there are infinitely many solutions. For suppose that $an_0+b=cm_0$. Then for any integer $t$, we have $a(n_0 +ct)+b=c(n_0+at).$ (Just expand. There will be a term $act$ on the left, and a term $cat on the right, and they cancel.)

So if (n_0,m_0)$ is a solution, then so is $(n_0+ct, m_0+at)$ for any positive integer $t$.

  • 0
    @Jakub: I did not tell the whole story. Sometimes, when the gcd of $a$ and $c$ is $\ne 1$, certain fractions may be allowed for $t$. The analysis can actually be restricted to the $\gcd(a,c)=1$ case, the rest follows without much trouble. Also, if we pick our $(n_0,m_0)$ too big, there may be some positive solutions $(n,m)$ that require a negative $t$. But roughly speaking, if we are careful, we can produce an expression for solutions that picks up *all* the positive solutions. The only place where some real work is involved is finding one solution. But the algorithm is fast.2012-02-08