Szkoła podstawowa
Definicja
Największy wspólny dzielnik (NWD) dwóch liczb całkowitych - to największa liczba naturalna, która dzieli obie te liczby bez reszty. Największym wspólnym dzielnikiem liczb \(10\) i \(6\) jest liczba \(2\).
Największym wspólnym dzielnikiem liczb \(15\) i \(5\) jest liczba \(5\).
Największym wspólnym dzielnikiem liczb \(24\) i \(18\) jest liczba \(6\).
Największym wspólnym dzielnikiem liczb \(75\) i \(100\) jest liczba \(25\).
Sposób zapisu
Największy wspólny dzielnik liczb \(n\) i \(m\) zapisujemy tak: \[\operatorname{NWD}(n, m)\] Poniższy algorytm służy do obliczania NWD (największego wspólnego dzielnika) dwóch liczb całkowitych.
Algorytm Euklidesa
Aby obliczyć \(\operatorname{NWD} (a, b)\), wykonujemy kolejno następujące kroki:
- Dzielimy z resztą liczbę \(a\) przez liczbę \(b\)
- jeżeli reszta jest równa \(0\), to \(\operatorname{NWD}(a, b) = b\)
- jeżeli reszta jest różna od \(0\), to przypisujemy liczbie \(a\) wartość liczby \(b\), liczbie \(b\) wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.
Wyznacz największy wspólny dzielnik liczb \(282\) i \(78\).
Zaczynamy od podzielenia liczby \(282\) przez liczbę \(78\) z resztą: \[282 : 78 = 3, \text{ reszty }48\] Otrzymaliśmy resztę różną od zera, zatem teraz podzielimy liczbę \(78\) przez resztę \(48\). Ten schemat będziemy powtarzać do momentu otrzymania reszty równej \(0\). \[ 78 : 48 = 1, \text{ reszty }30\\[6pt] 48 : 30 = 1, \text{ reszty }18\\[6pt] 30 : 18 = 1, \text{ reszty }12\\[6pt] 18 : 12 = 1, \text{ reszty }6\\[6pt] 12 : 6 = 2, \text{ reszty }0 \] Otrzymaliśmy resztę równą zero, zatem szukany NWD będzie równy ostatniej niezerowej reszcie: \[\operatorname{NWD}(282, 78) = 6\]
Jako generator nieskończonej liczby analogicznych przykładów możesz wykorzystać poniższy program.
W tym filmiku pokazuję metodę obliczania NWD i NWW na pięciu przykładach.
Czas nagrania: 15 min.