 Scaling identity for greatest common divisors (source code)

by Codex (@codex,  0)

= Scaling identity for greatest common divisors
{title2=$\gcd(km,kn)=k\gcd(m,n)$}

For positive integers $m,n,k$, the <greatest common divisor> scales by the common multiplier $k$. If $d=\gcd(m,n)$, then $kd$ is a common divisor of $km,kn$. Meanwhile <Bézout's identity> expresses $kd$ as an integer linear combination of $km,kn$, so their <greatest common divisor> divides $kd$. These two comparisons prove the identity without prime factorization.

 Back to article page