Hey, I got the Diophantine equation $3x + 4y = 5$ over $\mathbb{Z}$ numbers

Question

I've got a Diophantine equation: $$3x + 4y = 5$$ over $\mathbb{Z}$ numbers. The solution for this equation on WolframAlpha is: $$x = -4n-1, y=3n+2$$ and $n \in \mathbb{Z}$. I wonder where this solution comes from ... Please help ;)

Answer 1

OK, here's my take on how the solution set of (1) (see below) may be derived in a non ad-hoc manner; I haven't really (knowingly) invoked any established theory here, just "followed my nose", as it were.

Consider any two solutions $(x_1, y_1)$, $(x_2, y_2)$ to

$3x + 4y = 5; \tag 1$

we have:

$3x_1 + 4y_1 = 5, \tag 2$

$3x_2 + 4y_2 = 5; \tag 3$

subtracting (2) from (3) yields

$3 \Delta x + 4 \Delta y = 0, \tag 4$

where

$\Delta x = x_2 - x_1, \; \Delta y = y_2 - y_1 \in \Bbb Z; \tag 5$

then

$4\Delta y = -3 \Delta x; \tag 6$

thus,

$4 = 2^2 \mid -3\Delta x; \tag 7$

since $2$ is prime and $2 \not \mid 3$ we must have

$4 =2^2 \mid \Delta x; \tag 8$

that is,

$\Delta x = 4n, \; n \in \Bbb Z; \tag 9$

then (6) becomes

$4\Delta y = -12n, \tag{10}$

whence

$\Delta y = -3n; \tag{11}$

in the light of (5) we may thus express the solution $(x_2, y_2)$ as

$x_2 = x_1 + \Delta x = x_1 + 4n, \; y_2 = y_1 + \Delta y = y_1 - 3n, \; n \in \Bbb Z ; \tag{12}$

since any two solutions are related in this manner, we may find every solution by choosing "seed values" for $x_1$ and $y_1$ satisfying (2); any such pair will suffice; it is mere convenience to take

$x_1 = -1, \; y_1 = 2, \; n = 0; \tag{13}$

thus every solution may be written in the form

$x = x_2 = 4n - 1, \; y = y_2 = 3n + 2, \; n \in \Bbb Z; \tag{14}$

we notice the sign of $n$ is opposite to that given in the text of the question; but this is not really significant, since the swap $-n \longleftrightarrow n$ leaves the solution set invariant. $OE\Delta$.

Answer 2

First you fine a combination of $3$ and $4$ to make a $5$

They found one combination $$3(-1)+4(2)=5$$

Then you add $3(-4n)+4(3n)=0$ to both sides to get $$3(-4n-1)+4(3n+2)=5$$

Thus $x=-4n-1$ and $y=3n+2$ work.

Answer 3

The solution is a result of how linear Diophantine equations operate. In particular, we seek solutions to the equation

$$3x+4y=1$$

This can only be done provided that $gcd(3,4)=1$, which it does. There are many techniques to solving this problem (my favorite being the Kuttaka method), but one solution is $x=-1$ and $y=1$. From here, we solve the problem for $5$ instead of $1$. This means that we need to scale the problem by $5$, so the answer is $x=-5$ and $y=5$.

We still have infinitely many solutions to generate. We let $x=c-5$ and $y=d+5$ to get

$$3c+4d=0$$

The smallest values for $c$ and $d$ that solve this are $c=-4$ and $d=3$ (the negative sign can be put on either term). From here, all other solutions are scales of this, so we have

$$x=-5-4n,\;\;\;\;y=5+3n,\;\;\;\;n\in\mathbb{Z}$$

To simplify a bit, $x=-5-4n=-4-4n-1=-4(n+1)-1$, and similarly $y=3(n+1)+2$. By reindexing, we get the answer you have.

I hope you found this helpful!