Find proof Egyptian Fractions and modified Euclidean Algorithm The modified Euclidean Algorithm has you pick an $a,b\in\mathbb{Z}^+$.  Perform the usual division algorithm with the dividend being $b$ and the divisor being $a$.  This produces $b=aq+r$.  The next step is $bq=rq_2+r_2$.  The algorithm terminates and $\sum_{i=0}^n\frac{(-1)^i}{q_i}=\frac{a}{b}$.
Results like this come up but I can't find the proof in any number theory textbook I own, or online.  My thinking is I'm using the wrong resources.
My question then is: Can any of you provide either i) the proof, ii) where you found it and or iii) another place to look up "classical" results like this.
Addendum: There is yet another version of this where the sum adds only positive unit fractions and is more like the traditional egyptian fractions.
 A: You are missing key conditions in the Euclidean Algorithm; you require $0\leq r\lt a$ in the first step, and in general $0\leq r_{i+1}\lt r_i$, and "terminates" means the remainder is $0$. This is what guarantees that the process terminates: you have a strictly decreasing sequence of nonnegative integers, and therefore it must be a finite sequence before you get $r_n = 0$ for some $n$; certainly, no more than $a$ steps, but in fact less than that since you can show that after two steps the remainders drop by at least half. 
I'm not in my office, but unless I am much mistaken the fact that the process terminates is in Niven, Zuckerman, and Montgomery's An Introduction to the Theory of Numbers, among others. I'll check tomorrow.
The formula $\sum_{i=0}^n\frac{(-1)^i}{q_i}=\frac{a}{b}$ doesn't work with your notation, since you either don't have $q_0$ or you don't have $q_1$; I suspect you mistyped your "next step", and that you mean mean $b=aq_0 + r_0$, and then $bq_0 = r_0q_1 + r_1$, and more generally $bq_0\cdots q_k = r_kq_{k+1}+r_{k+1}$ (with the restrictions mentioned above on the $r_j$). Moreover, it requires the extra assumption that $a\lt b$ (otherwise, $q_0 = 0$); this is not usually necessary in the Euclidean algorithm, so you need to specify it if you are going to use that formula.
As to a proof: if the remainder is $0$ the result is immediate, since $b=aq$ with all nonzero implies $\frac{1}{q} = \frac{a}{b}$. Assume the formula holds if the algorithm terminates after $k$ steps, and that you have an application with $k+1$ steps. Using the induction hypothesis applied to $bq_0$ and $r_0$ you have that
$$\sum_{i=0}^{k} \frac{(-1)^i}{q_{i+1}} = \frac{r_0}{bq_0}.$$
Replacing $r_0$ with $b-aq_0$ we get 
$$\sum_{i=0}^k \frac{(-1)^i}{q_{i+1}} = \frac{b-aq_0}{bq_0} = \frac{1}{q_0} - \frac{a}{b}.$$
Now solving for $\frac{a}{b}$ gives
\begin{align*}
\frac{a}{b} &= \frac{1}{q_0} - \sum_{i=0}^{k}\frac{(-1)^i}{q_{i+1}}
= \frac{1}{q_0} + \sum_{i=0}^k\frac{(-1)^{i+1}}{q_{i+1}}\\
&= \frac{1}{q_0} + \sum_{i=1}^{k+1}\frac{(-1)^i}{q_i}
= \sum_{i=0}^{k+1}\frac{(-1)^i}{q_i},
\end{align*}
which proves the formula by induction.
As to the addendum: I don't know which version you are thinking of, but I'll wager a proof by induction will work along the same lines as the one above for it.
A: By the division algorithm $\rm\ \ b\ =\  a\ q\ +\ a'\ \ $ for  $\rm\ \ 0\: \le\: a'\: <\: a\:. $   
Dividing this by $\rm\: b\: q\: $ yields $\rm\displaystyle\ \frac{a}b\ =\ \frac{1}q\: -\: \frac{a'}{b'}\ $ for $\rm\ b' = b\ q\:.$  
Now recurse similarly on $\rm\ a'/\:b'\:.\ $ Since each step decreases numerators $\rm\ a' < a\:,\ $ eventually one reaches $\rm\ a' = 0\:,\: $ ending the recursion, so representing $\rm\ a/b\ $ as the claimed sum of unit fractions.
