Solve in integers the equation $2x+3y = 5$

If I have the following equation $$2x+3y = 5$$ I know all the integer solutions is $$x = 1+3n$$ $$y = 1-2n$$ $$n \in \Bbb Z$$ since I can just plug them in $$2(1+3n)+3(1-2n) = 5+6n-6n = 5$$

but I don't know how to derive the answer from the equation... also is there a name for algorithms to solve these integer function?

• Browsing this tag may help. – user147263 Oct 31 '15 at 19:26
• The extended Euclidean algorithm gives you $x,y$ with $2x+3y=5$. – Dietrich Burde Oct 31 '15 at 19:32

It has solution because $1=\text{gcd}(2,3)\mid 5$.

Let $(x_0, y_0)$ any solution of $2x+3y=5$ i.e. for example $x_0=y_0=1$. Let $(x,y)$ any other solution i.e. $2x+3y=5$. Subtracting we get: $2(x-1)=3(1-y)$. Hence $1-y=2t$ and $x-1=3t.$

Then any general solution can be find by generating formula: $$(3t+1, 1-2t), \quad t\in \mathbb{Z}.$$

• can I say that since $(x-1)/(1-y) = 3/2$, if I let $$(1-y) = z$$ $$z \in \Bbb Z$$ then $$(x-1) = 3t/2$$ and for $$3t/2 \in \Bbb Z$$ $$t = 2z$$ $$z \in \Bbb Z$$ thus $$x = 3z+1$$ $$y = 1-2z$$ I know your argument is correct, I am just having a hard time convincing myself that it is the only solution and I can reuse such algorithm for similar problems – watashiSHUN Oct 31 '15 at 20:44

Theorem 1: The $\gcd(a,b)$ (where $a$ and $b$ not both $0$) is the least positive integer $ax + by$ for some $x,y\in\mathbb{Z}$.

Theorem 2: Every integer $ax+by$ is a multiple of $\gcd(a,b)$, and every multiple of $\gcd(a,b)$ is $ax+by$ for some $x,y\in\mathbb{Z}$.

Theorem 3: $ax+by=c$ has a solution $\iff \gcd(a,b)\mid c$. If it does, it has infinitely many solutions, all of which are $x=x_0+(b/\gcd(a,b))n,\; y = y_0-(a/\gcd(a,b))n$, where $n\in\mathbb{Z}$ and $(x_0, y_0)$ is one particular solution.

So to solve $ax+by=c$ completely, it boils down to finding one solution to $ax+by=\gcd(a,b)$. This can be done by the Extended Euclidean Algorithm.

if $2x+3y=5$, then $3y = 5-2x$. We then focus on making $5-2x$ divisible by $3$. This will happen for positive $x$ when $x = [1, 4, 7...]$ and for negative $x$ when $x = [-2, -5, -8...]$ If we line these up as $[...-8, -5, -2, 1, 4, 7...]$ we see that we have a common difference of $3$, yielding $3n$ or $-3n$, although both off by $1$, so we set $x = 1+3n$ or $x= 1-3n$

Similarly, we set $2x = 5 - 3y$, and desire to find $y$ such that $5-3y$ is divisible by $2$. This happens at $y = [...-5, -3, -1, 1, 3, 5...]$ We see that we have a common difference of $2$ with the values shifted up by $1$, yielding $y=1+2n$ or $y=1-2n$

Checking the conditional expressions for what we want, we have our final solution, $(1\pm3n, 1\mp2n), \quad n\in \mathbb{Z} \quad$ (note that the sign on the equation for $y$ must be the opposite for $x$)

First you find a particular solution. Say $(x, y) = (1, 1)$.

Then you suppose that $2x + 3y = 5$ for some $(x, y)$

So \begin{align} 2x + 3y &= 2(1) + 3(1)\\ 2(x-1) &= -3(y-1)\\ \end{align}

Hence $2 \mid -3(y-1)$.

Since $2$ and $-3$ are relatively prime, we must have $2 \mid y-1$. That is $y - 1 = 2t$ for some integer $t$.

So $y = 2t + 1$ for some integer $t$.

Substituting this back into $2(x-1) = -3(y-1)$, we find $x = -3t + 1$.

What we have shown is that, if $(x, y)$ is a solution to $2x + 3y = 5$, then $(x,y) = (-3t+1, 2t+1)$ for some integer $t$.

It is easy to verify that if $(x,y) = (-3t+1, 2t+1)$ for some integer $t$, then $(x, y)$ is a solution to $2x + 3y = 5$.

Hence $(x, y)$ is a solution to $2x + 3y = 5$, if and only if $(x,y) = (-3t+1, 2t+1)$ for some integer $t$.