Mixing
Use the Euclidean Algorithm to find $a, b, c, d$ such that $225a + 360b +432c +480d = 3$
up vote
10
down vote
favorite
I wish to find the integers of $a,b,c$ and $d$ such that:
$$225a + 360b +432c +480d = 3$$
which is equal to:
$$75a + 120b +144c+ 160d =1$$
I know I have to use the Euclidean algorithm. And I managed to do it for two integers $x$ and $y$. But can't figure out, how to do it with $4$ integers.
number-theory
edited yesterday
Xander Henderson
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
add a comment |
up vote
10
down vote
favorite
I wish to find the integers of $a,b,c$ and $d$ such that:
$$225a + 360b +432c +480d = 3$$
which is equal to:
$$75a + 120b +144c+ 160d =1$$
I know I have to use the Euclidean algorithm. And I managed to do it for two integers $x$ and $y$. But can't figure out, how to do it with $4$ integers.
number-theory
edited yesterday
Xander Henderson
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
1
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
1
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
1
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
1
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
4
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago
add a comment |
up vote
10
down vote
favorite
up vote
10
down vote
favorite
I wish to find the integers of $a,b,c$ and $d$ such that:
$$225a + 360b +432c +480d = 3$$
which is equal to:
$$75a + 120b +144c+ 160d =1$$
I know I have to use the Euclidean algorithm. And I managed to do it for two integers $x$ and $y$. But can't figure out, how to do it with $4$ integers.
number-theory
edited yesterday
Xander Henderson
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
I wish to find the integers of $a,b,c$ and $d$ such that:
$$225a + 360b +432c +480d = 3$$
which is equal to:
$$75a + 120b +144c+ 160d =1$$
I know I have to use the Euclidean algorithm. And I managed to do it for two integers $x$ and $y$. But can't figure out, how to do it with $4$ integers.
number-theory
number-theory
edited yesterday
Xander Henderson
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
edited yesterday
Xander Henderson
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
edited yesterday
Xander Henderson
13.8k93552
edited yesterday
Xander Henderson
13.8k93552
edited yesterday
Xander Henderson
13.8k93552
13.8k93552
asked 2 days ago
Joe Goldiamond
575216
asked 2 days ago
Joe Goldiamond
575216
asked 2 days ago
Joe Goldiamond
575216
575216
1
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
1
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
1
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
1
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
4
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago
add a comment |
1
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
1
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
1
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
1
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
4
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago
1
1
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
1
1
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
1
1
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
1
1
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
4
4
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago
add a comment |
6 Answers
6
active
oldest
votes
up vote
6
down vote
accepted
TO solve $75a+120b+144c+160d=1$
You can always you Euclidean Algorithm to solve $75A + 120B = gcd(75,120)=15$
And to solve $120beta + 144gamma = gcd(120,144) = 24$
And to solve $144C+160D = gcd(144,160)=16$.
Then in an attempt to solve $15e + 24f + 16g=1$ and to
Solve $15E + 24F= gcd(15,24) = 3$ and $24phi + 16rho = gcd(24,16)=8$.
Then solve $3j + 8k = 1$.
Then $j(15E + 24F) + (24phi + 16rho)k = 15(jE) + 24(jF+phi k) + 16(rho k)=1$
So $e=jE; f=jF+phi k; g=rho k$ and
So $(75A + 120B)e + (120beta + 144gamma)f + (144C+160D)g = 1$
And $a = Ae; b=Be+beta f; c=gamma f + Cg; d = Dg$.
Of, course there are probably insights and ways to make it simpler along the way.
But that's the general idea, just break it into smaller and smaller pieces.
===
To actually do this:
$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.
$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)
$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.
The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so
$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So
$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$
answered 2 days ago
fleablood
65.6k22682
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
add a comment |
up vote
6
down vote
$$ 144 cdot 12 - 75 cdot 23 = 3 $$
$$ 160 cdot 1 - 3 cdot 53 = 1 $$
$$ 160 cdot 1 - 53 ( 144 cdot 12 - 75 cdot 23 ) =1 $$
$$ 160 cdot 1 - 636 cdot 144 + 1219 cdot 75 = 1 $$
The shortest vector solution is
$$ a= 3, b= -2, c= -1, d= 1 $$
with
$$ 3 cdot 75 - 2 cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$
The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:
$$
left(
begin{array}{rrrr}
-175536 & 0 & 91585 & -144 \
-146280 & 1 & 76320 & -120 \
-91424 & 0 & 47700 & -75 \
end{array}
right)
$$
This three dimensional lattice has Gram determinant $66361$
Next is a reduced basis by the LLL algorithm.
$$
left(
begin{array}{rrrr}
0 & 4 & 0 & -3 \
0 & 2 & -5 & 3 \
8 & -1 & 0 & -3 \
end{array}
right)
$$
The Gram matrix for the reduced basis, still with determinant 66361, is
$$
left(
begin{array}{rrr}
25 & -1 & 5 \
-1 & 38 & -11 \
5 & -11 & 74 \
end{array}
right)
$$
There is a theorem involved here,
$$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by
$$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
answered 2 days ago
Will Jagy
100k597198
add a comment |
up vote
5
down vote
First divide both sides by $3$ to get $$ 75a+120b+144c+160d=1$$
Now let $$a=b=c=x$$
Your equation changes to $$339x+160d=1$$
You can solve this one for $x$ and $d$ because $339$ and $160$ are relatively prime.
Back substitute and you have your solution.
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
|
show 8 more comments
up vote
4
down vote
You can systematically solve any such equation (or prove that there are no solutions) by the following:
Take any integers $a,b,c,d$. Then the following correspond:
- Solutions of $75a+120b+144c+160d = 1$
- Solutions of $120b+144c+160d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d+75p = 1$ where $p$ is an integer
- Solutions of $45b+10d+75p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p+6q = 1$ where $q$ is an integer
- Solutions of $4d equiv 1 pmod{3}$
And now you simply follow the reverse correspondences.
answered 2 days ago
user21820
38k441149
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
add a comment |
up vote
4
down vote
$color{#c00}6 = 2(75)!-!144,, $ $color{#0a0}{80} = 2(120)!-!160 $ so $,bbox[5px,border:1px solid red]{1 = 75!+!color{#c00}6!-!color{#0a0}{80} = 3(75)-2(120) -144 + 160}$
Remark $ $ Found by perusing coef remainders: $bmod 75: 144equiv -color{#c00}6,,$ $,bmod 120!: 160equiv -color{#0a0}{80}$
i.e. we applied a few (judicious) steps of the extended Euclidean algorithm.
Alternatively, applying the algorithm mechanically, reducing each argument by the least argument, we get a longer computation like that in user21820's answer, viz.
$$begin{align}
&gcd(color{#88f}{75},120,144,160) {rm so reducing} bmod color{#8af}{75}\
= &gcd (75, 45,,-color{#0a0}6, 10) {rm so reducing} bmod color{#0a0}{6} \
= &gcd( 3, 0, {-}color{#0a0}6, {-}color{#f4f}2) {rm so reducing} bmod color{#F4f}{2}\
= &gcd( color{#d00}{bf 1}, 0, 0, {-}2)\
end{align}qquadqquad $$
yielding a Bezout identity for $color{#d00}{bf 1}$ from the augmented matrix in the extended algorithm (follow the above link for a complete presentation with the augmented matrix displayed).
answered 2 days ago
Bill Dubuque
206k29189621
add a comment |
up vote
1
down vote
Here is a description of a program that I wrote to solve such problems. It is definitely not optimized.
I start by considering the equalities
begin{array}{r}
160 &= 160(1) &+& 144(0) &+& 120(0) &+& 75(0) \
144 &= 160(0) &+& 144(1) &+& 120(0) &+& 75(0) \
120 &= 160(0) &+& 144(0) &+& 120(1) &+& 75(0) \
75 &= 160(0) &+& 144(0) &+& 120(0) &+& 75(1) \
end{array}
This can be abstracted into the following partitioned array
begin{array}{r|rrrr}
160 & 1 & 0 & 0 & 0 \
144 & 0 & 1 & 0 & 0 \
120 & 0 & 0 & 1 & 0 \
75 & 0 & 0 & 0 & 1 \
end{array}
The important thing to remember is that, at any time, a row $fbox{n | d c b a}$ represents the equality $n = 160d + 144c + 120b + 75a$.
The "outer loop" of this algorithm assumes that the left column is in descending order.
The first step is to reduce the three upper rows so that the entries in the first column are all less than the bottom left number, $75$. For the first row, we know that
$160 = 2 times 75 + 10$ so we replace row $1$ ($R1$) with $R1 - 2R4$, getting $fbox{10 | 1 0 0 -2}$. Negative remainders are allowed if their absolute value is less than the positive remainder. So since $144 = 75(2)-6$, we replace the second row with $R2 - 2R4$, getting $fbox{-6 | 0 1 0 -2}$. Similarly the third row becomes $R3 - 24$, which is $fbox{-30 | 0 0 1 -2}$. So we now have
begin{array}{r|rrrr}
10 & 1 & 0 & 0 & -2 \
-6 & 0 & 1 & 0 & -2 \
-30 & 0 & 0 & 1 & -2 \
75 & 0 & 0 & 0 & 1 \
end{array}
Next, we make the substitution $Rk to -Rk$ for any row with a negative first element and we then sort the array in decreasing order of the first element. We end up with
begin{array}{r|rrrr}
75 & 0 & 0 & 0 & 1 \
30 & 0 & 0 & -1 & 2 \
10 & 1 & 0 & 0 & -2 \
6 & 0 & -1 & 0 & 2 \
end{array}
After the next pass through the loop, we get
begin{array}{r|rrrr}
3 & 0 & 12 & 0 & -23 \
0 & 0 & 5 & -1 & -8 \
-2 & 1 & 2 & 0 & -6 \
6 & 0 & -1 & 0 & 2 \
end{array}
which "sorts" to
begin{array}{r|rrrr}
6 & 0 & -1 & 0 & 2 \
3 & 0 & 12 & 0 & -23 \
2 & -1 & -2 & 0 & 6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The next outer loop will proceed as before except that we will make our adjustments with respect to the third row instead of the fourth row. we finally end up with
begin{array}{r|rrrr}
1 & 1 & 14 & 0 & -29 \
0 & -3 & -30 & 0 & 64 \
0 & 3 & 5 & 0 & -6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The tells is that the general solution is (if I haven't messed up my math)
$(d,c,b,a) = (1, 14 , 0 , -29) + u(-3, -30, 0, 64) + v(3, 5, 0, -6) + w(0, 5, -1, -8)$
answered yesterday
steven gregory
17.4k22156
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
add a comment |
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
TO solve $75a+120b+144c+160d=1$
You can always you Euclidean Algorithm to solve $75A + 120B = gcd(75,120)=15$
And to solve $120beta + 144gamma = gcd(120,144) = 24$
And to solve $144C+160D = gcd(144,160)=16$.
Then in an attempt to solve $15e + 24f + 16g=1$ and to
Solve $15E + 24F= gcd(15,24) = 3$ and $24phi + 16rho = gcd(24,16)=8$.
Then solve $3j + 8k = 1$.
Then $j(15E + 24F) + (24phi + 16rho)k = 15(jE) + 24(jF+phi k) + 16(rho k)=1$
So $e=jE; f=jF+phi k; g=rho k$ and
So $(75A + 120B)e + (120beta + 144gamma)f + (144C+160D)g = 1$
And $a = Ae; b=Be+beta f; c=gamma f + Cg; d = Dg$.
Of, course there are probably insights and ways to make it simpler along the way.
But that's the general idea, just break it into smaller and smaller pieces.
===
To actually do this:
$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.
$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)
$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.
The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so
$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So
$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$
answered 2 days ago
fleablood
65.6k22682
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
add a comment |
up vote
6
down vote
accepted
TO solve $75a+120b+144c+160d=1$
You can always you Euclidean Algorithm to solve $75A + 120B = gcd(75,120)=15$
And to solve $120beta + 144gamma = gcd(120,144) = 24$
And to solve $144C+160D = gcd(144,160)=16$.
Then in an attempt to solve $15e + 24f + 16g=1$ and to
Solve $15E + 24F= gcd(15,24) = 3$ and $24phi + 16rho = gcd(24,16)=8$.
Then solve $3j + 8k = 1$.
Then $j(15E + 24F) + (24phi + 16rho)k = 15(jE) + 24(jF+phi k) + 16(rho k)=1$
So $e=jE; f=jF+phi k; g=rho k$ and
So $(75A + 120B)e + (120beta + 144gamma)f + (144C+160D)g = 1$
And $a = Ae; b=Be+beta f; c=gamma f + Cg; d = Dg$.
Of, course there are probably insights and ways to make it simpler along the way.
But that's the general idea, just break it into smaller and smaller pieces.
===
To actually do this:
$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.
$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)
$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.
The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so
$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So
$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$
answered 2 days ago
fleablood
65.6k22682
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
add a comment |
up vote
6
down vote
accepted
up vote
6
down vote
accepted
TO solve $75a+120b+144c+160d=1$
You can always you Euclidean Algorithm to solve $75A + 120B = gcd(75,120)=15$
And to solve $120beta + 144gamma = gcd(120,144) = 24$
And to solve $144C+160D = gcd(144,160)=16$.
Then in an attempt to solve $15e + 24f + 16g=1$ and to
Solve $15E + 24F= gcd(15,24) = 3$ and $24phi + 16rho = gcd(24,16)=8$.
Then solve $3j + 8k = 1$.
Then $j(15E + 24F) + (24phi + 16rho)k = 15(jE) + 24(jF+phi k) + 16(rho k)=1$
So $e=jE; f=jF+phi k; g=rho k$ and
So $(75A + 120B)e + (120beta + 144gamma)f + (144C+160D)g = 1$
And $a = Ae; b=Be+beta f; c=gamma f + Cg; d = Dg$.
Of, course there are probably insights and ways to make it simpler along the way.
But that's the general idea, just break it into smaller and smaller pieces.
===
To actually do this:
$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.
$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)
$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.
The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so
$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So
$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$
answered 2 days ago
fleablood
65.6k22682
TO solve $75a+120b+144c+160d=1$
You can always you Euclidean Algorithm to solve $75A + 120B = gcd(75,120)=15$
And to solve $120beta + 144gamma = gcd(120,144) = 24$
And to solve $144C+160D = gcd(144,160)=16$.
Then in an attempt to solve $15e + 24f + 16g=1$ and to
Solve $15E + 24F= gcd(15,24) = 3$ and $24phi + 16rho = gcd(24,16)=8$.
Then solve $3j + 8k = 1$.
Then $j(15E + 24F) + (24phi + 16rho)k = 15(jE) + 24(jF+phi k) + 16(rho k)=1$
So $e=jE; f=jF+phi k; g=rho k$ and
So $(75A + 120B)e + (120beta + 144gamma)f + (144C+160D)g = 1$
And $a = Ae; b=Be+beta f; c=gamma f + Cg; d = Dg$.
Of, course there are probably insights and ways to make it simpler along the way.
But that's the general idea, just break it into smaller and smaller pieces.
===
To actually do this:
$75A + 120B = 15$ means $5A + 8B =1$ so $A=-3; B=2$ and $75(-3) + 120(2) = 15$.
$120B + 144C =24$ means $5B + 6C =1$ so $B=-1;C=1$ and $120(-1)+144(1) = 24$. (Don't let the recycling of variable names scare you; we won't combine them.)
$144C + 160D=16$ means $9C + 10D =1$ so $144(-1) + 160(1) = 16$.
The solve $15e + 24f + 16g = 1 $ .... well, I can just see $f=0$ and $e = -1; g = 1$ so
$-(75(-3) + 120(2)) + (144(-1) + 160(1)) = -15 + 16 = 1$ So
$75*3 + 120*(-2) + 144(-1) + 160(1) = 1$
answered 2 days ago
fleablood
65.6k22682
edited 2 days ago
answered 2 days ago
fleablood
65.6k22682
answered 2 days ago
fleablood
65.6k22682
answered 2 days ago
fleablood
65.6k22682
65.6k22682
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
add a comment |
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
3
3
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
add a comment |
up vote
6
down vote
$$ 144 cdot 12 - 75 cdot 23 = 3 $$
$$ 160 cdot 1 - 3 cdot 53 = 1 $$
$$ 160 cdot 1 - 53 ( 144 cdot 12 - 75 cdot 23 ) =1 $$
$$ 160 cdot 1 - 636 cdot 144 + 1219 cdot 75 = 1 $$
The shortest vector solution is
$$ a= 3, b= -2, c= -1, d= 1 $$
with
$$ 3 cdot 75 - 2 cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$
The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:
$$
left(
begin{array}{rrrr}
-175536 & 0 & 91585 & -144 \
-146280 & 1 & 76320 & -120 \
-91424 & 0 & 47700 & -75 \
end{array}
right)
$$
This three dimensional lattice has Gram determinant $66361$
Next is a reduced basis by the LLL algorithm.
$$
left(
begin{array}{rrrr}
0 & 4 & 0 & -3 \
0 & 2 & -5 & 3 \
8 & -1 & 0 & -3 \
end{array}
right)
$$
The Gram matrix for the reduced basis, still with determinant 66361, is
$$
left(
begin{array}{rrr}
25 & -1 & 5 \
-1 & 38 & -11 \
5 & -11 & 74 \
end{array}
right)
$$
There is a theorem involved here,
$$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by
$$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
answered 2 days ago
Will Jagy
100k597198
add a comment |
up vote
6
down vote
$$ 144 cdot 12 - 75 cdot 23 = 3 $$
$$ 160 cdot 1 - 3 cdot 53 = 1 $$
$$ 160 cdot 1 - 53 ( 144 cdot 12 - 75 cdot 23 ) =1 $$
$$ 160 cdot 1 - 636 cdot 144 + 1219 cdot 75 = 1 $$
The shortest vector solution is
$$ a= 3, b= -2, c= -1, d= 1 $$
with
$$ 3 cdot 75 - 2 cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$
The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:
$$
left(
begin{array}{rrrr}
-175536 & 0 & 91585 & -144 \
-146280 & 1 & 76320 & -120 \
-91424 & 0 & 47700 & -75 \
end{array}
right)
$$
This three dimensional lattice has Gram determinant $66361$
Next is a reduced basis by the LLL algorithm.
$$
left(
begin{array}{rrrr}
0 & 4 & 0 & -3 \
0 & 2 & -5 & 3 \
8 & -1 & 0 & -3 \
end{array}
right)
$$
The Gram matrix for the reduced basis, still with determinant 66361, is
$$
left(
begin{array}{rrr}
25 & -1 & 5 \
-1 & 38 & -11 \
5 & -11 & 74 \
end{array}
right)
$$
There is a theorem involved here,
$$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by
$$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
answered 2 days ago
Will Jagy
100k597198
add a comment |
up vote
6
down vote
up vote
6
down vote
$$ 144 cdot 12 - 75 cdot 23 = 3 $$
$$ 160 cdot 1 - 3 cdot 53 = 1 $$
$$ 160 cdot 1 - 53 ( 144 cdot 12 - 75 cdot 23 ) =1 $$
$$ 160 cdot 1 - 636 cdot 144 + 1219 cdot 75 = 1 $$
The shortest vector solution is
$$ a= 3, b= -2, c= -1, d= 1 $$
with
$$ 3 cdot 75 - 2 cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$
The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:
$$
left(
begin{array}{rrrr}
-175536 & 0 & 91585 & -144 \
-146280 & 1 & 76320 & -120 \
-91424 & 0 & 47700 & -75 \
end{array}
right)
$$
This three dimensional lattice has Gram determinant $66361$
Next is a reduced basis by the LLL algorithm.
$$
left(
begin{array}{rrrr}
0 & 4 & 0 & -3 \
0 & 2 & -5 & 3 \
8 & -1 & 0 & -3 \
end{array}
right)
$$
The Gram matrix for the reduced basis, still with determinant 66361, is
$$
left(
begin{array}{rrr}
25 & -1 & 5 \
-1 & 38 & -11 \
5 & -11 & 74 \
end{array}
right)
$$
There is a theorem involved here,
$$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by
$$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
answered 2 days ago
Will Jagy
100k597198
$$ 144 cdot 12 - 75 cdot 23 = 3 $$
$$ 160 cdot 1 - 3 cdot 53 = 1 $$
$$ 160 cdot 1 - 53 ( 144 cdot 12 - 75 cdot 23 ) =1 $$
$$ 160 cdot 1 - 636 cdot 144 + 1219 cdot 75 = 1 $$
The shortest vector solution is
$$ a= 3, b= -2, c= -1, d= 1 $$
with
$$ 3 cdot 75 - 2 cdot 120 - 144 + 160 = 225 -240 -144 + 160 = 1 $$
The more interesting question is finding a basis for the lattice of integer vectors orthogonal to your vector. A basis is given by these three rows:
$$
left(
begin{array}{rrrr}
-175536 & 0 & 91585 & -144 \
-146280 & 1 & 76320 & -120 \
-91424 & 0 & 47700 & -75 \
end{array}
right)
$$
This three dimensional lattice has Gram determinant $66361$
Next is a reduced basis by the LLL algorithm.
$$
left(
begin{array}{rrrr}
0 & 4 & 0 & -3 \
0 & 2 & -5 & 3 \
8 & -1 & 0 & -3 \
end{array}
right)
$$
The Gram matrix for the reduced basis, still with determinant 66361, is
$$
left(
begin{array}{rrr}
25 & -1 & 5 \
-1 & 38 & -11 \
5 & -11 & 74 \
end{array}
right)
$$
There is a theorem involved here,
$$ 75^2 + 120^2 + 144^2 + 160^2 = 66361 $$
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by
$$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
answered 2 days ago
Will Jagy
100k597198
edited 2 days ago
answered 2 days ago
Will Jagy
100k597198
answered 2 days ago
Will Jagy
100k597198
answered 2 days ago
Will Jagy
100k597198
100k597198
add a comment |
add a comment |
up vote
5
down vote
First divide both sides by $3$ to get $$ 75a+120b+144c+160d=1$$
Now let $$a=b=c=x$$
Your equation changes to $$339x+160d=1$$
You can solve this one for $x$ and $d$ because $339$ and $160$ are relatively prime.
Back substitute and you have your solution.
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
|
show 8 more comments
up vote
5
down vote
First divide both sides by $3$ to get $$ 75a+120b+144c+160d=1$$
Now let $$a=b=c=x$$
Your equation changes to $$339x+160d=1$$
You can solve this one for $x$ and $d$ because $339$ and $160$ are relatively prime.
Back substitute and you have your solution.
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
|
show 8 more comments
up vote
5
down vote
up vote
5
down vote
First divide both sides by $3$ to get $$ 75a+120b+144c+160d=1$$
Now let $$a=b=c=x$$
Your equation changes to $$339x+160d=1$$
You can solve this one for $x$ and $d$ because $339$ and $160$ are relatively prime.
Back substitute and you have your solution.
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
First divide both sides by $3$ to get $$ 75a+120b+144c+160d=1$$
Now let $$a=b=c=x$$
Your equation changes to $$339x+160d=1$$
You can solve this one for $x$ and $d$ because $339$ and $160$ are relatively prime.
Back substitute and you have your solution.
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
answered 2 days ago
Mohammad Riazi-Kermani
40.2k41958
40.2k41958
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
|
show 8 more comments
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
1
1
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
Interesting. But I don't understand why $a = b = c = x$ is a valid substitution, especially given we find (later) that $a neq b neq c$. Any explanation?
– David G. Stork
2 days ago
1
1
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
The solution is not unique. Any combination of the first three coefficients which gives an integer relatively prime to $160$ will do.
– Mohammad Riazi-Kermani
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
But given the selection of $a, b, c$ is not unique, even given the relative prime condition, won't different choices lead to different $d$s? But the true solution may be unique.
– David G. Stork
2 days ago
1
1
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
All solutions $(a,b,c,d)$ are given, with integer $s,t,u,$ by $$ (3+8u,-2+4s+2t-u,-1-5t,1-3s+3t-3u) $$
– Will Jagy
2 days ago
1
1
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
@MackTuesday: That's actually incorrect. "$6a+15b+35c+28d = 1$" has solutions (which you can find systematically by the method described in my post, but substituting $a=b=c$ gives "$56a+28d = 1$", substituting $a=b=d$ gives "$49a+35c = 1$", substituting $a=c=d$ gives "$69a+15b = 1$", and substituting $b=c=d$ gives "$6a+78b = 1$", all of which have no solution!
– user21820
2 days ago
|
show 8 more comments
up vote
4
down vote
You can systematically solve any such equation (or prove that there are no solutions) by the following:
Take any integers $a,b,c,d$. Then the following correspond:
- Solutions of $75a+120b+144c+160d = 1$
- Solutions of $120b+144c+160d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d+75p = 1$ where $p$ is an integer
- Solutions of $45b+10d+75p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p+6q = 1$ where $q$ is an integer
- Solutions of $4d equiv 1 pmod{3}$
And now you simply follow the reverse correspondences.
answered 2 days ago
user21820
38k441149
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
add a comment |
up vote
4
down vote
You can systematically solve any such equation (or prove that there are no solutions) by the following:
Take any integers $a,b,c,d$. Then the following correspond:
- Solutions of $75a+120b+144c+160d = 1$
- Solutions of $120b+144c+160d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d+75p = 1$ where $p$ is an integer
- Solutions of $45b+10d+75p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p+6q = 1$ where $q$ is an integer
- Solutions of $4d equiv 1 pmod{3}$
And now you simply follow the reverse correspondences.
answered 2 days ago
user21820
38k441149
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
add a comment |
up vote
4
down vote
up vote
4
down vote
You can systematically solve any such equation (or prove that there are no solutions) by the following:
Take any integers $a,b,c,d$. Then the following correspond:
- Solutions of $75a+120b+144c+160d = 1$
- Solutions of $120b+144c+160d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d+75p = 1$ where $p$ is an integer
- Solutions of $45b+10d+75p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p+6q = 1$ where $q$ is an integer
- Solutions of $4d equiv 1 pmod{3}$
And now you simply follow the reverse correspondences.
answered 2 days ago
user21820
38k441149
You can systematically solve any such equation (or prove that there are no solutions) by the following:
Take any integers $a,b,c,d$. Then the following correspond:
- Solutions of $75a+120b+144c+160d = 1$
- Solutions of $120b+144c+160d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d equiv 1 pmod{75}$
- Solutions of $45b-6c+10d+75p = 1$ where $p$ is an integer
- Solutions of $45b+10d+75p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p equiv 1 pmod{6}$
- Solutions of $3b+4d+3p+6q = 1$ where $q$ is an integer
- Solutions of $4d equiv 1 pmod{3}$
And now you simply follow the reverse correspondences.
answered 2 days ago
user21820
38k441149
answered 2 days ago
user21820
38k441149
answered 2 days ago
user21820
38k441149
answered 2 days ago
user21820
38k441149
38k441149
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
add a comment |
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
1
1
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
Worth emphasis. the above is a special case of the Extended Euclidean Algorithm, which is most conveniently done by hand in augmented-matrix form - see the remark in my answer here.
– Bill Dubuque
yesterday
add a comment |
up vote
4
down vote
$color{#c00}6 = 2(75)!-!144,, $ $color{#0a0}{80} = 2(120)!-!160 $ so $,bbox[5px,border:1px solid red]{1 = 75!+!color{#c00}6!-!color{#0a0}{80} = 3(75)-2(120) -144 + 160}$
Remark $ $ Found by perusing coef remainders: $bmod 75: 144equiv -color{#c00}6,,$ $,bmod 120!: 160equiv -color{#0a0}{80}$
i.e. we applied a few (judicious) steps of the extended Euclidean algorithm.
Alternatively, applying the algorithm mechanically, reducing each argument by the least argument, we get a longer computation like that in user21820's answer, viz.
$$begin{align}
&gcd(color{#88f}{75},120,144,160) {rm so reducing} bmod color{#8af}{75}\
= &gcd (75, 45,,-color{#0a0}6, 10) {rm so reducing} bmod color{#0a0}{6} \
= &gcd( 3, 0, {-}color{#0a0}6, {-}color{#f4f}2) {rm so reducing} bmod color{#F4f}{2}\
= &gcd( color{#d00}{bf 1}, 0, 0, {-}2)\
end{align}qquadqquad $$
yielding a Bezout identity for $color{#d00}{bf 1}$ from the augmented matrix in the extended algorithm (follow the above link for a complete presentation with the augmented matrix displayed).
answered 2 days ago
Bill Dubuque
206k29189621
add a comment |
up vote
4
down vote
$color{#c00}6 = 2(75)!-!144,, $ $color{#0a0}{80} = 2(120)!-!160 $ so $,bbox[5px,border:1px solid red]{1 = 75!+!color{#c00}6!-!color{#0a0}{80} = 3(75)-2(120) -144 + 160}$
Remark $ $ Found by perusing coef remainders: $bmod 75: 144equiv -color{#c00}6,,$ $,bmod 120!: 160equiv -color{#0a0}{80}$
i.e. we applied a few (judicious) steps of the extended Euclidean algorithm.
Alternatively, applying the algorithm mechanically, reducing each argument by the least argument, we get a longer computation like that in user21820's answer, viz.
$$begin{align}
&gcd(color{#88f}{75},120,144,160) {rm so reducing} bmod color{#8af}{75}\
= &gcd (75, 45,,-color{#0a0}6, 10) {rm so reducing} bmod color{#0a0}{6} \
= &gcd( 3, 0, {-}color{#0a0}6, {-}color{#f4f}2) {rm so reducing} bmod color{#F4f}{2}\
= &gcd( color{#d00}{bf 1}, 0, 0, {-}2)\
end{align}qquadqquad $$
yielding a Bezout identity for $color{#d00}{bf 1}$ from the augmented matrix in the extended algorithm (follow the above link for a complete presentation with the augmented matrix displayed).
answered 2 days ago
Bill Dubuque
206k29189621
add a comment |
up vote
4
down vote
up vote
4
down vote
$color{#c00}6 = 2(75)!-!144,, $ $color{#0a0}{80} = 2(120)!-!160 $ so $,bbox[5px,border:1px solid red]{1 = 75!+!color{#c00}6!-!color{#0a0}{80} = 3(75)-2(120) -144 + 160}$
Remark $ $ Found by perusing coef remainders: $bmod 75: 144equiv -color{#c00}6,,$ $,bmod 120!: 160equiv -color{#0a0}{80}$
i.e. we applied a few (judicious) steps of the extended Euclidean algorithm.
Alternatively, applying the algorithm mechanically, reducing each argument by the least argument, we get a longer computation like that in user21820's answer, viz.
$$begin{align}
&gcd(color{#88f}{75},120,144,160) {rm so reducing} bmod color{#8af}{75}\
= &gcd (75, 45,,-color{#0a0}6, 10) {rm so reducing} bmod color{#0a0}{6} \
= &gcd( 3, 0, {-}color{#0a0}6, {-}color{#f4f}2) {rm so reducing} bmod color{#F4f}{2}\
= &gcd( color{#d00}{bf 1}, 0, 0, {-}2)\
end{align}qquadqquad $$
yielding a Bezout identity for $color{#d00}{bf 1}$ from the augmented matrix in the extended algorithm (follow the above link for a complete presentation with the augmented matrix displayed).
answered 2 days ago
Bill Dubuque
206k29189621
$color{#c00}6 = 2(75)!-!144,, $ $color{#0a0}{80} = 2(120)!-!160 $ so $,bbox[5px,border:1px solid red]{1 = 75!+!color{#c00}6!-!color{#0a0}{80} = 3(75)-2(120) -144 + 160}$
Remark $ $ Found by perusing coef remainders: $bmod 75: 144equiv -color{#c00}6,,$ $,bmod 120!: 160equiv -color{#0a0}{80}$
i.e. we applied a few (judicious) steps of the extended Euclidean algorithm.
Alternatively, applying the algorithm mechanically, reducing each argument by the least argument, we get a longer computation like that in user21820's answer, viz.
$$begin{align}
&gcd(color{#88f}{75},120,144,160) {rm so reducing} bmod color{#8af}{75}\
= &gcd (75, 45,,-color{#0a0}6, 10) {rm so reducing} bmod color{#0a0}{6} \
= &gcd( 3, 0, {-}color{#0a0}6, {-}color{#f4f}2) {rm so reducing} bmod color{#F4f}{2}\
= &gcd( color{#d00}{bf 1}, 0, 0, {-}2)\
end{align}qquadqquad $$
yielding a Bezout identity for $color{#d00}{bf 1}$ from the augmented matrix in the extended algorithm (follow the above link for a complete presentation with the augmented matrix displayed).
answered 2 days ago
Bill Dubuque
206k29189621
edited yesterday
answered 2 days ago
Bill Dubuque
206k29189621
answered 2 days ago
Bill Dubuque
206k29189621
answered 2 days ago
Bill Dubuque
206k29189621
206k29189621
add a comment |
add a comment |
up vote
1
down vote
Here is a description of a program that I wrote to solve such problems. It is definitely not optimized.
I start by considering the equalities
begin{array}{r}
160 &= 160(1) &+& 144(0) &+& 120(0) &+& 75(0) \
144 &= 160(0) &+& 144(1) &+& 120(0) &+& 75(0) \
120 &= 160(0) &+& 144(0) &+& 120(1) &+& 75(0) \
75 &= 160(0) &+& 144(0) &+& 120(0) &+& 75(1) \
end{array}
This can be abstracted into the following partitioned array
begin{array}{r|rrrr}
160 & 1 & 0 & 0 & 0 \
144 & 0 & 1 & 0 & 0 \
120 & 0 & 0 & 1 & 0 \
75 & 0 & 0 & 0 & 1 \
end{array}
The important thing to remember is that, at any time, a row $fbox{n | d c b a}$ represents the equality $n = 160d + 144c + 120b + 75a$.
The "outer loop" of this algorithm assumes that the left column is in descending order.
The first step is to reduce the three upper rows so that the entries in the first column are all less than the bottom left number, $75$. For the first row, we know that
$160 = 2 times 75 + 10$ so we replace row $1$ ($R1$) with $R1 - 2R4$, getting $fbox{10 | 1 0 0 -2}$. Negative remainders are allowed if their absolute value is less than the positive remainder. So since $144 = 75(2)-6$, we replace the second row with $R2 - 2R4$, getting $fbox{-6 | 0 1 0 -2}$. Similarly the third row becomes $R3 - 24$, which is $fbox{-30 | 0 0 1 -2}$. So we now have
begin{array}{r|rrrr}
10 & 1 & 0 & 0 & -2 \
-6 & 0 & 1 & 0 & -2 \
-30 & 0 & 0 & 1 & -2 \
75 & 0 & 0 & 0 & 1 \
end{array}
Next, we make the substitution $Rk to -Rk$ for any row with a negative first element and we then sort the array in decreasing order of the first element. We end up with
begin{array}{r|rrrr}
75 & 0 & 0 & 0 & 1 \
30 & 0 & 0 & -1 & 2 \
10 & 1 & 0 & 0 & -2 \
6 & 0 & -1 & 0 & 2 \
end{array}
After the next pass through the loop, we get
begin{array}{r|rrrr}
3 & 0 & 12 & 0 & -23 \
0 & 0 & 5 & -1 & -8 \
-2 & 1 & 2 & 0 & -6 \
6 & 0 & -1 & 0 & 2 \
end{array}
which "sorts" to
begin{array}{r|rrrr}
6 & 0 & -1 & 0 & 2 \
3 & 0 & 12 & 0 & -23 \
2 & -1 & -2 & 0 & 6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The next outer loop will proceed as before except that we will make our adjustments with respect to the third row instead of the fourth row. we finally end up with
begin{array}{r|rrrr}
1 & 1 & 14 & 0 & -29 \
0 & -3 & -30 & 0 & 64 \
0 & 3 & 5 & 0 & -6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The tells is that the general solution is (if I haven't messed up my math)
$(d,c,b,a) = (1, 14 , 0 , -29) + u(-3, -30, 0, 64) + v(3, 5, 0, -6) + w(0, 5, -1, -8)$
answered yesterday
steven gregory
17.4k22156
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
add a comment |
up vote
1
down vote
Here is a description of a program that I wrote to solve such problems. It is definitely not optimized.
I start by considering the equalities
begin{array}{r}
160 &= 160(1) &+& 144(0) &+& 120(0) &+& 75(0) \
144 &= 160(0) &+& 144(1) &+& 120(0) &+& 75(0) \
120 &= 160(0) &+& 144(0) &+& 120(1) &+& 75(0) \
75 &= 160(0) &+& 144(0) &+& 120(0) &+& 75(1) \
end{array}
This can be abstracted into the following partitioned array
begin{array}{r|rrrr}
160 & 1 & 0 & 0 & 0 \
144 & 0 & 1 & 0 & 0 \
120 & 0 & 0 & 1 & 0 \
75 & 0 & 0 & 0 & 1 \
end{array}
The important thing to remember is that, at any time, a row $fbox{n | d c b a}$ represents the equality $n = 160d + 144c + 120b + 75a$.
The "outer loop" of this algorithm assumes that the left column is in descending order.
The first step is to reduce the three upper rows so that the entries in the first column are all less than the bottom left number, $75$. For the first row, we know that
$160 = 2 times 75 + 10$ so we replace row $1$ ($R1$) with $R1 - 2R4$, getting $fbox{10 | 1 0 0 -2}$. Negative remainders are allowed if their absolute value is less than the positive remainder. So since $144 = 75(2)-6$, we replace the second row with $R2 - 2R4$, getting $fbox{-6 | 0 1 0 -2}$. Similarly the third row becomes $R3 - 24$, which is $fbox{-30 | 0 0 1 -2}$. So we now have
begin{array}{r|rrrr}
10 & 1 & 0 & 0 & -2 \
-6 & 0 & 1 & 0 & -2 \
-30 & 0 & 0 & 1 & -2 \
75 & 0 & 0 & 0 & 1 \
end{array}
Next, we make the substitution $Rk to -Rk$ for any row with a negative first element and we then sort the array in decreasing order of the first element. We end up with
begin{array}{r|rrrr}
75 & 0 & 0 & 0 & 1 \
30 & 0 & 0 & -1 & 2 \
10 & 1 & 0 & 0 & -2 \
6 & 0 & -1 & 0 & 2 \
end{array}
After the next pass through the loop, we get
begin{array}{r|rrrr}
3 & 0 & 12 & 0 & -23 \
0 & 0 & 5 & -1 & -8 \
-2 & 1 & 2 & 0 & -6 \
6 & 0 & -1 & 0 & 2 \
end{array}
which "sorts" to
begin{array}{r|rrrr}
6 & 0 & -1 & 0 & 2 \
3 & 0 & 12 & 0 & -23 \
2 & -1 & -2 & 0 & 6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The next outer loop will proceed as before except that we will make our adjustments with respect to the third row instead of the fourth row. we finally end up with
begin{array}{r|rrrr}
1 & 1 & 14 & 0 & -29 \
0 & -3 & -30 & 0 & 64 \
0 & 3 & 5 & 0 & -6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The tells is that the general solution is (if I haven't messed up my math)
$(d,c,b,a) = (1, 14 , 0 , -29) + u(-3, -30, 0, 64) + v(3, 5, 0, -6) + w(0, 5, -1, -8)$
answered yesterday
steven gregory
17.4k22156
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
add a comment |
up vote
1
down vote
up vote
1
down vote
Here is a description of a program that I wrote to solve such problems. It is definitely not optimized.
I start by considering the equalities
begin{array}{r}
160 &= 160(1) &+& 144(0) &+& 120(0) &+& 75(0) \
144 &= 160(0) &+& 144(1) &+& 120(0) &+& 75(0) \
120 &= 160(0) &+& 144(0) &+& 120(1) &+& 75(0) \
75 &= 160(0) &+& 144(0) &+& 120(0) &+& 75(1) \
end{array}
This can be abstracted into the following partitioned array
begin{array}{r|rrrr}
160 & 1 & 0 & 0 & 0 \
144 & 0 & 1 & 0 & 0 \
120 & 0 & 0 & 1 & 0 \
75 & 0 & 0 & 0 & 1 \
end{array}
The important thing to remember is that, at any time, a row $fbox{n | d c b a}$ represents the equality $n = 160d + 144c + 120b + 75a$.
The "outer loop" of this algorithm assumes that the left column is in descending order.
The first step is to reduce the three upper rows so that the entries in the first column are all less than the bottom left number, $75$. For the first row, we know that
$160 = 2 times 75 + 10$ so we replace row $1$ ($R1$) with $R1 - 2R4$, getting $fbox{10 | 1 0 0 -2}$. Negative remainders are allowed if their absolute value is less than the positive remainder. So since $144 = 75(2)-6$, we replace the second row with $R2 - 2R4$, getting $fbox{-6 | 0 1 0 -2}$. Similarly the third row becomes $R3 - 24$, which is $fbox{-30 | 0 0 1 -2}$. So we now have
begin{array}{r|rrrr}
10 & 1 & 0 & 0 & -2 \
-6 & 0 & 1 & 0 & -2 \
-30 & 0 & 0 & 1 & -2 \
75 & 0 & 0 & 0 & 1 \
end{array}
Next, we make the substitution $Rk to -Rk$ for any row with a negative first element and we then sort the array in decreasing order of the first element. We end up with
begin{array}{r|rrrr}
75 & 0 & 0 & 0 & 1 \
30 & 0 & 0 & -1 & 2 \
10 & 1 & 0 & 0 & -2 \
6 & 0 & -1 & 0 & 2 \
end{array}
After the next pass through the loop, we get
begin{array}{r|rrrr}
3 & 0 & 12 & 0 & -23 \
0 & 0 & 5 & -1 & -8 \
-2 & 1 & 2 & 0 & -6 \
6 & 0 & -1 & 0 & 2 \
end{array}
which "sorts" to
begin{array}{r|rrrr}
6 & 0 & -1 & 0 & 2 \
3 & 0 & 12 & 0 & -23 \
2 & -1 & -2 & 0 & 6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The next outer loop will proceed as before except that we will make our adjustments with respect to the third row instead of the fourth row. we finally end up with
begin{array}{r|rrrr}
1 & 1 & 14 & 0 & -29 \
0 & -3 & -30 & 0 & 64 \
0 & 3 & 5 & 0 & -6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The tells is that the general solution is (if I haven't messed up my math)
$(d,c,b,a) = (1, 14 , 0 , -29) + u(-3, -30, 0, 64) + v(3, 5, 0, -6) + w(0, 5, -1, -8)$
answered yesterday
steven gregory
17.4k22156
Here is a description of a program that I wrote to solve such problems. It is definitely not optimized.
I start by considering the equalities
begin{array}{r}
160 &= 160(1) &+& 144(0) &+& 120(0) &+& 75(0) \
144 &= 160(0) &+& 144(1) &+& 120(0) &+& 75(0) \
120 &= 160(0) &+& 144(0) &+& 120(1) &+& 75(0) \
75 &= 160(0) &+& 144(0) &+& 120(0) &+& 75(1) \
end{array}
This can be abstracted into the following partitioned array
begin{array}{r|rrrr}
160 & 1 & 0 & 0 & 0 \
144 & 0 & 1 & 0 & 0 \
120 & 0 & 0 & 1 & 0 \
75 & 0 & 0 & 0 & 1 \
end{array}
The important thing to remember is that, at any time, a row $fbox{n | d c b a}$ represents the equality $n = 160d + 144c + 120b + 75a$.
The "outer loop" of this algorithm assumes that the left column is in descending order.
The first step is to reduce the three upper rows so that the entries in the first column are all less than the bottom left number, $75$. For the first row, we know that
$160 = 2 times 75 + 10$ so we replace row $1$ ($R1$) with $R1 - 2R4$, getting $fbox{10 | 1 0 0 -2}$. Negative remainders are allowed if their absolute value is less than the positive remainder. So since $144 = 75(2)-6$, we replace the second row with $R2 - 2R4$, getting $fbox{-6 | 0 1 0 -2}$. Similarly the third row becomes $R3 - 24$, which is $fbox{-30 | 0 0 1 -2}$. So we now have
begin{array}{r|rrrr}
10 & 1 & 0 & 0 & -2 \
-6 & 0 & 1 & 0 & -2 \
-30 & 0 & 0 & 1 & -2 \
75 & 0 & 0 & 0 & 1 \
end{array}
Next, we make the substitution $Rk to -Rk$ for any row with a negative first element and we then sort the array in decreasing order of the first element. We end up with
begin{array}{r|rrrr}
75 & 0 & 0 & 0 & 1 \
30 & 0 & 0 & -1 & 2 \
10 & 1 & 0 & 0 & -2 \
6 & 0 & -1 & 0 & 2 \
end{array}
After the next pass through the loop, we get
begin{array}{r|rrrr}
3 & 0 & 12 & 0 & -23 \
0 & 0 & 5 & -1 & -8 \
-2 & 1 & 2 & 0 & -6 \
6 & 0 & -1 & 0 & 2 \
end{array}
which "sorts" to
begin{array}{r|rrrr}
6 & 0 & -1 & 0 & 2 \
3 & 0 & 12 & 0 & -23 \
2 & -1 & -2 & 0 & 6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The next outer loop will proceed as before except that we will make our adjustments with respect to the third row instead of the fourth row. we finally end up with
begin{array}{r|rrrr}
1 & 1 & 14 & 0 & -29 \
0 & -3 & -30 & 0 & 64 \
0 & 3 & 5 & 0 & -6 \
0 & 0 & 5 & -1 & -8 \
end{array}
The tells is that the general solution is (if I haven't messed up my math)
$(d,c,b,a) = (1, 14 , 0 , -29) + u(-3, -30, 0, 64) + v(3, 5, 0, -6) + w(0, 5, -1, -8)$
answered yesterday
steven gregory
17.4k22156
answered yesterday
steven gregory
17.4k22156
answered yesterday
steven gregory
17.4k22156
answered yesterday
steven gregory
17.4k22156
17.4k22156
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
add a comment |
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
1
1
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
– Bill Dubuque
yesterday
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005591%2fuse-the-euclidean-algorithm-to-find-a-b-c-d-such-that-225a-360b-432c-4%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
2 days ago
1
I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
2 days ago
1
You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
2 days ago
1
$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
2 days ago
4
@YvesDaoust No, because no two of the coefficients are relatively prime. For example, if I choose $a=b=0$ (for simplicity), then I'm left with $144c+160d=1$, which has no integer solutions because the left side is divisible by $16$ for any integers $c$ and $d$.
– Andreas Blass
2 days ago