Introducing …. the Greedy Calvinosaurus Dinosaur
In this week's post, learn about Greatest Common Divisor.
Last week, we introduced several questions based on calculating the Greatest Common Divisor of several integers and polynomials. Using the Euclidean Algorithm is a standard approach to helping us to quickly calculate these values.
Judging from the comments in the solution discussions, here are some questions for you to ponder:
1) If \( n < 10 \), can \( \gcd (n, m ) > 10 \)?
2) What is the value of \( \gcd( -14, -21 ) \)?
3) Why does the Euclidean algorithm work? Specifically, why does \( \gcd(n,m) = \gcd(n, m+kn ) \) for any integers \(n, m, k \)?
For those who want a coding challenge:
Write code to calculate the GCD of 2 numbers, which ends in finitely many steps. You are not allowed to use conditions like “If n > 0, continue” or equivalent hacks.