Question

Find the greatest common divisor of 100 and 254, using • prime factorization- • euclidean algorithm-

Answer 1

Via prime factorization:

$100=10^2=2^2\cdot5^2$
$254=2\cdot127$

of which the only common factor is a single power of 2, so $\mathrm{gcd}(100,254)=2$.

Via the Euclidean algorithm:

$254=2\cdot100+54$
$100=1\cdot54+46$
$54=1\cdot46+8$
$46=5\cdot8+6$
$8=1\cdot6+2$
$6=3\cdot2+0$

which means $\mathrm{gcd}(100,254)=2$, as expected.