整除和素数Gcd

我们可以再次使用素数因子来计算两个数的最大公约数。记住， 一个数的除数必定包含有这个数的部分素数因子。

假设__{.m-red}X__是__{.m-green}18__和__{.m-blue}30__的最大公约数.那么__{.m-red}X__ 整除__{.m-green}18__, 因此__{.m-red}X__的素数因子也在_{span.number-ball.small.l-blue}2_, 2_和{span.number-ball.small.l-blue}3_中。同理, X 整除__{.m-blue}30__, 因此__{.m-red}X__的素数因子也在 2, 3 和 _{span.number-ball.small.l-green}5_中。