Number of integer solutions to Ax + By + Cz = D












0














How many integer solutions exits for the equations, $Ax + By + Cz = D$, where



$B = (A + 1), C = (A + 2)$, and $x, y, z$ are non-negative i.e $x, y, z, >= 0$



I require a general solution which can be implemented using code as well. We would be given the values of $A, D$.










share|cite|improve this question






















  • What are A, B, C and D? Matrices?
    – Dhanvi Sreenivasan
    Nov 6 '16 at 7:20










  • No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
    – caretaker
    Nov 6 '16 at 7:27
















0














How many integer solutions exits for the equations, $Ax + By + Cz = D$, where



$B = (A + 1), C = (A + 2)$, and $x, y, z$ are non-negative i.e $x, y, z, >= 0$



I require a general solution which can be implemented using code as well. We would be given the values of $A, D$.










share|cite|improve this question






















  • What are A, B, C and D? Matrices?
    – Dhanvi Sreenivasan
    Nov 6 '16 at 7:20










  • No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
    – caretaker
    Nov 6 '16 at 7:27














0












0








0


2





How many integer solutions exits for the equations, $Ax + By + Cz = D$, where



$B = (A + 1), C = (A + 2)$, and $x, y, z$ are non-negative i.e $x, y, z, >= 0$



I require a general solution which can be implemented using code as well. We would be given the values of $A, D$.










share|cite|improve this question













How many integer solutions exits for the equations, $Ax + By + Cz = D$, where



$B = (A + 1), C = (A + 2)$, and $x, y, z$ are non-negative i.e $x, y, z, >= 0$



I require a general solution which can be implemented using code as well. We would be given the values of $A, D$.







combinatorics






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 6 '16 at 7:16









caretakercaretaker

245




245












  • What are A, B, C and D? Matrices?
    – Dhanvi Sreenivasan
    Nov 6 '16 at 7:20










  • No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
    – caretaker
    Nov 6 '16 at 7:27


















  • What are A, B, C and D? Matrices?
    – Dhanvi Sreenivasan
    Nov 6 '16 at 7:20










  • No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
    – caretaker
    Nov 6 '16 at 7:27
















What are A, B, C and D? Matrices?
– Dhanvi Sreenivasan
Nov 6 '16 at 7:20




What are A, B, C and D? Matrices?
– Dhanvi Sreenivasan
Nov 6 '16 at 7:20












No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
– caretaker
Nov 6 '16 at 7:27




No, A, D are simply numbers, for eg: number of non - negative integer solutions to $3x + 4y + 5z = 12$
– caretaker
Nov 6 '16 at 7:27










2 Answers
2






active

oldest

votes


















0














First note that $gcd(A, A + 1, A + 2) = 1 $. Since this gcd while divide $D$ this Diophantine equation will always have solutions. So first solve $Au + (A+1)v = gcd(A, A+1) = 1$. Then solve $(1)w + (A+2)s = gcd(1,A+2) = 1$. After finding the integer solutions(values of $u,v,w$ and $s$) using the Extended Euclidean Algorithm we then have
begin{align}
w + (A +2)s &= 1\
(Au + (A+1)v)w + (A+2)s &= 1\
A(uw) + (A+1)(vw) + (A+2)s &= 1\
A(Duw) + (A+1)(Dvw) + (A +2)(Ds) &= D
end{align}
Thus we have our solutions $x = Duw$, $y = Dvw$ and $z = Ds$.






share|cite|improve this answer





























    0














    So, assuming that $A,, D$ are non negative integers
    $$
    left{ matrix{
    0 le x,y,z,A,D; in mathbb Z hfill cr
    Ax + left( {A + 1} right)y + left( {A + 2} right)z = D hfill cr} right.
    $$

    when $A=0$ we are left with $y+2z=D$ and it is easy to see that the number of solutions is
    $$
    N_{A = 0} = 1 + leftlfloor {{D over 2}} rightrfloor = leftlceil {{{D + 1} over 2}} rightrceil
    $$



    Taking then $1 le A$, we can write
    $$
    left{ matrix{
    0 le x,y,k,A,D hfill cr
    Ax + left( {A + 1} right)y = D - left( {A + 2} right)k hfill cr} right.
    $$

    and since $gcd left( {A,A + 1} right) = 1$ we can apply to the Popoviciu's Theorem which reads
    $$ bbox[lightyellow] {
    eqalign{
    & p_{left{ {a,b} right}} (n) = left| {,left{ matrix{
    0 le x,y,a,b,n in Z hfill cr
    gcd (a,b) = 1 hfill cr
    ax + by = n hfill cr} right.;} right| = cr
    & = {n over {ab}} - left{ {{{b^{,left( { - 1} right)} n} over a}} right} - left{ {{{a^{,left( { - 1} right)} n} over b}} right} + 1 cr}
    } tag{1}$$

    where:
    $left{ x right} $ denotes the fractional part : $left{ x right} = x - leftlfloor x rightrfloor $

    and the exponent in brackets denotes the modular inverse
    $$
    b^{,left( { - 1} right)} b equiv 1;left( {bmod a} right)quad a^{,left( { - 1} right)} a equiv 1;left( {bmod b} right)
    $$



    In this respect we have
    $$
    eqalign{
    & A^{,left( { - 1} right)} A equiv 1;left( {bmod A + 1} right)quad Rightarrow quad A^{,left( { - 1} right)} = A cr
    & left( {A + 1} right)^{,left( { - 1} right)} left( {A + 1} right) equiv 1;left( {bmod A} right)quad Rightarrow
    quad left( {A + 1} right)^{,left( { - 1} right)} = 1 cr}
    $$



    Therefore the Popoviciu's theorem gives
    $$
    N_{,1 le A} = sumlimits_{k = 0}^{leftlfloor {D/left( {A + 2} right)} rightrfloor } {,left( {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}}
    - left{ {{{D - left( {A + 2} right)k} over A}} right} - left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} + 1} right)}
    $$



    The terms above can be simplified to some extent. Let's put
    $$d=leftlfloor {D/left( {A + 2} right)} rightrfloor $$



    Then
    $$
    eqalign{
    & sumlimits_{k = 0}^d {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}} + 1}
    = {{D + Aleft( {A + 1} right)} over {Aleft( {A + 1} right)}}left( {d + 1} right) - {{left( {A + 2} right)} over {Aleft( {A + 1} right)}}{{left( {d + 1} right)d} over 2} = cr
    & = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) cr}
    $$

    and
    $$
    eqalign{
    & left{ {{{D - left( {A + 2} right)k} over A}} right} + left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} = cr
    & = left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right} cr}
    $$



    Finally we obtain
    $$ bbox[lightyellow] {
    eqalign{
    & N_{,1 le A} = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) + cr
    & - sumlimits_{k = 0}^d {left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right}} cr}
    } tag{2}$$






    share|cite|improve this answer





















      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',
      autoActivateHeartbeat: false,
      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%2f2001624%2fnumber-of-integer-solutions-to-ax-by-cz-d%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      0














      First note that $gcd(A, A + 1, A + 2) = 1 $. Since this gcd while divide $D$ this Diophantine equation will always have solutions. So first solve $Au + (A+1)v = gcd(A, A+1) = 1$. Then solve $(1)w + (A+2)s = gcd(1,A+2) = 1$. After finding the integer solutions(values of $u,v,w$ and $s$) using the Extended Euclidean Algorithm we then have
      begin{align}
      w + (A +2)s &= 1\
      (Au + (A+1)v)w + (A+2)s &= 1\
      A(uw) + (A+1)(vw) + (A+2)s &= 1\
      A(Duw) + (A+1)(Dvw) + (A +2)(Ds) &= D
      end{align}
      Thus we have our solutions $x = Duw$, $y = Dvw$ and $z = Ds$.






      share|cite|improve this answer


























        0














        First note that $gcd(A, A + 1, A + 2) = 1 $. Since this gcd while divide $D$ this Diophantine equation will always have solutions. So first solve $Au + (A+1)v = gcd(A, A+1) = 1$. Then solve $(1)w + (A+2)s = gcd(1,A+2) = 1$. After finding the integer solutions(values of $u,v,w$ and $s$) using the Extended Euclidean Algorithm we then have
        begin{align}
        w + (A +2)s &= 1\
        (Au + (A+1)v)w + (A+2)s &= 1\
        A(uw) + (A+1)(vw) + (A+2)s &= 1\
        A(Duw) + (A+1)(Dvw) + (A +2)(Ds) &= D
        end{align}
        Thus we have our solutions $x = Duw$, $y = Dvw$ and $z = Ds$.






        share|cite|improve this answer
























          0












          0








          0






          First note that $gcd(A, A + 1, A + 2) = 1 $. Since this gcd while divide $D$ this Diophantine equation will always have solutions. So first solve $Au + (A+1)v = gcd(A, A+1) = 1$. Then solve $(1)w + (A+2)s = gcd(1,A+2) = 1$. After finding the integer solutions(values of $u,v,w$ and $s$) using the Extended Euclidean Algorithm we then have
          begin{align}
          w + (A +2)s &= 1\
          (Au + (A+1)v)w + (A+2)s &= 1\
          A(uw) + (A+1)(vw) + (A+2)s &= 1\
          A(Duw) + (A+1)(Dvw) + (A +2)(Ds) &= D
          end{align}
          Thus we have our solutions $x = Duw$, $y = Dvw$ and $z = Ds$.






          share|cite|improve this answer












          First note that $gcd(A, A + 1, A + 2) = 1 $. Since this gcd while divide $D$ this Diophantine equation will always have solutions. So first solve $Au + (A+1)v = gcd(A, A+1) = 1$. Then solve $(1)w + (A+2)s = gcd(1,A+2) = 1$. After finding the integer solutions(values of $u,v,w$ and $s$) using the Extended Euclidean Algorithm we then have
          begin{align}
          w + (A +2)s &= 1\
          (Au + (A+1)v)w + (A+2)s &= 1\
          A(uw) + (A+1)(vw) + (A+2)s &= 1\
          A(Duw) + (A+1)(Dvw) + (A +2)(Ds) &= D
          end{align}
          Thus we have our solutions $x = Duw$, $y = Dvw$ and $z = Ds$.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Nov 6 '16 at 8:38









          Jeevan DevaranjanJeevan Devaranjan

          2,227516




          2,227516























              0














              So, assuming that $A,, D$ are non negative integers
              $$
              left{ matrix{
              0 le x,y,z,A,D; in mathbb Z hfill cr
              Ax + left( {A + 1} right)y + left( {A + 2} right)z = D hfill cr} right.
              $$

              when $A=0$ we are left with $y+2z=D$ and it is easy to see that the number of solutions is
              $$
              N_{A = 0} = 1 + leftlfloor {{D over 2}} rightrfloor = leftlceil {{{D + 1} over 2}} rightrceil
              $$



              Taking then $1 le A$, we can write
              $$
              left{ matrix{
              0 le x,y,k,A,D hfill cr
              Ax + left( {A + 1} right)y = D - left( {A + 2} right)k hfill cr} right.
              $$

              and since $gcd left( {A,A + 1} right) = 1$ we can apply to the Popoviciu's Theorem which reads
              $$ bbox[lightyellow] {
              eqalign{
              & p_{left{ {a,b} right}} (n) = left| {,left{ matrix{
              0 le x,y,a,b,n in Z hfill cr
              gcd (a,b) = 1 hfill cr
              ax + by = n hfill cr} right.;} right| = cr
              & = {n over {ab}} - left{ {{{b^{,left( { - 1} right)} n} over a}} right} - left{ {{{a^{,left( { - 1} right)} n} over b}} right} + 1 cr}
              } tag{1}$$

              where:
              $left{ x right} $ denotes the fractional part : $left{ x right} = x - leftlfloor x rightrfloor $

              and the exponent in brackets denotes the modular inverse
              $$
              b^{,left( { - 1} right)} b equiv 1;left( {bmod a} right)quad a^{,left( { - 1} right)} a equiv 1;left( {bmod b} right)
              $$



              In this respect we have
              $$
              eqalign{
              & A^{,left( { - 1} right)} A equiv 1;left( {bmod A + 1} right)quad Rightarrow quad A^{,left( { - 1} right)} = A cr
              & left( {A + 1} right)^{,left( { - 1} right)} left( {A + 1} right) equiv 1;left( {bmod A} right)quad Rightarrow
              quad left( {A + 1} right)^{,left( { - 1} right)} = 1 cr}
              $$



              Therefore the Popoviciu's theorem gives
              $$
              N_{,1 le A} = sumlimits_{k = 0}^{leftlfloor {D/left( {A + 2} right)} rightrfloor } {,left( {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}}
              - left{ {{{D - left( {A + 2} right)k} over A}} right} - left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} + 1} right)}
              $$



              The terms above can be simplified to some extent. Let's put
              $$d=leftlfloor {D/left( {A + 2} right)} rightrfloor $$



              Then
              $$
              eqalign{
              & sumlimits_{k = 0}^d {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}} + 1}
              = {{D + Aleft( {A + 1} right)} over {Aleft( {A + 1} right)}}left( {d + 1} right) - {{left( {A + 2} right)} over {Aleft( {A + 1} right)}}{{left( {d + 1} right)d} over 2} = cr
              & = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) cr}
              $$

              and
              $$
              eqalign{
              & left{ {{{D - left( {A + 2} right)k} over A}} right} + left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} = cr
              & = left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right} cr}
              $$



              Finally we obtain
              $$ bbox[lightyellow] {
              eqalign{
              & N_{,1 le A} = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) + cr
              & - sumlimits_{k = 0}^d {left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right}} cr}
              } tag{2}$$






              share|cite|improve this answer


























                0














                So, assuming that $A,, D$ are non negative integers
                $$
                left{ matrix{
                0 le x,y,z,A,D; in mathbb Z hfill cr
                Ax + left( {A + 1} right)y + left( {A + 2} right)z = D hfill cr} right.
                $$

                when $A=0$ we are left with $y+2z=D$ and it is easy to see that the number of solutions is
                $$
                N_{A = 0} = 1 + leftlfloor {{D over 2}} rightrfloor = leftlceil {{{D + 1} over 2}} rightrceil
                $$



                Taking then $1 le A$, we can write
                $$
                left{ matrix{
                0 le x,y,k,A,D hfill cr
                Ax + left( {A + 1} right)y = D - left( {A + 2} right)k hfill cr} right.
                $$

                and since $gcd left( {A,A + 1} right) = 1$ we can apply to the Popoviciu's Theorem which reads
                $$ bbox[lightyellow] {
                eqalign{
                & p_{left{ {a,b} right}} (n) = left| {,left{ matrix{
                0 le x,y,a,b,n in Z hfill cr
                gcd (a,b) = 1 hfill cr
                ax + by = n hfill cr} right.;} right| = cr
                & = {n over {ab}} - left{ {{{b^{,left( { - 1} right)} n} over a}} right} - left{ {{{a^{,left( { - 1} right)} n} over b}} right} + 1 cr}
                } tag{1}$$

                where:
                $left{ x right} $ denotes the fractional part : $left{ x right} = x - leftlfloor x rightrfloor $

                and the exponent in brackets denotes the modular inverse
                $$
                b^{,left( { - 1} right)} b equiv 1;left( {bmod a} right)quad a^{,left( { - 1} right)} a equiv 1;left( {bmod b} right)
                $$



                In this respect we have
                $$
                eqalign{
                & A^{,left( { - 1} right)} A equiv 1;left( {bmod A + 1} right)quad Rightarrow quad A^{,left( { - 1} right)} = A cr
                & left( {A + 1} right)^{,left( { - 1} right)} left( {A + 1} right) equiv 1;left( {bmod A} right)quad Rightarrow
                quad left( {A + 1} right)^{,left( { - 1} right)} = 1 cr}
                $$



                Therefore the Popoviciu's theorem gives
                $$
                N_{,1 le A} = sumlimits_{k = 0}^{leftlfloor {D/left( {A + 2} right)} rightrfloor } {,left( {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}}
                - left{ {{{D - left( {A + 2} right)k} over A}} right} - left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} + 1} right)}
                $$



                The terms above can be simplified to some extent. Let's put
                $$d=leftlfloor {D/left( {A + 2} right)} rightrfloor $$



                Then
                $$
                eqalign{
                & sumlimits_{k = 0}^d {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}} + 1}
                = {{D + Aleft( {A + 1} right)} over {Aleft( {A + 1} right)}}left( {d + 1} right) - {{left( {A + 2} right)} over {Aleft( {A + 1} right)}}{{left( {d + 1} right)d} over 2} = cr
                & = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) cr}
                $$

                and
                $$
                eqalign{
                & left{ {{{D - left( {A + 2} right)k} over A}} right} + left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} = cr
                & = left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right} cr}
                $$



                Finally we obtain
                $$ bbox[lightyellow] {
                eqalign{
                & N_{,1 le A} = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) + cr
                & - sumlimits_{k = 0}^d {left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right}} cr}
                } tag{2}$$






                share|cite|improve this answer
























                  0












                  0








                  0






                  So, assuming that $A,, D$ are non negative integers
                  $$
                  left{ matrix{
                  0 le x,y,z,A,D; in mathbb Z hfill cr
                  Ax + left( {A + 1} right)y + left( {A + 2} right)z = D hfill cr} right.
                  $$

                  when $A=0$ we are left with $y+2z=D$ and it is easy to see that the number of solutions is
                  $$
                  N_{A = 0} = 1 + leftlfloor {{D over 2}} rightrfloor = leftlceil {{{D + 1} over 2}} rightrceil
                  $$



                  Taking then $1 le A$, we can write
                  $$
                  left{ matrix{
                  0 le x,y,k,A,D hfill cr
                  Ax + left( {A + 1} right)y = D - left( {A + 2} right)k hfill cr} right.
                  $$

                  and since $gcd left( {A,A + 1} right) = 1$ we can apply to the Popoviciu's Theorem which reads
                  $$ bbox[lightyellow] {
                  eqalign{
                  & p_{left{ {a,b} right}} (n) = left| {,left{ matrix{
                  0 le x,y,a,b,n in Z hfill cr
                  gcd (a,b) = 1 hfill cr
                  ax + by = n hfill cr} right.;} right| = cr
                  & = {n over {ab}} - left{ {{{b^{,left( { - 1} right)} n} over a}} right} - left{ {{{a^{,left( { - 1} right)} n} over b}} right} + 1 cr}
                  } tag{1}$$

                  where:
                  $left{ x right} $ denotes the fractional part : $left{ x right} = x - leftlfloor x rightrfloor $

                  and the exponent in brackets denotes the modular inverse
                  $$
                  b^{,left( { - 1} right)} b equiv 1;left( {bmod a} right)quad a^{,left( { - 1} right)} a equiv 1;left( {bmod b} right)
                  $$



                  In this respect we have
                  $$
                  eqalign{
                  & A^{,left( { - 1} right)} A equiv 1;left( {bmod A + 1} right)quad Rightarrow quad A^{,left( { - 1} right)} = A cr
                  & left( {A + 1} right)^{,left( { - 1} right)} left( {A + 1} right) equiv 1;left( {bmod A} right)quad Rightarrow
                  quad left( {A + 1} right)^{,left( { - 1} right)} = 1 cr}
                  $$



                  Therefore the Popoviciu's theorem gives
                  $$
                  N_{,1 le A} = sumlimits_{k = 0}^{leftlfloor {D/left( {A + 2} right)} rightrfloor } {,left( {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}}
                  - left{ {{{D - left( {A + 2} right)k} over A}} right} - left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} + 1} right)}
                  $$



                  The terms above can be simplified to some extent. Let's put
                  $$d=leftlfloor {D/left( {A + 2} right)} rightrfloor $$



                  Then
                  $$
                  eqalign{
                  & sumlimits_{k = 0}^d {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}} + 1}
                  = {{D + Aleft( {A + 1} right)} over {Aleft( {A + 1} right)}}left( {d + 1} right) - {{left( {A + 2} right)} over {Aleft( {A + 1} right)}}{{left( {d + 1} right)d} over 2} = cr
                  & = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) cr}
                  $$

                  and
                  $$
                  eqalign{
                  & left{ {{{D - left( {A + 2} right)k} over A}} right} + left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} = cr
                  & = left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right} cr}
                  $$



                  Finally we obtain
                  $$ bbox[lightyellow] {
                  eqalign{
                  & N_{,1 le A} = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) + cr
                  & - sumlimits_{k = 0}^d {left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right}} cr}
                  } tag{2}$$






                  share|cite|improve this answer












                  So, assuming that $A,, D$ are non negative integers
                  $$
                  left{ matrix{
                  0 le x,y,z,A,D; in mathbb Z hfill cr
                  Ax + left( {A + 1} right)y + left( {A + 2} right)z = D hfill cr} right.
                  $$

                  when $A=0$ we are left with $y+2z=D$ and it is easy to see that the number of solutions is
                  $$
                  N_{A = 0} = 1 + leftlfloor {{D over 2}} rightrfloor = leftlceil {{{D + 1} over 2}} rightrceil
                  $$



                  Taking then $1 le A$, we can write
                  $$
                  left{ matrix{
                  0 le x,y,k,A,D hfill cr
                  Ax + left( {A + 1} right)y = D - left( {A + 2} right)k hfill cr} right.
                  $$

                  and since $gcd left( {A,A + 1} right) = 1$ we can apply to the Popoviciu's Theorem which reads
                  $$ bbox[lightyellow] {
                  eqalign{
                  & p_{left{ {a,b} right}} (n) = left| {,left{ matrix{
                  0 le x,y,a,b,n in Z hfill cr
                  gcd (a,b) = 1 hfill cr
                  ax + by = n hfill cr} right.;} right| = cr
                  & = {n over {ab}} - left{ {{{b^{,left( { - 1} right)} n} over a}} right} - left{ {{{a^{,left( { - 1} right)} n} over b}} right} + 1 cr}
                  } tag{1}$$

                  where:
                  $left{ x right} $ denotes the fractional part : $left{ x right} = x - leftlfloor x rightrfloor $

                  and the exponent in brackets denotes the modular inverse
                  $$
                  b^{,left( { - 1} right)} b equiv 1;left( {bmod a} right)quad a^{,left( { - 1} right)} a equiv 1;left( {bmod b} right)
                  $$



                  In this respect we have
                  $$
                  eqalign{
                  & A^{,left( { - 1} right)} A equiv 1;left( {bmod A + 1} right)quad Rightarrow quad A^{,left( { - 1} right)} = A cr
                  & left( {A + 1} right)^{,left( { - 1} right)} left( {A + 1} right) equiv 1;left( {bmod A} right)quad Rightarrow
                  quad left( {A + 1} right)^{,left( { - 1} right)} = 1 cr}
                  $$



                  Therefore the Popoviciu's theorem gives
                  $$
                  N_{,1 le A} = sumlimits_{k = 0}^{leftlfloor {D/left( {A + 2} right)} rightrfloor } {,left( {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}}
                  - left{ {{{D - left( {A + 2} right)k} over A}} right} - left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} + 1} right)}
                  $$



                  The terms above can be simplified to some extent. Let's put
                  $$d=leftlfloor {D/left( {A + 2} right)} rightrfloor $$



                  Then
                  $$
                  eqalign{
                  & sumlimits_{k = 0}^d {{{D - left( {A + 2} right)k} over {Aleft( {A + 1} right)}} + 1}
                  = {{D + Aleft( {A + 1} right)} over {Aleft( {A + 1} right)}}left( {d + 1} right) - {{left( {A + 2} right)} over {Aleft( {A + 1} right)}}{{left( {d + 1} right)d} over 2} = cr
                  & = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) cr}
                  $$

                  and
                  $$
                  eqalign{
                  & left{ {{{D - left( {A + 2} right)k} over A}} right} + left{ {{{Aleft( {D - left( {A + 2} right)k} right)} over {A + 1}}} right} = cr
                  & = left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right} cr}
                  $$



                  Finally we obtain
                  $$ bbox[lightyellow] {
                  eqalign{
                  & N_{,1 le A} = {{left( {d + 1} right)} over {Aleft( {A + 1} right)}}left( {D - d + Aleft( {A - d/2 + 1} right)} right) + cr
                  & - sumlimits_{k = 0}^d {left{ {{{D - 2k} over A}} right} + left{ {{{Aleft( {D - k} right)} over {A + 1}}} right}} cr}
                  } tag{2}$$







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Oct 26 '18 at 22:00









                  G CabG Cab

                  18k31237




                  18k31237






























                      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%2f2001624%2fnumber-of-integer-solutions-to-ax-by-cz-d%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

                      1300-talet

                      1300-talet

                      Display a custom attribute below product name in the front-end Magento 1.9.3.8