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