This question already has an answer here:

I was trying to solve some algorithms when I found out that one could leverage a simple stupid linear Diophantine equation, but I cannot figure out how solve it (I'm pretty sure I would have been able to do that back in high-school but I guess I am getting rusted).

Basically, I ended up on this equation: $ax+by=c$, where $a=3$, $b=5$ and the triplet $\lbrace a, b, c\rbrace \in ℕ$

Which is to say the least the most "basic" Diophantine equation.

Obviously, I am trying to find out the value of $x$ and $y$ according to $c$ that are .

The equation has a solution upon the condition that $c$ is a multiple of $gcd(a,b)=gcd(3,5)=1$

I noticed that there is an obvious solution here, which is the couple: $\lbrace x=2c, y=-c\rbrace$

Supposedly other solutions are of the form: $\lbrace x + kv, y − ku\rbrace$ where $k$ is an arbitrary integer such as: $u=\frac{a}{gcd(a,b)}=\frac{3}{1}=3$ and $v=\frac{b}{gcd(a,b)}=\frac{5}{1}=5$.

Therefore other solutions are more specifically $\lbrace 2c = x + 5k, -c = y − 3k\rbrace$

Equivalent to: $\lbrace x = 2c - 5k, y = -c + 3k\rbrace$

At that point I cannot manage to find the value of $k$ that would make $x$ and / or $y$ positive.

The replacement strategy seem to lead to nothing.

I am pretty sure it might be really easy but cannot get my head around it.

Any idea?


My point is how to find out $k$. If I'm just replacing $x$ and $y$ with their respective values found above in the former equation, I am going to end up with:

$3(2c+5k) + 5(-c+3k) = c$

$\Rightarrow 6c + 15k -5c + 15k = c$

$\Rightarrow c + 30k = c$

$\Rightarrow 30k = c - c = 0...$

I don't think $k$ is equal to $0$... so I might be wrong.


marked as duplicate by Dietrich Burde, user147263, Shailesh, Daniel W. Farlow, N. F. Taussig Feb 26 '16 at 0:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I don't think the question has already an answer, I didn't properly phrased the problem at first. Basically my issue lies more in how to find out k than in resolving the Diophantine the equation itself. $\endgroup$ – Ehouarn Perret Feb 27 '16 at 12:40

$3x+5y=c$ and $3(2c)+5(-c)=c$ imply $3(x-2c)-5(y+c)=0$ which give all the solutions by $$x-2c=5t$$ and $$y+c=3t$$

  • $\begingroup$ I know how to end up on that, my question is more about finding out the value(s) of k depending on c. $\endgroup$ – Ehouarn Perret Feb 27 '16 at 12:37
  • $\begingroup$ I apologize, so I did not read well enough your question $\endgroup$ – Piquito Feb 28 '16 at 2:45

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