Solving Linear Diophantine Equations With Finite Continued Fractions
Example: Find the general solution of
\[16x+219y=17\]
.The finite continued fraction of
\[\frac{219}{16}\]
is \[[ 13,1,2,5 ]\]
and this finite continued fraction has convergents \[13, \; 13 + \frac{1}{1}=14, \; 13 + \frac{1}{1+ \frac{1}{2}}= \frac{41}{3}, \; 13 + \frac{1}{1+ \frac{1}{2+ \frac{1}{5}}}= \frac{219}{16}\]
.From the final two convergents
\[\begin{equation} \begin{aligned} & 3 \times 219 -16 \times 41=1 \\ & (17 \times 3=51) \times 219 -16 \times (17 \times 41=697)=17 \end{aligned} \end{equation}\]
.We can take the general solution as
\[x=-697+219t, \; y=51-16t \]
. 
