Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks for the comprehensive answer. I didn't include the restrictions because I only wanted someone to recognize what I was talking about but for clarity's sake - next time. As for the addendum: 4=3*2-2 (Similar to the division algorithm but here q is 1 larger) 4*2=(-2)(-4)+0. Taking the alternate sum of the quotients we get 1/2+1/4 or 3/4. Thanks! –  ttt Jan 13 '11 at 2:03

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.

share|improve this answer
    
I like how this clearly shows how the alternating sum works out. Thanks! (I've since talked to a professor, and he gave yet another proof beyond this and the induction one above.) –  ttt Jan 13 '11 at 2:11
    
@Tony: What proof did the professor give? –  Bill Dubuque Jan 13 '11 at 2:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.