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.

Find all $k_1, k_2$ that satisfy $k_1 a = k_2 b + c$ where everything are integers. It feels like there should be some easy way to describe this in terms of congruence and gcd.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Let $d=\gcd(a,b)$. If $d$ does not divide $c$, there is no solution. So assume from now on that $d$ divides $c$.

Suppose that we have found one particular solution $(x_0,y_0)$ of the equation $ax=by+c$. Then all solutions $(x,y)$ are given by $$x=x_0 +\frac{b}{d}t, \qquad y=y_0+\frac{a}{d}t,\tag{$1$}$$ where $t$ ranges over the integers, positive, negative, and $0$.

So now look for a particular solution $(x_0,y_0)$. In "small" cases, a particular solution can be found by experimentation. In other cases, use the Extended Euclidean Algorithm to find integers $s$ and $t$ such that $as=bt+d$. Then a particular solution $(x_0,y_0)$ of our original equation is given by $$x_0=\frac{c}{d}s,\qquad y_0=\frac{c}{d}t.$$ Now using $(1)$ we can generate all the solutions.

share|improve this answer

This is the simplest of the Diophantine equation i.e. linear Diophantine equation with 2 variables.$$ax+by=c$$ The condition for solvability is - $ax+by=c$ admits a solution if and only if $gcd(a,b)|c$ .
And if $(x_0,y_0)$ is any particular solution of this equation , then all other solutions are given by$$x=x_0+\frac{b}{d}t\quad \quad y=y_0-\frac{a}{b}t$$ For example consider the linear Diophantine equation$$172x+20y=1000$$ So applying Euclid's algorithms to find the gcd. $$\begin{align*}172&=8.20+12 \\ 20&=1.12+8\\ 12&=1.8+4\\ 8&=2.4\end{align*}$$ So the $\text{gcd}(172,20)=4$.And since $4|1000$ ,a solution to this equation exists.So working backward. $$\begin{align*}4&=12-8\\ &=12-(20-12)\\ &=2.12-20\\ &=2(172-8.20)-20\\ &=2.172+(-17)20 \end{align*}$$ Multiplying by $250$ we get$$1000=500.172+(-4250)20$$ So $x=500 \text{ and }y=-4250$. And then putting these value in above formula you can get the general solution.

share|improve this answer

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.