NWD czyli największy wspólny dzielnik dwóch liczb to największa liczba, która dzieli je bez reszty. Aby znaleźć największy wspólny dzielnik dwóch liczb całkowitych należy na początek obie liczby rozłożyć na czynniki pierwsze. Robi się to poprzez dzielenie przez kolejne liczby pierwsze. Najpierw dzielimy przez 2. Jeżeli wynik dzielenia jest bez reszty, wtedy zapisujemy 2 do wyniku i próbujemy wynik dzielenia znów podzielić przez 2. Robimy tak póki wyniki dzielenia są bez reszty. Kiedy dostajemy resztę, wtedy 2 z tego dzielenia nie trafia do wyniku i próbujemy podzielić przez 3. Jeżeli wynik dzielenia jest bez reszty do wyniku trafia 3 i wynik dzielenia próbujemy dalej dzielić. Jak dostaniemy resztę wtedy próbujemy podzielić przez 5 i tak dalej. Uzyskane liczby z wyniku dają rozkład na czynniki pierwsze. Kiedy pomnożymy je kolejno przez siebie powinniśmy dostać wyjściową liczbę.

Kiedy mamy już obie liczby rozłożone na czynniki pierwsze wtedy podreślamy pary liczb znajdujące się w obu rozkładach. Mnożymy te powtarzające się liczby przez siebie i wynik tego mnożenia jest szukanym największym wspólnym dzielnikiem.

Chcemy znaleźć NWD( 658, 84 ), czyli największy wspólny dzielnik liczb 658 i 84. Najpierw musimy rozłożyć obie liczby na czynniki pierwsze. Zacznijmy od 658. Próbujemy podzielić przez 2 i uzyskujemy wynik 329 bez reszty. Zapamiętujemy 2 do wyniku. Najprościej robi się to w tabelce:

Teraz próbujemy przez 2 podzielić 329. Widać od razu, że tym razem dzielenie będzie z resztą. Próbujemy zatem dzielić przez 3 i znów mamy resztę. Kolejną liczbą pierwszą jest 5 i też na podstawie wiedzy o cechach podzielności wiemy, że dzielenie będzie z resztą. Dopiero dzielenie przez następną liczbę pierwszą czyli 7 daje 47 bez reszty. Zapisujemy więc:

47 jest liczbą pierwszą, więc od razu możemy iść dalej:

Kiedy uzyskamy 1 po lewej stronie tabelki zatrzymuemy się. Rozkład na czynniki pierwsze liczby 628 odczytujemy z prawej kolumny tabeli: 628 = 2 * 7 * 47.

Teraz musimy znaleźć rozkład na czynniki pierwsze drugiej liczby zadania czyli 84. Najpierw próbujemy dzielić przez 2 i dostajemy 42 bez reszty:

Druga próba dzielenia ( 42 : 2 = 21 ) również nie daje reszty:

Za trzecim razem dzielenie przez 2 da już wynik z resztą. Próbujemy dzielić przez 3:

7 jest liczbą pierwszą, więc od możemy pominąć próby dzielenia przez 5 i od razu zapisać:

Jak już wiemy, gdy po lewej stronie dostaniemy 1 zatrzymujemy się. Rozkład na czynniki pierwsze to: 84 = 2 * 2 * 3 * 7

Mamy więc dwa rozkłady:

• 628 = 2 * 7 * 47
• 84 = 2 * 2 * 3 * 7

Wspólnymi liczbami w obu rozkładach są zaznaczone na czerwono 2 i 7. Największym wspólnym dzielnikiem 628 i 84 będzie więc 2 * 7 = 14.

Może się tak zdażyć, że w rozkładach nie będzie wspólnych liczb. Wtedy największym wspólnym dzielnikim obu liczb jest 1.