Kalkulator NWD (największego wspólnego dzielnika)
Podaj co najmniej dwie liczby całkowite. Obliczymy największą liczbę, która dzieli je wszystkie, i pokażemy każdy krok.
Wynik
6NWD
- 48 = 2 × 18 + 12
- 18 = 1 × 12 + 6
- 12 = 2 × 6 + 0
Dane wejściowe
- Liczby całkowite
- 48; 18
Jak to obliczyć
Podziel większą liczbę przez mniejszą i zapisz resztę.
Wynik
NWD
Jak to obliczyć
- Podziel większą liczbę przez mniejszą i zapisz resztę.
- Powtórz działanie dla mniejszej liczby i otrzymanej reszty.
- Gdy reszta wynosi 0, ostatni dzielnik jest NWD: GCD(a, b) = GCD(b, a mod b).
- Dla większej liczby: GCD(a, b, c) = GCD(GCD(a, b), c).
Przykład
GCD(48, 18): 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0. NWD wynosi 6.
Warto wiedzieć
- Dozwolone są tylko liczby całkowite; znak minus jest pomijany.
- Maksymalnie 50 liczb po 200 cyfr każda, obliczanych dokładnie.
Kiedy użyć
- Skróć ułamek, dzieląc licznik i mianownik przez NWD.
- Sprawdź, czy podane liczby są względnie pierwsze.
Częste pytania
Co to jest NWD?
To największa dodatnia liczba całkowita, która dzieli wszystkie podane liczby bez reszty.
Jak algorytm Euklidesa znajduje NWD?
Dzieli większą liczbę przez mniejszą, a potem powtarza działanie dla dzielnika i reszty. Ostatnia niezerowa reszta to NWD.
Co oznacza NWD równy 1?
Liczby nie mają wspólnego dodatniego dzielnika poza 1, czyli są względnie pierwsze.