3
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – watashiSHUN Oct 31 '15 at 20:44
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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