"division algorithm algebra" : supply missing proof from Gauss' Disquisitiones Arithmeticae, article 27

94 Views Asked by At

I started reading Gauss's Disquistiones Arithmeticae (English translation by Clarke) and in article 27 Gauss introduces a notation that is essentially an algebra for the division algorithm for relatively prime operands. This might be a little hard to follow without the book, but I'll do my best (hopefully although this is a little obscure someone out there is familiar with this).

$A = \alpha$, $B = \beta A + 1$, $C = \gamma B + A$, $D = \delta C + B$, $E = \epsilon D + C$, etc.

Notationally, $A = [\alpha]$, $B = [\alpha, \beta]$, $C = [\alpha, \beta, \gamma]$, etc.

He then states without proof the property

$$[\alpha, \beta, ...,\lambda, \mu] \cdot [\beta, \gamma, ..., \lambda] - [\alpha, \beta, \gamma, ..., \lambda] \cdot [\beta, \gamma, ..., \lambda, \mu] = \pm 1$$ where $+1$ is taken if the number of terms $\alpha, ..., \mu$ is even and $-1$ if odd.

Gauss states in a footnote that the simple demonstration is omitted. I worked out an inductive proof that probably has a few flaws in it but I think is essentially correct in that it contains the valid kernel of the reasoning involved, but is quite messy. I've outlined my proof below, but my question is whether this level of detail is truly something that Gauss would have considered too simple to explain, or if I am missing some very simple way to see this relationship?

For my inductive proof a base case $$[\alpha, \beta, \gamma][\beta] - [\alpha, \beta][\beta, \gamma]$$ is straightforward and you wind up with $$(\gamma[\alpha, \beta] + \alpha)\beta - (\beta\alpha + 1)(\gamma\beta + 1) = -1$$

Similarly $$[\alpha, \beta, \gamma, \delta][\beta, \gamma] - [\alpha, \beta, \gamma] \cdot [\beta, \gamma, \delta] = 1$$.

I was unsure how to handle the alternating signs for the induction (hence the pair of base cases), as well as how to be technically correct with the IH (e.g. it's more like a more complicated base case than a true IH - the best I could do with this would be to say something handwavy like "it would be essentially the same with an arbitrarily extended list") but made an "IH" of $$[\alpha, \beta, ..., \epsilon][\beta, ..., \delta] - [\alpha, ..., \delta][\beta, ..., \epsilon] = -1$$

Showing the next step then involves the expression

$$[\alpha,...,\zeta][\beta,...,\epsilon] = (\zeta[\alpha,...,\epsilon] + [\alpha,...,\delta])(\epsilon[\beta,..,\delta] + [\beta,...,\gamma])$$

and the IH can be used to substitute $-1 + [\alpha,...,\delta][\beta,...,\epsilon]$ for $[\alpha,...,\epsilon][\beta,...,\delta]$.

Continued calculation in which the "preceding IH" is also used produces cancellations (messy, but straightforward) and does eventually yield the desired value 1.

With all its flaws I think this convinces me of the truth of the stated relationship, and I think I couild probably work it into a correct form if I wanted to.

I just want to know if it really has to be this messy? I realize there may be other modern methods and I don't mind if someone wants to explain using one of those, but what I'm most interested in is the explanation Gauss would have been referring to.

1

There are 1 best solutions below

0
On BEST ANSWER

Write $$\left[\alpha,\cdots,\kappa \right]=K_1 \quad \left[\alpha,\cdots,\kappa,\lambda \right]=L_1 \quad \left[\alpha,\cdots,\kappa,\lambda,\mu \right]=M_1$$

and

$$\left[\beta,\cdots,\kappa \right]=K_2 \quad \left[\beta,\cdots,\kappa,\lambda \right]=L_2 \quad \left[\beta,\cdots,\kappa,\lambda,\mu \right]=M_2$$

Then $$M_1=\mu L_1+K_1\quad \&\quad M_2=\mu L_2+K_2$$

You would like to compute $$M_1\times L_2-L_1\times M_2$$ But we have $$M_1\times L_2-L_1\times M_2=\left(\mu L_1+K_1\right)\times L_2-\left(\mu L_2+K_2\right)\times L_1=K_1\times L_2-K_2\times L_1$$ Which is just $-1$ times the same expression with one fewer variable, hence induction immediately gives us what we want.