Algebra.Com's Answer #635614 by mathmate(429)![\"\"](\"/images/stars/stars-10.gif\")  
You can put this solution on YOUR website!
\n" );
document.write( "Question:
\n" );
document.write( "This diophantine equation seems impossible for me..
\n" );
document.write( "\"A dealer spent $10000 buying cattle, some at $410 each and the rest at $530 each. How many of each sort did she buy?\"
\n" );
document.write( "I made a diophantine equation for this..
\n" );
document.write( "
\n" );
document.write( "simplifies to:
\n" );
document.write( "
\n" );
document.write( "i seem to have most trouble when the c is the biggest number in the equation in ax+by=c
\n" );
document.write( "I tried using euclid's algorithm but it doesnt seem to work for me, i think im using it wrong..
\n" );
document.write( "Any help to the question would be helpful.
\n" );
document.write( "
\n" );
document.write( "Solution:
\n" );
document.write( "There exists a systematic method for solving linear diophantine equations like this one. As Robert mentioned, the key is
\n" );
document.write( "1. check if there is a solution.
\n" );
document.write( "2. find a particular solution, and form the basis for finding all the other solutions.
\n" );
document.write( "This problem is a good example of doing the above, as follows.
\n" );
document.write( "
\n" );
document.write( "Given : 410x+530y=10000
\n" );
document.write( "Step 1.
\n" );
document.write( "Will first find the GCF(410,530) by Euclid's algorithm:
\n" );
document.write( "530=410(1)+120
\n" );
document.write( "410=120(3)+50
\n" );
document.write( "120=50(2)+20
\n" );
document.write( "50=20(2)+10
\n" );
document.write( "20=10(2)
\n" );
document.write( "Therefore the GCF is 10, and since 10|10000, there are infinite solutions.
\n" );
document.write( "
\n" );
document.write( "Step 2.
\n" );
document.write( "Find A particular solution.
\n" );
document.write( "we need to express the GCF (10) as the difference of multiples of 410 and 530. If the answer is not obtained by inspection, we can use the reverse of the Euclid Algorithm to retrace the values.
\n" );
document.write( "For this particular example, we have
\n" );
document.write( "10=50-20(2)
\n" );
document.write( "=50-2(120-50(2))
\n" );
document.write( "=50(5)-120(2)
\n" );
document.write( "=(410-3(120))(5)-120(2)
\n" );
document.write( "=410(5)-120(17)
\n" );
document.write( "=410(5)-(530-410)(17)
\n" );
document.write( "=410(22)-530(17)
\n" );
document.write( "Multiplying by 1000 gives
\n" );
document.write( "10000=410(22000)-530(17000) which satisfies the given diophantine equation, and constitutes ONE solution, where
\n" );
document.write( "x=22000, y=-17000
\n" );
document.write( "
\n" );
document.write( "Step 3.
\n" );
document.write( "We need to find positive values of x and y in order to satisfy the conditions of the problem.
\n" );
document.write( "For this, we start from the original solution of
\n" );
document.write( "x=22000 and y=-17000 and start exchanging x and y according to
\n" );
document.write( "x=22000-530k/10=22000-53k
\n" );
document.write( "y=-17000+410k/10=-17000+41k
\n" );
document.write( "In order to get a positive value for y, we try k≥17000/41=414.6, or 415
\n" );
document.write( "x=5, y=15, since both x and y are non-negative, it is a valid solution.
\n" );
document.write( "Try k=416, x=-48, y=56 which is not acceptable.
\n" );
document.write( "So the final answer is
\n" );
document.write( "x=5, y=15.
\n" );
document.write( "
\n" );
document.write( "Check: 5(410)+15(530)=10000, therefore answer is correct. \n" );
document.write( " |