Lamé's Theorem/Examples/12378 and 3054

From ProofWiki
Jump to navigation Jump to search

Example of Use of Lamé's Theorem

The Euclidean Algorithm, when employed to find the GCD of $12378$ and $3054$, will take no more than $20$ steps.


Proof

The smaller of the $2$ integers $12378$ and $3054$ has $4$ digits.

Hence by Lamé's Theorem it will take no more than $4 \times 5 = 20$ steps of the Euclidean Algorithm to terminate.


In fact, from Euclidean Algorithm: $12378$ and $3054$, it in fact takes as few as $6$ steps.

$\blacksquare$


Sources