# Lamé's Theorem/Least Absolute Remainder

Jump to navigation
Jump to search

## 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