Solve a Linear Diophantine Equation

Solving a linear Diophantine equation means that you need to find solutions for the variables x and y that are integers only. Finding integral solutions is more difficult than a standard solution and requires an ordered pattern of steps. You must first find the greatest common factor of the coefficients in the problem, and then use that result to find a solution. If you can find one integral solution to a linear equation, you can apply a simple pattern to find infinitely many more.

Steps

Setting up the Equation

  1. Write the equation in standard form. A linear equation is one that has no exponents greater than 1 on any variables. To solve a linear equation in this style, you need to begin by writing it in what is called “standard form.” The standard form of a linear equation looks like <math>Ax+By=C</math>, where <math>A, B</math> and <math>C</math> are integers.
    • If the equation is not already in standard form, you need to use the basic rules of algebra to rearrange or combine the terms to create the standard form. For example, if you begin with <math>23x+4y-7x=-3y+15</math>, you can combine similar terms to reduce the equation to <math>16x+7y=15</math>.
  2. Reduce the equation if possible. When the equation is in standard form, check all three terms <math>A, B</math> and <math>C</math>. If there is a common factor in all three terms, then reduce the equation by dividing all terms by that factor. If you reduce evenly across all three terms, then any solution you find for the reduced equation will also be a solution for the original equation.
    • For example, if all three terms are even, you can at least divide by 2, as follows:
      • <math>42x+36y=48</math> (all terms are divisible by 2)
      • <math>21x+18y=24</math> (all terms now are divisible by 3)
      • <math>7x+6y=8</math> (this equation is as reduced as possible)
  3. Check for the impossibility of a solution. In some cases, you may be able to tell immediately if there is no solution to your problem. If you see a common factor on the left side of the equation that is not shared on the right side, then there can be no solution to the problem.
    • For example, if both <math>A</math> and <math>B</math> are even, then the sum of the left side of the equation would have to be even. But if <math>C</math> is odd, then there will be no integer solution to the problem.
      • <math>2x+4y=21</math> will have no integer solution.
      • <math>5x+10y=17</math> can have no integer solution, because the left side of the equation is divisible by 5, but the right side is not.

Using the Euclidean Algorithm

  1. Review the Euclidean algorithm. The Euclidean algorithm is a system of repeated divisions, using the remainder each time as the divisor of a new division. The last divisor that divides evenly is the greatest common factor (GCF) of the two numbers.[1]
    • For example, the following steps illustrate the Euclidean algorithm being used to find the GCF of 272 and 36:
      • <math>272=7*36+20</math>....divide the larger number (272) by the smaller (36) and note the remainder (20)
      • <math>36=1*20+16</math>....divide the previous divisor (36) by the previous remainder (20). Note the new remainder (16).
      • <math>20=1*16+4</math>....Repeat. Divide the previous divisor (20) by the previous remainder (16). Note the new remainder (4).
      • <math>16=4*4+0</math>....Repeat. Divide the previous divisor (16) by the previous remainder (4). Since the remainder is now 0, conclude that 4 is the GCF of the original two numbers 272 and 36.
  2. Apply the Euclidean algorithm to the coefficients A and B. With your linear equation in standard form, identify the coefficients A and B. Apply the Euclidean algorithm to find their GCF. Suppose you need to find integral solutions for the linear equation <math>87x-64y=3</math>.[1]
    • The steps of the Euclidean algorithm for the coefficients 87 and 64 are as follows:
      • <math>87=1*64+23</math>
      • <math>64=2*23+18</math>
      • <math>23=1*18+5</math>
      • <math>18=3*5+3</math>
      • <math>5=1*3+2</math>
      • <math>3=1*2+1</math>
      • <math>2=2*1+0</math>
  3. Identify the greatest common factor (GCF). Because the Euclidean algorithm for this pair continues all the way down to dividing by 1, the GCF between 87 and 64 is 1. This is another way of saying that 87 and 64 are relatively prime.[1]
  4. Interpret the result. When you complete the Euclidean algorithm to find the GCF of <math>A</math> and <math>B</math>, you need to compare that result with the number <math>C</math> of the original equation. If the greatest common factor of <math>A</math> and <math>B</math> is a number that can divide into <math>C</math>, then your linear equation will have an integral solution. If not, then there will be no solution.[1]
    • For example, the sample problem <math>87x-64y=3</math> will have an integral solution, since the GCF of 1 can be evenly divided into 3.
    • Suppose, for example, that the GCF had worked out to be 5. The divisor 5 cannot go evenly into 3. In that case, the equation would have no integral solutions.
    • As you will see below, if an equation has one integral solution, then it also has infinitely many integral solutions.

Renaming the GCF to find the Solution

  1. Label the steps of the GCF reduction. To find the solution of the linear equation, you will use your work on the Euclidean algorithm as the basis for a repeated process of renaming and simplifying values.[2]
    • Begin by numbering the steps of the Euclidean algorithm reduction, as reference points. Thus, you have the following steps:
      • <math>\text{Step 1}: 87=(1*64)+23</math>
      • <math>\text{Step 2}: 64=(2*23)+18</math>
      • <math>\text{Step 3}: 23=(1*18)+5</math>
      • <math>\text{Step 4}: 18=(3*5)+3</math>
      • <math>\text{Step 5}: 5=(1*3)+2</math>
      • <math>\text{Step 6}: 3=(1*2)+1</math>
      • <math>\text{Step 7}: 2=(2*1)+0</math>
  2. Begin with the last step that has a remainder. Rewrite that equation so the remainder stands alone, as equal to the rest of the information in the equation.[2]
    • For this problem, Step 6 is the last one that showed a remainder. That remainder was 1. Rewrite the equation in Step 6 as follows:
      • <math>1=3-(1*2)</math>
  3. Isolate the remainder of the previous step. This procedure is a step-by-step process of moving “up” the steps. Each time, you will be revising the right side of the equation in terms of the numbers in the higher step.[2]
    • You can revise Step 5 to isolate its remainder as:
      • <math>2=5-(1*3)</math> or <math>2=5-3</math>
  4. Perform a substitution and simplify. You should notice that your revision of Step 6 contains the number 2, and your revision of Step 5 is equal to 2. Substitute the equality in Step 5 into the place of the 2 in your Step 6 revision:[2]
    • <math>1=3-(1*2)</math>….. (This is the Step 6 revision.)
    • <math>1=3-(5-3)</math>….. (Substitute in place of the value 2.)
    • <math>1=3-5+3</math>….. (Distribution of the negative sign)
    • <math>1=2(3)-5</math>…..(Simplify)
  5. Repeat the process of substitution and simplification. Moving through the Euclidean algorithm steps in reverse, repeat the process. Each time, you will revise the previous step, and substitute its value into your latest result.[2]
    • The last step was Step 5. Now revise Step 4 to isolate its remainder as:
      • <math>3=18-(3*5)</math>
    • Substitute that value in place of the 3 in your latest simplification step and then simplify:
      • <math>1=2(18-3*5)-5</math>
      • <math>1=2(18)-6(5)-5</math>
      • <math>1=2(18)-7(5)</math>
  6. Continue repeating substitution and simplification. This process will repeat, step by step, until you reach the original step of the Euclidean algorithm. The purpose of this procedure is to wind up with an equation that will be written in terms of 87 and 64, which are the original coefficients of the problem you are trying to solve. Continuing in this manner, the remaining steps are as follows:[2]
    • <math>1=2(18)-7(5)</math>
    • <math>1=2(18)-7(23-18)</math>…..(Substitution from Step 3)
      • <math>1=2(18)-7(23)+7(18)</math>
      • <math>1=9(18)-7(23)</math>
    • <math>1=9(64-2*23)-7(23)</math>…..(Substitution from Step 2)
      • <math>1=9(64)-18(23)-7(23)</math>
      • <math>1=9(64)-25(23)</math>
    • <math>1=9(64)-25(87-64)</math>…..(Substitution from Step 1)
      • <math>1=9(64)-25(87)+25(64)</math>
      • <math>1=34(64)-25(87)</math>
  7. Rewrite the result in terms of the original coefficients. When you return to the first step of the Euclidean algorithm, you should notice that the resulting equation contains the two coefficients of the original problem. Rearrange the numbers so they align with the original equation.[2]
    • In this case, the original problem you are trying to solve is <math>87x-64y=3</math>. Thus, you can rearrange your last step to put the terms in that standard order. Pay particular attention to the 64 term. In the original problem, that term is subtracted, but the Euclidean algorithm treats it as a positive term. To account for the subtraction, you need to change the multiplier 34 to a negative. The final equation looks like this:
      • <math>87(-25)-64(-34)=1</math>
  8. Multiply by the necessary factor to find your solutions. Notice that the greatest common divisor for this problem was 1, so the solution that you reached is equal to 1. However, that is not the solution to the problem, since the original problem sets 87x-64y equal to 3. You need to multiply the terms of your last equation by 3 to get a solution:[2]
    • <math>87(-25*3)-64(-34*3)=1*3</math>
    • <math>87(-75)-64(-102)=3</math>
  9. Identify the integral solution to the equation. The values that must be multiplied by the coefficients are the x and y solutions to the equation.
    • In this case, you can identify the solution as the coordinate pair <math>(x,y)=(-75, -102)</math>.

Finding Infinitely Many More Solutions

  1. Recognize that infinitely many solutions exist. If a linear equation has one integral solution, then it must have infinitely many integral solutions. Here is a brief algebraic statement of the proof:[3]
    • <math>Ax+By=C</math>
    • <math>A(x+B)+B(y-A)=C</math> ….. (Adding a B to x while subtracting A from y results in the same solution.)
  2. Identify your original solution values for x and y. The pattern of infinite solutions begins with the single solution that you identified.[3]
    • In this case, your solution is the coordinate pair <math>(x,y)=(-75, -102)</math>.
  3. Add the y-coefficient B to the x solution. To find a new solution for x, add the value of the coefficient of y.[3]
    • In this problem, beginning with the solution x=-75, add the y coefficient of -64, as follows:
      • <math>x=-75+(-64)=-139</math>
    • Thus, a new solution for the original equation will have the x value of -139.
  4. Subtract the x-coefficient A from the y solution. To make the equation remain balanced, when you add to the x term, you must then subtract from the y term.
    • For this problem, beginning with the solution y=-102, subtract the x coefficient of 87, as follows:
      • <math>y=-102-87=-189</math>
    • Thus, a new solution for the original equation will have the y coordinate of -189.
    • The new ordered pair should be <math>(x,y)=(-139,-189)</math>.
  5. Check the solution. To verify that your new ordered pair is a solution to the equation, insert the values into the equation and see if it works.[3]
    • <math>87x-64y=3</math>
    • <math>87(-139)-64(-189)=3</math>
    • <math>3=3</math>
    • Because the statement is true, the solution works.
  6. Write a general solution. The values for x will fit a pattern of the original solution, plus any multiple of the B coefficient. You can write this algebraically as follows:[3]
    • x(k)=x+k(B), where x(k) represents the series of all x solutions, and x is the original x value that you solved.
      • For this problem, you can say:
      • <math>x(k)=-75-64k</math>
    • y(k)=y-k(A), where y(k) represents the series of all y solutions, and y is the original y value that you solved.
      • For this problem, you can say:
      • <math>y(k)=-102-87k</math>

Related Articles

Sources and Citations

  1. ↑ 1.0 1.1 1.2 1.3 http://mathworld.wolfram.com/EuclideanAlgorithm.html
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
  3. ↑ 3.0 3.1 3.2 3.3 3.4 https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
Retrieved from "https://kipkis.com/index.php?title=Solve_a_Linear_Diophantine_Equation&oldid=302139"