Mixing
![Why are the protons in the nucleus not repelled by each other? [duplicate]](https://lh4.googleusercontent.com/-m2vMXind9xY/AAAAAAAAAAI/AAAAAAAAABg/Zooc8mD7W5o/s72-c/photo.jpg?sz=32)
How to find solutions of linear Diophantine ax + by = c?
$begingroup$
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?
I tried to play around with it:
$x = (c - by)/a$, hence $a|(c - by)$.
$a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?
Thanks,
Chan
elementary-number-theory diophantine-equations linear-diophantine-equations
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
$endgroup$
add a comment |
$begingroup$
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?
I tried to play around with it:
$x = (c - by)/a$, hence $a|(c - by)$.
$a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?
Thanks,
Chan
elementary-number-theory diophantine-equations linear-diophantine-equations
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
$endgroup$
6
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
1
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56
add a comment |
$begingroup$
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?
I tried to play around with it:
$x = (c - by)/a$, hence $a|(c - by)$.
$a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?
Thanks,
Chan
elementary-number-theory diophantine-equations linear-diophantine-equations
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
$endgroup$
I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ?
I tried to play around with it:
$x = (c - by)/a$, hence $a|(c - by)$.
$a$, $c$ and $b$ are known. So to obtain integer solution for $a$, then $c - by = ak$, and I lost from here, because $y = (c - ak)/b$. I kept repeating this routine and could not find a way to get rid of it? Any hint?
Thanks,
Chan
elementary-number-theory diophantine-equations linear-diophantine-equations
elementary-number-theory diophantine-equations linear-diophantine-equations
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
edited Jun 5 '16 at 6:22
Martin Sleziak
44.8k10118272
44.8k10118272
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
asked Feb 6 '11 at 19:08
ChanChan
5,3961178121
5,3961178121
6
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
1
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56
add a comment |
6
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
1
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56
6
6
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
1
1
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
The diophantine equation $ax+by = c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $gcd(a,b)$ divides $c$, there exists an integer $k$ such that $gcd(a,b)k = c$. Multiplying $as+bt=gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = gcd(a,b)k = c.$$
So this gives one solution, with $x=sk$ and $y=tk$.
Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $frac{a}{gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + rfrac{a}{gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rbleft(frac{a}{gcd(a,b)}right)$$
which yields
$$gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - rfrac{b}{gcd(a,b)}$.
Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - rfrac{b}{gcd(a,b)},qquad y = y_1 + rfrac{a}{gcd(a,b)}$$
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$
First, we use the Euclidean Algorithm to find $gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
begin{align*}
258 &= 147(1) + 111 &quad&mbox{(equivalently, $111=258 - 147$)}\
147 &= 111(1) + 36&&mbox{(equivalently, $36 = 147 - 111$)}\
111 &= 36(3) + 3&&mbox{(equivalently, $3 = 111-3(36)$)}\
36 &= 3(12).
end{align*}
So $gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.
Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
begin{align*}
3 &= 111 - 3(36)\
&= 111 - 3(147 - 111) = 4(111) - 3(147)\
&= 4(258 - 147) - 3(147)\
&= 4(258) -7(147).
end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
begin{align*}
x &= 492 - frac{147r}{3} = 492 - 49r,\
y &= -861 + frac{258r}{3} =86r - 861, &qquad&rinmathbb{Z}.
end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then
begin{align*}
x &= 492 - 49(t+10) = 2 - 49t,\
y &= 86(t+10) - 861 = 86t - 1,&qquad&tinmathbb{Z}.
end{align*}
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
$endgroup$
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
|
show 3 more comments
$begingroup$
As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
The 1st row is the particular solution: 2 = 7(80) - 9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
$endgroup$
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
add a comment |
$begingroup$
Do you mean $gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get
$$
frac{a}{g}x+frac{b}{g}y=frac{c}{g}
$$
where $g=gcd(a,b)$.
But since $gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation
$$
frac{a}{g}x+frac{b}{g}y=1.
$$
Once you have that, the solution $(X,Y)=(frac{c}{g}cdot x_0,frac{c}{g}cdot y_0)$ is a solution to your original equation. Furthermore, the values
$$
x=X + frac{b}{g} tquad y=Y - frac{a}{g} t
$$
give all solutions when $t$ ranges over $mathbb{Z}$, I believe.
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
$endgroup$
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
add a comment |
$begingroup$
Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)
Solve $2x+3y=5$.
$2xequiv 5pmod{3}$.
You could either find a multiplicative inverse:
$xequiv 5cdot 2^{-1}pmod{3}$
Or do it as follows:
$2xequiv 2pmod{3}$
Divide both sides by $2$ (notice $gcd(3,2)=1$).
$xequiv 1pmod{3}$, $x=3n+1$, $ninmathbb Z$.
Substitute this value of $x$ into the original equation:
$2(3n+1)+3y=5$, $y=1-2n$.
Answer: $(x,y)=(3n+1,1-2n)$, $ninmathbb Z$.
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
$endgroup$
add a comment |
protected by hardmath Sep 29 '16 at 10:33
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The diophantine equation $ax+by = c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $gcd(a,b)$ divides $c$, there exists an integer $k$ such that $gcd(a,b)k = c$. Multiplying $as+bt=gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = gcd(a,b)k = c.$$
So this gives one solution, with $x=sk$ and $y=tk$.
Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $frac{a}{gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + rfrac{a}{gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rbleft(frac{a}{gcd(a,b)}right)$$
which yields
$$gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - rfrac{b}{gcd(a,b)}$.
Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - rfrac{b}{gcd(a,b)},qquad y = y_1 + rfrac{a}{gcd(a,b)}$$
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$
First, we use the Euclidean Algorithm to find $gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
begin{align*}
258 &= 147(1) + 111 &quad&mbox{(equivalently, $111=258 - 147$)}\
147 &= 111(1) + 36&&mbox{(equivalently, $36 = 147 - 111$)}\
111 &= 36(3) + 3&&mbox{(equivalently, $3 = 111-3(36)$)}\
36 &= 3(12).
end{align*}
So $gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.
Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
begin{align*}
3 &= 111 - 3(36)\
&= 111 - 3(147 - 111) = 4(111) - 3(147)\
&= 4(258 - 147) - 3(147)\
&= 4(258) -7(147).
end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
begin{align*}
x &= 492 - frac{147r}{3} = 492 - 49r,\
y &= -861 + frac{258r}{3} =86r - 861, &qquad&rinmathbb{Z}.
end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then
begin{align*}
x &= 492 - 49(t+10) = 2 - 49t,\
y &= 86(t+10) - 861 = 86t - 1,&qquad&tinmathbb{Z}.
end{align*}
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
$endgroup$
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
|
show 3 more comments
$begingroup$
The diophantine equation $ax+by = c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $gcd(a,b)$ divides $c$, there exists an integer $k$ such that $gcd(a,b)k = c$. Multiplying $as+bt=gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = gcd(a,b)k = c.$$
So this gives one solution, with $x=sk$ and $y=tk$.
Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $frac{a}{gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + rfrac{a}{gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rbleft(frac{a}{gcd(a,b)}right)$$
which yields
$$gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - rfrac{b}{gcd(a,b)}$.
Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - rfrac{b}{gcd(a,b)},qquad y = y_1 + rfrac{a}{gcd(a,b)}$$
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$
First, we use the Euclidean Algorithm to find $gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
begin{align*}
258 &= 147(1) + 111 &quad&mbox{(equivalently, $111=258 - 147$)}\
147 &= 111(1) + 36&&mbox{(equivalently, $36 = 147 - 111$)}\
111 &= 36(3) + 3&&mbox{(equivalently, $3 = 111-3(36)$)}\
36 &= 3(12).
end{align*}
So $gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.
Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
begin{align*}
3 &= 111 - 3(36)\
&= 111 - 3(147 - 111) = 4(111) - 3(147)\
&= 4(258 - 147) - 3(147)\
&= 4(258) -7(147).
end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
begin{align*}
x &= 492 - frac{147r}{3} = 492 - 49r,\
y &= -861 + frac{258r}{3} =86r - 861, &qquad&rinmathbb{Z}.
end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then
begin{align*}
x &= 492 - 49(t+10) = 2 - 49t,\
y &= 86(t+10) - 861 = 86t - 1,&qquad&tinmathbb{Z}.
end{align*}
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
$endgroup$
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
|
show 3 more comments
$begingroup$
The diophantine equation $ax+by = c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $gcd(a,b)$ divides $c$, there exists an integer $k$ such that $gcd(a,b)k = c$. Multiplying $as+bt=gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = gcd(a,b)k = c.$$
So this gives one solution, with $x=sk$ and $y=tk$.
Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $frac{a}{gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + rfrac{a}{gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rbleft(frac{a}{gcd(a,b)}right)$$
which yields
$$gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - rfrac{b}{gcd(a,b)}$.
Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - rfrac{b}{gcd(a,b)},qquad y = y_1 + rfrac{a}{gcd(a,b)}$$
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$
First, we use the Euclidean Algorithm to find $gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
begin{align*}
258 &= 147(1) + 111 &quad&mbox{(equivalently, $111=258 - 147$)}\
147 &= 111(1) + 36&&mbox{(equivalently, $36 = 147 - 111$)}\
111 &= 36(3) + 3&&mbox{(equivalently, $3 = 111-3(36)$)}\
36 &= 3(12).
end{align*}
So $gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.
Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
begin{align*}
3 &= 111 - 3(36)\
&= 111 - 3(147 - 111) = 4(111) - 3(147)\
&= 4(258 - 147) - 3(147)\
&= 4(258) -7(147).
end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
begin{align*}
x &= 492 - frac{147r}{3} = 492 - 49r,\
y &= -861 + frac{258r}{3} =86r - 861, &qquad&rinmathbb{Z}.
end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then
begin{align*}
x &= 492 - 49(t+10) = 2 - 49t,\
y &= 86(t+10) - 861 = 86t - 1,&qquad&tinmathbb{Z}.
end{align*}
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
$endgroup$
The diophantine equation $ax+by = c$ has solutions if and only if $gcd(a,b)|c$. If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.
To see this, note that the greatest common divisor of $a$ and $b$ divides both $ax$ and $by$, hence divides $c$ if there is a solution. This gives the necessity of the condition (which you have backwards). (fixed in edits)
The converse is actually a constructive proof, that you can find in pretty much every elementary number theory course or book, and which is essentially the same as yunone's answer above (but without dividing through first).
From the Extended Euclidean Algorithm, given any integers $a$ and $b$ you can find integers $s$ and $t$ such that $as+bt = gcd(a,b)$; the numbers $s$ and $t$ are not unique, but you only need one pair. Once you find $s$ and $t$, since we are assuming that $gcd(a,b)$ divides $c$, there exists an integer $k$ such that $gcd(a,b)k = c$. Multiplying $as+bt=gcd(a,b)$ through by $k$ you get
$$a(sk) + b(tk) = gcd(a,b)k = c.$$
So this gives one solution, with $x=sk$ and $y=tk$.
Now suppose that $ax_1 + by_1 = c$ is a solution, and $ax+by=c$ is some other solution. Taking the difference between the two, we get
$$a(x_1-x) + b(y_1-y) = 0.$$
Therefore, $a(x_1-x) = b(y-y_1)$. That means that $a$ divides $b(y-y_1)$, and therefore $frac{a}{gcd(a,b)}$ divides $y-y_1$. Therefore, $y = y_1 + rfrac{a}{gcd(a,b)}$ for some integer $r$. Substituting into the equation $a(x_1-x) = b(y-y_1)$ gives
$$a(x_1 - x) = rbleft(frac{a}{gcd(a,b)}right)$$
which yields
$$gcd(a,b)a(x_1-x) = rba$$
or $x = x_1 - rfrac{b}{gcd(a,b)}$.
Thus, if $ax_1+by_1 = c$ is any solution, then all solutions are of the form
$$x = x_1 - rfrac{b}{gcd(a,b)},qquad y = y_1 + rfrac{a}{gcd(a,b)}$$
exactly as yunone said.
To give you an example of this in action, suppose we want to find all integer solutions to $$258x + 147y = 369.$$
First, we use the Euclidean Algorithm to find $gcd(147,258)$; the parenthetical equation on the far right is how we will use this equality after we are done with the computation.
begin{align*}
258 &= 147(1) + 111 &quad&mbox{(equivalently, $111=258 - 147$)}\
147 &= 111(1) + 36&&mbox{(equivalently, $36 = 147 - 111$)}\
111 &= 36(3) + 3&&mbox{(equivalently, $3 = 111-3(36)$)}\
36 &= 3(12).
end{align*}
So $gcd(147,258)=3$. Since $3|369$, the equation has integral solutions.
Then we find a way of writing $3$ as a linear combination of $147$ and $258$, using the Euclidean algorithm computation above, and the equalities on the far right. We have:
begin{align*}
3 &= 111 - 3(36)\
&= 111 - 3(147 - 111) = 4(111) - 3(147)\
&= 4(258 - 147) - 3(147)\
&= 4(258) -7(147).
end{align*}
Then, we take $258(4) + 147(-7)=3$, and multiply through by $123$; why $123$? Because $3times 123 = 369$. We get:
$$258(492) + 147(-861) = 369.$$
So one solution is $x=492$ and $y=-861$. All other solutions will have the form
begin{align*}
x &= 492 - frac{147r}{3} = 492 - 49r,\
y &= -861 + frac{258r}{3} =86r - 861, &qquad&rinmathbb{Z}.
end{align*}
You can reduce those constants by making a simple change of variable. For example, if we let $r=t+10$, then
begin{align*}
x &= 492 - 49(t+10) = 2 - 49t,\
y &= 86(t+10) - 861 = 86t - 1,&qquad&tinmathbb{Z}.
end{align*}
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
edited Jul 22 '11 at 2:32
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
answered Feb 6 '11 at 20:46
Arturo MagidinArturo Magidin
263k34586911
263k34586911
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
|
show 3 more comments
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
5
5
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
All I have to say is AMAZING ANSWER ^_^!
$endgroup$
– Chan
Feb 6 '11 at 21:40
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
I think there was a typo on the line: $x = 592 - frac{147r}{3} = 492 - 49r$. I believe it should be $492$ on the left hand side.
$endgroup$
– Chan
Feb 28 '11 at 1:02
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
@Chan: Yes, thank you.
$endgroup$
– Arturo Magidin
Feb 28 '11 at 1:05
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
I don't mean to bug you all these months later, but I believe there is an extraneous $t$ in the equation for $y$ right before the gray page break line.
$endgroup$
– yunone
Jul 22 '11 at 2:15
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
$begingroup$
@yunone: On first glance, looks like you're right. Thanks.
$endgroup$
– Arturo Magidin
Jul 22 '11 at 2:32
|
show 3 more comments
$begingroup$
As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
The 1st row is the particular solution: 2 = 7(80) - 9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
$endgroup$
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
add a comment |
$begingroup$
As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
The 1st row is the particular solution: 2 = 7(80) - 9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
$endgroup$
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
add a comment |
$begingroup$
As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
The 1st row is the particular solution: 2 = 7(80) - 9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
$endgroup$
As others have mentioned one may employ the extended Euclidean algorithm. It deserves to be better known that this is most easily performed via row-reduction on an augmented matrix - analogous to methods used in linear algebra. See this excerpt from one of my old sci.math posts:
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(80) + y(62) proceeds as:
in equation form | in row form
---------------------+------------
80 = 1(80) + 0(62) | 80 1 0
62 = 0(80) + 1(62) | 62 0 1
row1 - row2 -> 18 = 1(80) - 1(62) | 18 1 -1
row2 - 3 row3 -> 8 = -3(80) + 4(62) | 8 -3 4
row3 - 2 row4 -> 2 = 7(80) - 9(62) | 2 7 -9
row4 - 4 row5 -> 0 = -31(80) -40(62) | 0 -31 40
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 80, 62, 18, 8, 2 = Euclidean remainder sequence
| |
for example 62-3(18) = 8, the 2nd step in Euclidean algorithm
becomes: row2 -3 row3 = row4 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 7 -9] [ 80 1 0] = [2 7 -9]
[-31 40] [ 62 0 1] [0 -31 40]
The 1st row is the particular solution: 2 = 7(80) - 9(62)
The 2nd row is the homogeneous solution: 0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 2n = (7n-31m) 80 + (40m-9n) 62
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
edited Sep 19 '16 at 14:52
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
answered Feb 6 '11 at 21:43
Bill DubuqueBill Dubuque
210k29192644
210k29192644
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
add a comment |
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
2
2
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
$begingroup$
Thanks, I really like your Linear Algebra approach.
$endgroup$
– Chan
Feb 6 '11 at 21:54
2
2
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
$begingroup$
@Chan: It irks me that most textbooks in elementary number theory present more obfuscated approaches. If you go on to study algebra you will learn more about the underlying theory when you study Hermite Smith normal forms and other module-theoretic generalizations of linear algebra results.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:06
2
2
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
$begingroup$
This is actually discussed in Niven, Zuckerman, Montgomery. Just so you have a reference (pages 217-218 in the 5th edition).
$endgroup$
– Arturo Magidin
Feb 6 '11 at 22:07
1
1
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
$begingroup$
@Arturo. Thanks for the reference. I'm happy to see that it finally made it into an edition of a popular textbook, but I'm sad that the presentation there leaves much to be desired.
$endgroup$
– Bill Dubuque
Feb 6 '11 at 22:21
add a comment |
$begingroup$
Do you mean $gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get
$$
frac{a}{g}x+frac{b}{g}y=frac{c}{g}
$$
where $g=gcd(a,b)$.
But since $gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation
$$
frac{a}{g}x+frac{b}{g}y=1.
$$
Once you have that, the solution $(X,Y)=(frac{c}{g}cdot x_0,frac{c}{g}cdot y_0)$ is a solution to your original equation. Furthermore, the values
$$
x=X + frac{b}{g} tquad y=Y - frac{a}{g} t
$$
give all solutions when $t$ ranges over $mathbb{Z}$, I believe.
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
$endgroup$
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
add a comment |
$begingroup$
Do you mean $gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get
$$
frac{a}{g}x+frac{b}{g}y=frac{c}{g}
$$
where $g=gcd(a,b)$.
But since $gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation
$$
frac{a}{g}x+frac{b}{g}y=1.
$$
Once you have that, the solution $(X,Y)=(frac{c}{g}cdot x_0,frac{c}{g}cdot y_0)$ is a solution to your original equation. Furthermore, the values
$$
x=X + frac{b}{g} tquad y=Y - frac{a}{g} t
$$
give all solutions when $t$ ranges over $mathbb{Z}$, I believe.
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
$endgroup$
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
add a comment |
$begingroup$
Do you mean $gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get
$$
frac{a}{g}x+frac{b}{g}y=frac{c}{g}
$$
where $g=gcd(a,b)$.
But since $gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation
$$
frac{a}{g}x+frac{b}{g}y=1.
$$
Once you have that, the solution $(X,Y)=(frac{c}{g}cdot x_0,frac{c}{g}cdot y_0)$ is a solution to your original equation. Furthermore, the values
$$
x=X + frac{b}{g} tquad y=Y - frac{a}{g} t
$$
give all solutions when $t$ ranges over $mathbb{Z}$, I believe.
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
$endgroup$
Do you mean $gcd(a,b)$ divides $c$? If so, you can divide both sides of the equation to get
$$
frac{a}{g}x+frac{b}{g}y=frac{c}{g}
$$
where $g=gcd(a,b)$.
But since $gcd(a/g,b/g)=1$, you can use the extended Euclidean algorithm to find a solution $(x_0,y_0)$ to the equation
$$
frac{a}{g}x+frac{b}{g}y=1.
$$
Once you have that, the solution $(X,Y)=(frac{c}{g}cdot x_0,frac{c}{g}cdot y_0)$ is a solution to your original equation. Furthermore, the values
$$
x=X + frac{b}{g} tquad y=Y - frac{a}{g} t
$$
give all solutions when $t$ ranges over $mathbb{Z}$, I believe.
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
answered Feb 6 '11 at 19:33
yunoneyunone
14.7k652132
14.7k652132
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
add a comment |
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
$begingroup$
@yuone: Yes, that gives all solutions.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 20:47
add a comment |
$begingroup$
Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)
Solve $2x+3y=5$.
$2xequiv 5pmod{3}$.
You could either find a multiplicative inverse:
$xequiv 5cdot 2^{-1}pmod{3}$
Or do it as follows:
$2xequiv 2pmod{3}$
Divide both sides by $2$ (notice $gcd(3,2)=1$).
$xequiv 1pmod{3}$, $x=3n+1$, $ninmathbb Z$.
Substitute this value of $x$ into the original equation:
$2(3n+1)+3y=5$, $y=1-2n$.
Answer: $(x,y)=(3n+1,1-2n)$, $ninmathbb Z$.
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
$endgroup$
add a comment |
$begingroup$
Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)
Solve $2x+3y=5$.
$2xequiv 5pmod{3}$.
You could either find a multiplicative inverse:
$xequiv 5cdot 2^{-1}pmod{3}$
Or do it as follows:
$2xequiv 2pmod{3}$
Divide both sides by $2$ (notice $gcd(3,2)=1$).
$xequiv 1pmod{3}$, $x=3n+1$, $ninmathbb Z$.
Substitute this value of $x$ into the original equation:
$2(3n+1)+3y=5$, $y=1-2n$.
Answer: $(x,y)=(3n+1,1-2n)$, $ninmathbb Z$.
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
$endgroup$
add a comment |
$begingroup$
Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)
Solve $2x+3y=5$.
$2xequiv 5pmod{3}$.
You could either find a multiplicative inverse:
$xequiv 5cdot 2^{-1}pmod{3}$
Or do it as follows:
$2xequiv 2pmod{3}$
Divide both sides by $2$ (notice $gcd(3,2)=1$).
$xequiv 1pmod{3}$, $x=3n+1$, $ninmathbb Z$.
Substitute this value of $x$ into the original equation:
$2(3n+1)+3y=5$, $y=1-2n$.
Answer: $(x,y)=(3n+1,1-2n)$, $ninmathbb Z$.
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
$endgroup$
Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a generalization. It may make it more clear.)
Solve $2x+3y=5$.
$2xequiv 5pmod{3}$.
You could either find a multiplicative inverse:
$xequiv 5cdot 2^{-1}pmod{3}$
Or do it as follows:
$2xequiv 2pmod{3}$
Divide both sides by $2$ (notice $gcd(3,2)=1$).
$xequiv 1pmod{3}$, $x=3n+1$, $ninmathbb Z$.
Substitute this value of $x$ into the original equation:
$2(3n+1)+3y=5$, $y=1-2n$.
Answer: $(x,y)=(3n+1,1-2n)$, $ninmathbb Z$.
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
edited May 17 '17 at 20:17
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
answered Jun 27 '16 at 22:35
user236182user236182
12k11233
12k11233
add a comment |
add a comment |
protected by hardmath Sep 29 '16 at 10:33
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
6
$begingroup$
en.wikipedia.org/wiki/Extended_Euclidean_algorithm
$endgroup$
– Qiaochu Yuan
Feb 6 '11 at 19:21
1
$begingroup$
Your condition is flipped; it's $gcd(a,b)|c$, not the other way around.
$endgroup$
– Arturo Magidin
Feb 6 '11 at 21:04
$begingroup$
@Arturo Magidin: Thanks, edited.
$endgroup$
– Chan
Feb 6 '11 at 21:37
$begingroup$
Read the following paper researchgate.net/publication/…. Hope it helps . best
$endgroup$
– Issam.Kaddoura
Sep 3 '16 at 14:56