Use the Euclidean Algorithm to find $a, b, c, d$ such that $225a + 360b +432c +480d = 3$











up vote
10
down vote

favorite
2












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.










share|cite|improve this question




















  • 1




    you could cancel 3 from both sides, will definitely make it simpler
    – gt6989b
    Nov 19 at 22:04






  • 1




    I would take a look at this SE post for a similar problem with 3 variables.
    – Jack Moody
    Nov 19 at 22:05






  • 1




    You can choose two unknowns arbitrarily and solve for the two remaining ones.
    – Yves Daoust
    Nov 19 at 22:06






  • 1




    $a = 3, b = 0, c = 4, d = -5$
    – David G. Stork
    Nov 19 at 22:36






  • 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
    Nov 20 at 3:03















up vote
10
down vote

favorite
2












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.










share|cite|improve this question




















  • 1




    you could cancel 3 from both sides, will definitely make it simpler
    – gt6989b
    Nov 19 at 22:04






  • 1




    I would take a look at this SE post for a similar problem with 3 variables.
    – Jack Moody
    Nov 19 at 22:05






  • 1




    You can choose two unknowns arbitrarily and solve for the two remaining ones.
    – Yves Daoust
    Nov 19 at 22:06






  • 1




    $a = 3, b = 0, c = 4, d = -5$
    – David G. Stork
    Nov 19 at 22:36






  • 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
    Nov 20 at 3:03













up vote
10
down vote

favorite
2









up vote
10
down vote

favorite
2






2





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.










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 20 at 15:47









Xander Henderson

14k103552




14k103552










asked Nov 19 at 22:03









Joe Goldiamond

575216




575216








  • 1




    you could cancel 3 from both sides, will definitely make it simpler
    – gt6989b
    Nov 19 at 22:04






  • 1




    I would take a look at this SE post for a similar problem with 3 variables.
    – Jack Moody
    Nov 19 at 22:05






  • 1




    You can choose two unknowns arbitrarily and solve for the two remaining ones.
    – Yves Daoust
    Nov 19 at 22:06






  • 1




    $a = 3, b = 0, c = 4, d = -5$
    – David G. Stork
    Nov 19 at 22:36






  • 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
    Nov 20 at 3:03














  • 1




    you could cancel 3 from both sides, will definitely make it simpler
    – gt6989b
    Nov 19 at 22:04






  • 1




    I would take a look at this SE post for a similar problem with 3 variables.
    – Jack Moody
    Nov 19 at 22:05






  • 1




    You can choose two unknowns arbitrarily and solve for the two remaining ones.
    – Yves Daoust
    Nov 19 at 22:06






  • 1




    $a = 3, b = 0, c = 4, d = -5$
    – David G. Stork
    Nov 19 at 22:36






  • 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
    Nov 20 at 3:03








1




1




you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
Nov 19 at 22:04




you could cancel 3 from both sides, will definitely make it simpler
– gt6989b
Nov 19 at 22:04




1




1




I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
Nov 19 at 22:05




I would take a look at this SE post for a similar problem with 3 variables.
– Jack Moody
Nov 19 at 22:05




1




1




You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
Nov 19 at 22:06




You can choose two unknowns arbitrarily and solve for the two remaining ones.
– Yves Daoust
Nov 19 at 22:06




1




1




$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
Nov 19 at 22:36




$a = 3, b = 0, c = 4, d = -5$
– David G. Stork
Nov 19 at 22:36




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
Nov 20 at 3:03




@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
Nov 20 at 3:03










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$






share|cite|improve this answer



















  • 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
    Nov 19 at 23:20


















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






share|cite|improve this answer






























    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.






    share|cite|improve this answer

















    • 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
      Nov 19 at 22:41






    • 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
      Nov 19 at 22:50










    • 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
      Nov 19 at 22:53






    • 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
      Nov 19 at 23:18






    • 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
      Nov 20 at 11:33


















    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.






    share|cite|improve this answer

















    • 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
      Nov 20 at 19:00


















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






    share|cite|improve this answer






























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






      share|cite|improve this answer

















      • 1




        This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
        – Bill Dubuque
        Nov 20 at 19:12













      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      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

























      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$






      share|cite|improve this answer



















      • 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
        Nov 19 at 23:20















      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$






      share|cite|improve this answer



















      • 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
        Nov 19 at 23:20













      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$






      share|cite|improve this answer














      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$







      share|cite|improve this answer














      share|cite|improve this answer



      share|cite|improve this answer








      edited Nov 19 at 22:57

























      answered Nov 19 at 22:44









      fleablood

      66.4k22684




      66.4k22684








      • 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
        Nov 19 at 23:20














      • 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
        Nov 19 at 23:20








      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
      Nov 19 at 23:20




      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
      Nov 19 at 23:20










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






      share|cite|improve this answer



























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






        share|cite|improve this answer

























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






          share|cite|improve this answer














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







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Nov 19 at 23:13

























          answered Nov 19 at 22:21









          Will Jagy

          101k597198




          101k597198






















              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.






              share|cite|improve this answer

















              • 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
                Nov 19 at 22:41






              • 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
                Nov 19 at 22:50










              • 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
                Nov 19 at 22:53






              • 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
                Nov 19 at 23:18






              • 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
                Nov 20 at 11:33















              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.






              share|cite|improve this answer

















              • 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
                Nov 19 at 22:41






              • 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
                Nov 19 at 22:50










              • 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
                Nov 19 at 22:53






              • 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
                Nov 19 at 23:18






              • 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
                Nov 20 at 11:33













              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.






              share|cite|improve this answer












              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.







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Nov 19 at 22:23









              Mohammad Riazi-Kermani

              40.3k41958




              40.3k41958








              • 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
                Nov 19 at 22:41






              • 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
                Nov 19 at 22:50










              • 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
                Nov 19 at 22:53






              • 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
                Nov 19 at 23:18






              • 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
                Nov 20 at 11:33














              • 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
                Nov 19 at 22:41






              • 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
                Nov 19 at 22:50










              • 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
                Nov 19 at 22:53






              • 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
                Nov 19 at 23:18






              • 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
                Nov 20 at 11:33








              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
              Nov 19 at 22:41




              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
              Nov 19 at 22:41




              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
              Nov 19 at 22:50




              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
              Nov 19 at 22:50












              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
              Nov 19 at 22:53




              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
              Nov 19 at 22:53




              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
              Nov 19 at 23:18




              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
              Nov 19 at 23:18




              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
              Nov 20 at 11:33




              @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
              Nov 20 at 11:33










              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.






              share|cite|improve this answer

















              • 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
                Nov 20 at 19:00















              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.






              share|cite|improve this answer

















              • 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
                Nov 20 at 19:00













              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.






              share|cite|improve this answer












              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.







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Nov 20 at 11:17









              user21820

              38.1k541150




              38.1k541150








              • 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
                Nov 20 at 19:00














              • 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
                Nov 20 at 19:00








              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
              Nov 20 at 19:00




              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
              Nov 20 at 19:00










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






              share|cite|improve this answer



























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






                share|cite|improve this answer

























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






                  share|cite|improve this answer














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







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Nov 20 at 19:03

























                  answered Nov 19 at 23:29









                  Bill Dubuque

                  207k29189624




                  207k29189624






















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






                      share|cite|improve this answer

















                      • 1




                        This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                        – Bill Dubuque
                        Nov 20 at 19:12

















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






                      share|cite|improve this answer

















                      • 1




                        This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                        – Bill Dubuque
                        Nov 20 at 19:12















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






                      share|cite|improve this answer












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







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Nov 20 at 16:19









                      steven gregory

                      17.6k22257




                      17.6k22257








                      • 1




                        This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                        – Bill Dubuque
                        Nov 20 at 19:12
















                      • 1




                        This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                        – Bill Dubuque
                        Nov 20 at 19:12










                      1




                      1




                      This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                      – Bill Dubuque
                      Nov 20 at 19:12






                      This is the standard Extended Euclidean Algorithm in augmented matrix form - see the Remark in my answer.
                      – Bill Dubuque
                      Nov 20 at 19:12




















                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Plaza Victoria

                      Puebla de Zaragoza

                      Musa