# Lamé's Theorem/Examples/12378 and 3054

< Lamé's Theorem | Examples

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

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