整数方程:
10x+6y=12
The point here is not to solve this specific equation but rather to generate an algorithm to handle the more general problem:
ax+by=c eq(1), all variables are integers.
first extract common denominator between a,b and c to the form
a1x+b1y=c1. eq(2)
c1 is prime to both a1 and b1.
Now, if a1 and b1 have common denominator, then there is no solution.
So we look at
a1x+b1y=1 eq(3).
Unfortunately from this point there is no single algebraic equation that can give the solution...
Write q=mod(a1,b1) (all positive integers)
Consider the series l(i)=q*i, i=1,2,...b1-1, and the corresponding series m(i)=mod(l(i), b1).
Each of m(i) is prime to b1 and less than b1 so they all have different values, and there must be one that equals to 1. Denote this i value as i0, then the solution to eq (1) is
x=c1*i0, y=c1*(-i0*a1+1)/b1
Again, we want to build the skill of abstract thinking without specific values.
There is another way of doing it by continuing the breaking down of a pair of mutually prime numbers until we get to the pair of 1 and 2, this is more elegant in looking but much difficult to implement in coding...
