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?

$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Can there be two (or more) solutions such that $n_1\neq n_0+ct$ for all t? Or are all solutions of form (n_0+ct, m_0+at) for a single (n_0,m_0)? $\endgroup$
    – Jakub
    Commented Feb 8, 2012 at 9:50
  • $\begingroup$ @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. $\endgroup$
    – André Nicolas
    Commented Feb 8, 2012 at 10:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .