§ Extended euclidian algorithm
§ Original definition
I feel like I only understand the extended euclidian algorithm algebraically,
so I've been trying to understand it from other perspectives. Note that
we want to find . WLOG, we assume that .
We now find a coefficient such that where .
At this stage, we need to repeat the algorithm to find . We
stop with the base case .
§ My choice of notation
I dislike the differentiation that occurs between , , and
in the notation. I will notate this as . WLOG, assume
that . We now find a coefficient such that
such that . At this stage, we recurse to find
. We stop with the base case iff
. That is, when we have , we stop
with the process, taking the gcd to be .
We can write the equation as the equation
. But now, we have lost some state. We used
to have both and , but we are left with . We should always
strive to have "matching" inputs and output so we can iterate maps. This
leads us to the natural generalization:
So at the first step, we are trying to find a such that the
matrix equation holds, and .
§ Extended euclidian division
When we finish, we have that . I'll call the GCD
as for clarity. We can now write the GCD as a linear combination
of the inputs . We now
want to backtrack to find out how to write .
And so on, all the way to .
- We can begin with the general case:
- We have the relationship:
- We can invert the matrix to get:
- now combine with the previous equation to get:
- GCD factorization equation: .
- Bezout equation: .
- Bezout equation as fractions .