Divizibilitate și Numere PrimeGcd

Putem folosi din nou descompunerea în factori primi pentru a calcula cmmdc al oricăror două numere. Să ne reamintim că orice divizor al unui număr trebuie să aibă o parte din divizorii primi ai acelui număr.

Să presupunem că X este cmmdc al lui 18 și 30. Atunci X divide pe 18, deci divizorii primi ai lui X vor fi 2, 3 și 3. De asemenea, X divide pe 30, deci divizorii primi ai lui X vor fi 2, 3 și 5.