§ 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 gcd(p,p)gcd(p, p'). WLOG, we assume that p>pp > p'. We now find a coefficient dd such that p=dp+rp = d p' + r where 0r<p0 \leq r < p'. At this stage, we need to repeat the algorithm to find gcd(p,r)gcd(p', r). We stop with the base case gcd(p,0)=pgcd(p', 0) = p'.

§ My choice of notation

I dislike the differentiation that occurs between pp, pp', and rr in the notation. I will notate this as gcd(p0,p1)gcd(p_0, p_1). WLOG, assume that p0>p1p_0 > p_1. We now find a coefficient d0d_0 such that p0=p1d1+p2p_0 = p_1 d_1 + p_2 such that 0p2<p10 \leq p_2 < p_1. At this stage, we recurse to find gcd(p1,p2)gcd(p_1, p_2). We stop with the base case gcd(pn1,pn)=pngcd(p_{n-1}, p_n) = p_n iff pn1=dnpn+0p_{n-1} = d_n p_n + 0. That is, when we have pn+1=0p_{n+1} = 0, we stop with the process, taking the gcd to be pnp_n.

§ Matrices

We can write the equation p0=p1d1+p2p_0 = p_1 d_1 + p_2 as the equation p0=[d1;1][p1;p2]Tp_0 = [d_1; 1] [p_1; p_2]^T. But now, we have lost some state. We used to have both p1p_1 and p2p_2, but we are left with p0p_0. We should always strive to have "matching" inputs and output so we can iterate maps. This leads us to the natural generalization:
[p0p1]=[d1110][p1p2] \begin{bmatrix} p_0 \\ p_1 \end{bmatrix} = \begin{bmatrix} d_1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} p_1 \\ p_2 \end{bmatrix}
So at the first step, we are trying to find a (d1,p2)(d_1, p_2) such that the matrix equation holds, and 0p2<d10 \leq p_2 < d_1.

§ Extended euclidian division

When we finish, we have that gcd(pn1,pn)=pngcd(p_{n-1}, p_n) = p_n. I'll call the GCD as gg for clarity. We can now write the GCD as a linear combination of the inputs g=pn=0pn1+1png = p_n = 0 \cdot p_{n-1} + 1 \cdot p_n. We now want to backtrack to find out how to write g=ωn2pn2+ωn1pn1g = \omega_{n-2} p_{n-2} + \omega_{n-1} p_{n-1}. And so on, all the way to g=ω0p0+ω1p1g = \omega_0 p_0 + \omega_1 p_1.
  • We can begin with the general case:
g=[ωω][pp] g = \begin{bmatrix} \omega' & \omega'' \end{bmatrix} \begin{bmatrix} p' \\ p'' \end{bmatrix}
  • We have the relationship:
[pp]=[d110][pp] \begin{bmatrix} p \\ p' \end{bmatrix} = \begin{bmatrix} d' & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} p' \\ p'' \end{bmatrix}
  • We can invert the matrix to get:
[pp]=[011d][pp] \begin{bmatrix} p' \\ p'' \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & - d' \end{bmatrix} \begin{bmatrix} p \\ p' \end{bmatrix}
  • now combine with the previous equation to get:
g=[ωω][pp]g=[ωω][011d][pp]g=[ωωdω][pp] \begin{aligned} &g = \begin{bmatrix} \omega' & \omega'' \end{bmatrix} \begin{bmatrix} p' \\ p'' \end{bmatrix} \\ &g = \begin{bmatrix} \omega' & \omega'' \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & - d' \end{bmatrix} \begin{bmatrix} p \\ p' \end{bmatrix} \\ &g = \begin{bmatrix} \omega'' & \omega - d' \omega' \end{bmatrix} \begin{bmatrix} p \\ p' \end{bmatrix} \\ \end{aligned}

§ Fractions

  • GCD factorization equation: p/p=(αp+p)/p=α+p/pp/p' = (\alpha p' + p'')/p' = \alpha + p''/p'.
  • Bezout equation: ωp+ωp=g\omega' p' + \omega'' p'' = g.
  • Bezout equation as fractions ω+ωp/p=g/p\omega' + \omega'' p''/p' = g/p'.