Lamé's Theorem/Least Absolute Remainder

Theorem

Let $a, b \in \Z_{>0}$ be (strictly) positive integers.

Let $c$ and $d$ be the number of digits in $a$ and $b$ respectively when expressed in decimal notation.

Let the Euclidean Algorithm: Least Absolute Remainder variant be employed to find the GCD of $a$ and $b$.

Then it will in general take fewer integer divisions to find $\gcd \set {a, b}$ than it does to use the conventional form of the Euclidean Algorithm.

Proof

This theorem requires a proof. In particular: Don't even know what the form of the theorem itself actually is -- this is mentioned in an aside in Burton's book. He may return to it later. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Source of Name

This entry was named for Gabriel Lamé.

Historical Note

This result was demonstrated by Gabriel Lamé in $1844$.

Sources

• 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm