## Sunday, February 23, 2014

### Linear diophantine equations: simplification of sums for reachability (enabled javascipt for latex is needed)

My first meaningful post shall be a mathy one. I wanted to understand the idea behind this, so I've decided to make a post explaining it :)
Assume we have a problem where we have to iterate over all $$x = \sum\limits_{i=1}^n c_{i} \cdot a_{i}$$, where the $$c_{i}$$ are freely selectable. In such problems a very easy simplification can be made: each such $$x$$ can be represented in the form $$x = t \cdot q$$, where $$t = gcd(a_{1},...,a_{n})$$ and $$q \in \mathbb Z$$.

To understand the above statement, we only need to think of the extended euclidean algorithm. Inside of it we find the integers $$x$$ and $$y$$ so that $$x \cdot a_{1} + y \cdot a_{2} = gcd(a_{1},a_{2})$$ holds. Additionally, we can easily imply that each number $$v$$ written in the form $$v = c_{1} \cdot a_{1} + c_{2} \cdot a_{2}$$ must be a multiple of $$g:=gcd(a_{1},a_{2})$$ (as g divides $$a_{1}$$and $$a_{2}$$ it must divide v for the equation to hold (!)).
We show now that the same holds for 3 variables. Let $$x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3}$$ and $$g:=gcd(a_{1},a_{2},a_{3})$$. We have to prove that $$x$$ is a multiple of $$g$$. Consider the first two variables and write: $$a_{1} \cdot c_{1} + a_{2} \cdot c_{2} = t_{1} \cdot gcd(a_{1},a_{2})$$. This gives us $$x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3} = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3}$$. Simply seen here: there are again two fixed numbers and two free! Smells like the extended euclidean again :)
We write: $$G := gcd( gcd(a_{1},a_{2}) , a_{3} ) = gcd(a_{1},a_{2},a_{3}) = g$$ and get: $$x = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3} = t_{2} \cdot g$$ - with this we're done! Inductively the statement follows for 4 and more variables.