Lamé's Theorem/Least Absolute Remainder

From ProofWiki
Jump to navigation Jump to search


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.


Source of Name

This entry was named for Gabriel Lamé.

Historical Note

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