Given a set of linear Diophantine Equations (LDE's), where each equation is one of the following form:Let C be a positive integer constant. Also, the number of variables in each equation is exactly C.1. a i + b i + c i . . . . . = C or2. a i + b i + c i . . . . . = ( C + 1 )For every such set of LDE problem instance, the problem is solvable iff, at least one such solution exists, such that each variable's assigned value in that solution is:1. ≤ C2. ≥ 0In other words, the solution if it exists is bounded by the constant C and 0.Can someone help with the proof of the above statement (or counterexamples with some small C)?

Question

Given a set of linear Diophantine Equations (LDE&#039;s), where each equation is one of the following form:Let   C be a positive integer constant. Also, the number of variables in each equation is exactly   C.1.       a    i    +      b    i    +      c    i    .  .  .  .  .  =  C or2.       a    i    +      b    i    +      c    i    .  .  .  .  .  =  (  C  +  1  )For every such set of LDE problem instance, the problem is solvable iff, at least one such solution exists, such that each variable&#039;s assigned value in that solution is:1.  ≤  C2.   ≥  0In other words, the solution if it exists is bounded by the constant   C and 0.Can someone help with the proof of the above statement (or counterexamples with some small   C)?

sleuteleni7 · Accepted Answer

So, if I understood properly your exposition, the system can be written as      {                                        x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    1                                                              =                      c                                        1                                +                      d                                        1                                                                        x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    2                                                              =                      c                                        2                                +                      d                                        2                                                                                ⋮                                                  x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    n                                                              =                      c                                        n                                +                      d                                        n                                              where       d    k    ∈  {  0  ,  1  }.Clearly we can always rearrange the rows by increasing       c    k  &#039;s      {                                        x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    1                                                              =                      c                                        1                                +                      d                                        1                                                                        x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    1                                                              +          ⋯          +                      x                                                        c                                                    2                                                              =                      c                                        2                                +                      d                                        2                                                                                ⋮                                                  x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    1                                                              +          ⋯          +                      x                                                        c                                                    2                                                              +          ⋯          +          ⋯          +                      x                                                        c                                                    n                  −                  1                                                              +          ⋯          +                      x                                                        c                                                    n                                                              =                      c                                        n                                +                      d                                        n                                              and subtracting from each row the preceding one      {                                        x                                        1                                +                      x                                        2                                +          ⋯          +                      x                                                        c                                                    1                                                              =                      c                                        1                                +                      d                                        1                                                                        x                                                        c                                                    1                                            +              1                                +          ⋯          +                      x                                                        c                                                    2                                                              =                      (                                          c                                                    2                                            −                              c                                                    1                                                      )                    +                      d                                        2                                −                      d                                        1                                                                                ⋮                                                  x                                                        c                                                    n                  −                  1                                            +              1                                +          ⋯          +                      x                                                        c                                                    n                                                              =                      (                                          c                                                    n                                            −                              c                                                    n                  −                  1                                                      )                    +                      d                                        n                                −                      d                                        n              −              1                                              This is not, actually, a set of equations but a collection of   n independent equations, since the variables in each row are different from (i.e. not related to) those in the other rows.Now, an equation of those, of the type      x                1        +      x                2        +  ⋯  +      x                m        =  m  +            d      ^              |                                  d          ^                    =      −      1      ,      0      ,      1          can have solutions in which the various xk are not necessarily limited to the range [0,m].Thus your claim is not justified.

Given a set of linear Diophantine Equations (LDE's), where each equation is one of the following for

Answered question

Answer & Explanation

New Questions in Algebra I