Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Bezout's Identity –  pedja Feb 8 '12 at 9:23

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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)? –  Jakub Feb 8 '12 at 9:50
    
@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. –  André Nicolas Feb 8 '12 at 10:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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