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 23x+4y−7x=−3y+15{\displaystyle 23x+4y-7x=-3y+15}, you can combine similar terms to reduce the equation to 16x+7y=15{\displaystyle 16x+7y=15}.
For example, if all three terms are even, you can at least divide by 2, as follows: 42x+36y=48{\displaystyle 42x+36y=48} (all terms are divisible by 2) 21x+18y=24{\displaystyle 21x+18y=24} (all terms now are divisible by 3) 7x+6y=8{\displaystyle 7x+6y=8} (this equation is as reduced as possible)
For example, if both A{\displaystyle A} and B{\displaystyle B} are even, then the sum of the left side of the equation would have to be even. But if C{\displaystyle C} is odd, then there will be no integer solution to the problem. 2x+4y=21{\displaystyle 2x+4y=21} will have no integer solution. 5x+10y=17{\displaystyle 5x+10y=17} can have no integer solution, because the left side of the equation is divisible by 5, but the right side is not.
For example, the following steps illustrate the Euclidean algorithm being used to find the GCF of 272 and 36: 272=7∗36+20{\displaystyle 272=736+20}. . . . divide the larger number (272) by the smaller (36) and note the remainder (20) 36=1∗20+16{\displaystyle 36=120+16}. . . . divide the previous divisor (36) by the previous remainder (20). Note the new remainder (16). 20=1∗16+4{\displaystyle 20=116+4}. . . . Repeat. Divide the previous divisor (20) by the previous remainder (16). Note the new remainder (4). 16=4∗4+0{\displaystyle 16=44+0}. . . . 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.
The steps of the Euclidean algorithm for the coefficients 87 and 64 are as follows: 87=1∗64+23{\displaystyle 87=164+23} 64=2∗23+18{\displaystyle 64=223+18} 23=1∗18+5{\displaystyle 23=118+5} 18=3∗5+3{\displaystyle 18=35+3} 5=1∗3+2{\displaystyle 5=13+2} 3=1∗2+1{\displaystyle 3=12+1} 2=2∗1+0{\displaystyle 2=2*1+0}
For example, the sample problem 87x−64y=3{\displaystyle 87x-64y=3} 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.
Begin by numbering the steps of the Euclidean algorithm reduction, as reference points. Thus, you have the following steps: Step 1:87=(1∗64)+23{\displaystyle {\text{Step 1}}:87=(164)+23} Step 2:64=(2∗23)+18{\displaystyle {\text{Step 2}}:64=(223)+18} Step 3:23=(1∗18)+5{\displaystyle {\text{Step 3}}:23=(118)+5} Step 4:18=(3∗5)+3{\displaystyle {\text{Step 4}}:18=(35)+3} Step 5:5=(1∗3)+2{\displaystyle {\text{Step 5}}:5=(13)+2} Step 6:3=(1∗2)+1{\displaystyle {\text{Step 6}}:3=(12)+1} Step 7:2=(2∗1)+0{\displaystyle {\text{Step 7}}:2=(2*1)+0}
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: 1=3−(1∗2){\displaystyle 1=3-(1*2)}
You can revise Step 5 to isolate its remainder as: 2=5−(1∗3){\displaystyle 2=5-(1*3)} or 2=5−3{\displaystyle 2=5-3}
1=3−(1∗2){\displaystyle 1=3-(1*2)}…. . (This is the Step 6 revision. ) 1=3−(5−3){\displaystyle 1=3-(5-3)}…. . (Substitute in place of the value 2. ) 1=3−5+3{\displaystyle 1=3-5+3}…. . (Distribution of the negative sign) 1=2(3)−5{\displaystyle 1=2(3)-5}…. . (Simplify)
The last step was Step 5. Now revise Step 4 to isolate its remainder as: 3=18−(3∗5){\displaystyle 3=18-(35)} Substitute that value in place of the 3 in your latest simplification step and then simplify: 1=2(18−3∗5)−5{\displaystyle 1=2(18-35)-5} 1=2(18)−6(5)−5{\displaystyle 1=2(18)-6(5)-5} 1=2(18)−7(5){\displaystyle 1=2(18)-7(5)}
1=2(18)−7(5){\displaystyle 1=2(18)-7(5)} 1=2(18)−7(23−18){\displaystyle 1=2(18)-7(23-18)}…. . (Substitution from Step 3) 1=2(18)−7(23)+7(18){\displaystyle 1=2(18)-7(23)+7(18)} 1=9(18)−7(23){\displaystyle 1=9(18)-7(23)} 1=9(64−2∗23)−7(23){\displaystyle 1=9(64-2*23)-7(23)}…. . (Substitution from Step 2) 1=9(64)−18(23)−7(23){\displaystyle 1=9(64)-18(23)-7(23)} 1=9(64)−25(23){\displaystyle 1=9(64)-25(23)} 1=9(64)−25(87−64){\displaystyle 1=9(64)-25(87-64)}…. . (Substitution from Step 1) 1=9(64)−25(87)+25(64){\displaystyle 1=9(64)-25(87)+25(64)} 1=34(64)−25(87){\displaystyle 1=34(64)-25(87)}
In this case, the original problem you are trying to solve is 87x−64y=3{\displaystyle 87x-64y=3}. 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: 87(−25)−64(−34)=1{\displaystyle 87(-25)-64(-34)=1}
87(−25∗3)−64(−34∗3)=1∗3{\displaystyle 87(-253)-64(-343)=1*3} 87(−75)−64(−102)=3{\displaystyle 87(-75)-64(-102)=3}
In this case, you can identify the solution as the coordinate pair (x,y)=(−75,−102){\displaystyle (x,y)=(-75,-102)}.
Ax+By=C{\displaystyle Ax+By=C} A(x+B)+B(y−A)=C{\displaystyle A(x+B)+B(y-A)=C} …. . (Adding a B to x while subtracting A from y results in the same solution. )
In this case, your solution is the coordinate pair (x,y)=(−75,−102){\displaystyle (x,y)=(-75,-102)}.
In this problem, beginning with the solution x=-75, add the y coefficient of -64, as follows: x=−75+(−64)=−139{\displaystyle x=-75+(-64)=-139} Thus, a new solution for the original equation will have the x value of -139.
For this problem, beginning with the solution y=-102, subtract the x coefficient of 87, as follows: y=−102−87=−189{\displaystyle y=-102-87=-189} Thus, a new solution for the original equation will have the y coordinate of -189. The new ordered pair should be (x,y)=(−139,−189){\displaystyle (x,y)=(-139,-189)}.
87x−64y=3{\displaystyle 87x-64y=3} 87(−139)−64(−189)=3{\displaystyle 87(-139)-64(-189)=3} 3=3{\displaystyle 3=3} Because the statement is true, the solution works.
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: x(k)=−75−64k{\displaystyle x(k)=-75-64k} 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: y(k)=−102−87k{\displaystyle y(k)=-102-87k}
