I have this linear Diophantine equation that I want to find all the solutions for.
$6x+10y+15z=1$
Here is my attempt at a solution:
Check if solutions exist: $gcd(6,10,15)|1$ holds and therefore the equation does have solutions.
(1) $6x+10y+15z=1$
(2) $2(3x+5y)+15z=1$
(3) Let $w=3x+5y$ and substitute into (2)
(4) $2w+15z=1$ has a particular solution $(w,z)=(-7,1)$
(5) All the solutions become $w=-7+15k$ and $z=1-2k$
(6) Using (3) and (5) we get $3x+5y=w=-7+15k$
...
Now this is where I get stuck, I do not know how to continue. To my understanding I need to solve for x and y but I do not know how I will achieve this feat. It feels like I am missing something trivial.
EDIT
I may have solved it:
$3x+5y=w=-7+15k$
Using Euclid's algorithm to find $gcd(3,5)$ and then working backwards I end up with:
$2*3 + (-1)5 = 1$
but we had $3x+5y=w$ so I have to modify
$2*3w + (-1)5*w = 1w$
add the term $l(lcm(3,5)-lcm(3,5))$
$2*3w + (-1)5*w + l(3*5-3*5) = w$
$3(2w-5l) + 5(-1w+3l)=w$
Giving us
$x=2w-5l = 2(-7+15k)-5l = -14 + 30k - 5l$
and
$y=-w+3k = (-1)(-7+15k)+3l = 7 - 15k + 3l$
The final answer then becomes:
$x= -14 + 30k - 5l$
$y= 7 - 15k + 3l$
$z= 1 - 2k$
Is this correct?
Using Haskell:
let fun k l = 6*(-14 + 30*k - 5*l) + 10*(7 - 15*k + 3*l) + 15*(1 - 2*k)
and then calling the function with different k,l all seem to give the answer 1 which is to be expected since our original LDE is $6x+10y+15z=1$.
Using QuickCheck library to test it yields:
Prelude Test.QuickCheck> quickCheck (withMaxSuccess 100000 prop_testLDE)
+++ OK, passed 100000 tests.
Hint:t consider the family
$x=5k+1,y=-6k-2,z=2k+1$