3
$\begingroup$

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.

2 Answers 2

5

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.

  • 0
    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!2011-01-13
5

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.

  • 0
    @Tony: What proof did the professor give?2011-01-13