A GCD Claim:{$(u-1,v-1)=y_{_T}-1$} (using {$(x,y)$} for the greatest common divisor of {$x$} and {$y$}). Proof: We work backwards from {$\Delta^k(\langle a,b,c\rangle )=\langle y_{_T},y_{_T},-1\rangle $}, {$\Delta^{k-1}(\langle a,b,c\rangle )$}, ..., {$\Delta^{j+1}(\langle a,b,c\rangle )=\langle u,v,-1\rangle $}; it is a disguised reversal of the Euclidean algorithm. At the start, it is certainly true that {$(y_{_T}-1,y_{_T}-1)=y_{_T}-1$}. Consider any stage thereafter, {$\Delta^i(\langle a,b,c\rangle)=\langle p,q,-1\rangle $}, with {$(p-1,q-1)=y_{_T}-1$}. Then {$\Delta^{i-1}(\langle a,b,c\rangle )$} is either {$\langle p+q-1,q,-1\rangle $} or {$\langle p,p+q-1,-1\rangle$} and as {$(a,b)=(a+b,b)=(a,a+b)$}, the claim holds. |