Kalkulator NWD dwóch liczb naturalnych
Znajdź największy wspólny dzielnik bez zgadywania. Zobacz kolejne dzielenia z resztą, NWW, skrócony stosunek oraz pełną listę wspólnych dzielników w bezpiecznym zakresie obliczeń.
Dwie liczby do porównania
Taśma dzielenia z resztą
126 = 1 × 84 + 4284 = 2 × 42 + 0Szybka zasada kontroli
Prawidłowy NWD zawsze dzieli oba argumenty bez reszty. Jeżeli choć jedno dzielenie pozostawia resztę, przepisano liczbę lub wykonano krok algorytmu niepoprawnie.
Pełny przykład: NWD liczb 1071 i 462
Zacznij od większej liczby. Dzielenie 1071 przez 462 daje iloraz 2, ponieważ dwie kopie 462 dają 924, oraz resztę 147. Pierwszy zapis ma więc postać 1071 = 2 × 462 + 147. Nie szukamy teraz dzielników 1071; przenosimy do kolejnego wiersza poprzedni dzielnik i otrzymaną resztę.
Dzielimy 462 przez 147. Trzy kopie 147 dają 441, dlatego reszta wynosi 21: 462 = 3 × 147 + 21. Następnie 147 dzieli się przez 21 dokładnie siedem razy, co zapisujemy jako 147 = 7 × 21 + 0. Ostatnią niezerową resztą jest 21, zatem NWD(1071, 462) = 21.
Kontrola daje 1071 ÷ 21 = 51 oraz 462 ÷ 21 = 22. Liczby 51 i 22 nie mają wspólnego dzielnika większego niż 1, więc stosunek 1071 : 462 skraca się do 51 : 22. NWW wynosi (1071 ÷ 21) × 462, czyli 23 562. Ten przykład pokazuje, że zaledwie trzy dzielenia zastępują sprawdzanie wielu kandydatów.
NWD trzech lub większej liczby wartości
Formularz przyjmuje dwie liczby, ale algorytm można stosować etapami do dłuższej listy. Najpierw oblicz NWD pierwszej i drugiej wartości. Otrzymany rezultat wpisz razem z trzecią wartością, potem powtórz z czwartą. Zależność ma postać NWD(a, b, c) = NWD(NWD(a, b), c).
Dla 84, 126 i 210 najpierw otrzymujemy NWD(84, 126) = 42. Drugi etap to NWD(42, 210) = 42, więc wszystkie trzy liczby można podzielić na 42 identyczne grupy. Gdy na dowolnym etapie rezultat spadnie do 1, dalsze argumenty nie zwiększą go ponownie; NWD całej listy pozostanie 1. Zapisuj wyniki pośrednie, aby móc odtworzyć tok rozwiązania i nie pomylić rezultatu pary z odpowiedzią dla całego zestawu.
Czym jest NWD?
Największy wspólny dzielnik dwóch liczb naturalnych to największa liczba naturalna, przez którą obie liczby dzielą się bez reszty. Dla 84 i 126 wspólnymi dzielnikami są 1, 2, 3, 6, 7, 14, 21 i 42. Największy z nich to 42, dlatego zapisujemy NWD(84, 126) = 42.
Definicja mówi, czego szukamy, ale ręczne sprawdzanie wszystkich kandydatów jest powolne dla dużych liczb. Kalkulator używa algorytmu Euklidesa. Jego siła polega na tym, że wspólny dzielnik większej liczby i mniejszej liczby jest także wspólnym dzielnikiem mniejszej liczby i reszty z ich dzielenia. Każdy krok zmniejsza drugi argument, aż reszta stanie się zerem.
Jak czytać taśmę obliczeń?
Kalkulator najpierw ustawia większą z podanych liczb po lewej. Pierwszy wiersz przykładu brzmi: 126 = 1 × 84 + 42. Iloraz całkowity wynosi 1, a reszta 42. W kolejnym kroku liczba 84 zajmuje miejsce dzielnej, a poprzednia reszta 42 staje się dzielnikiem.
Drugi wiersz to 84 = 2 × 42 + 0. Reszta zero kończy algorytm. Ostatni niezerowy dzielnik, czyli 42, jest NWD. Numer kroku nie oznacza potęgi ani kolejnego dzielnika; porządkuje tylko rzeczywiście wykonane dzielenia.
Dlaczego algorytm Euklidesa działa?
Jeżeli a = q × b + r, to r = a − q × b. Każda liczba dzieląca jednocześnie a oraz b dzieli również ich różnicę po odjęciu q kopii b, czyli r. Odwrotnie, wspólny dzielnik b i r dzieli sumę q × b + r, a więc także a. Zbiory wspólnych dzielników par (a, b) oraz (b, r) są takie same.
Możemy więc zastępować parę nową, mniejszą parą bez utraty odpowiedzi. Reszta jest zawsze mniejsza od dodatniego dzielnika, dlatego proces musi się skończyć. To dowód konstrukcyjny: nie tylko stwierdza istnienie NWD, lecz podaje sposób jego znalezienia.
NWW obliczane z NWD
Najmniejsza wspólna wielokrotność jest najmniejszą dodatnią liczbą podzielną przez oba argumenty. Dla dodatnich liczb iloczyn NWD i NWW jest równy iloczynowi tych liczb. Aby ograniczyć ryzyko zbyt dużego wyniku, kalkulator najpierw dzieli pierwszy argument przez NWD, a dopiero potem mnoży przez drugi.
Dla 84 i 126 otrzymujemy (84 ÷ 42) × 126 = 252. NWW przydaje się przy szukaniu pierwszego wspólnego terminu cykli oraz wspólnego mianownika ułamków.
Skracanie ułamka i stosunku
Aby skrócić ułamek 84/126, dzielimy licznik i mianownik przez ich NWD, czyli 42. Otrzymujemy 2/3. Ten sam rachunek upraszcza stosunek 84 : 126 do 2 : 3. Po skróceniu obie nowe liczby nie mają już wspólnego dzielnika większego niż 1.
Kalkulator pokazuje kolejność zgodną z formularzem. Gdy wpiszesz 126 jako pierwszą liczbę, zobaczysz 3 : 2, choć NWD pozostanie 42. Stosunek opisuje relację uporządkowaną; zamiana stron zmienia jego znaczenie.
Liczby względnie pierwsze
Dwie liczby są względnie pierwsze, jeśli ich NWD wynosi 1. Nie oznacza to, że każda z nich musi być liczbą pierwszą. Przykładowo 8 i 15 są złożone, ale nie mają wspólnego czynnika pierwszego, więc NWD(8, 15) = 1.
Gdy kalkulator oznacza parę jako względnie pierwszą, stosunku nie można dalej skrócić, a NWW jest po prostu iloczynem liczb. Ta własność jest ważna w ułamkach, arytmetyce modularnej i zadaniach o cykliczności.
Lista wszystkich wspólnych dzielników
Każdy wspólny dzielnik dwóch liczb jest dzielnikiem ich NWD, a każdy dzielnik NWD dzieli oba argumenty. Dlatego zamiast przeszukiwać obie liczby kalkulator wyznacza dzielniki tylko dla otrzymanego NWD. Kandydaci występują parami: jeśli d dzieli g, to g/d także jest dzielnikiem.
Wyszukiwanie wystarczy prowadzić do pierwiastka kwadratowego z NWD, a znalezione pary uporządkować rosnąco. Przy wyjątkowo wielkim NWD strona pomija pełną listę po przekroczeniu limitu pracy, ale nadal wyświetla prawidłowy NWD. Zapobiega to zamrożeniu przeglądarki przez miliony prób.
Przykład dzielenia przedmiotów na grupy
Masz 84 niebieskie i 126 białych elementów. Chcesz utworzyć możliwie najwięcej identycznych zestawów, bez reszty i bez mieszania kolorów w licznikach. Liczba zestawów musi dzielić obie liczby. Największa możliwa liczba to NWD, czyli 42.
W każdym zestawie znajdą się 84 ÷ 42 = 2 niebieskie elementy oraz 126 ÷ 42 = 3 białe elementy. Skrócony stosunek 2 : 3 opisuje zatem zawartość jednego zestawu. To praktyczna interpretacja, a nie tylko formalny zapis.
Przykład wspólnego rytmu
Jedna czynność powtarza się co 84 sekundy, a druga co 126 sekund. Jeśli wystąpiły razem teraz, pierwszy ponowny wspólny moment nastąpi po NWW(84, 126), czyli po 252 sekundach. NWD nie odpowiada tutaj bezpośrednio na pytanie o czas spotkania, ale pozwala szybko obliczyć NWW.
W zadaniach tekstowych rozpoznaj kierunek pytania. „Największe równe grupy”, „najdłuższe jednakowe odcinki” i „maksymalny rozmiar bez reszty” często prowadzą do NWD. „Pierwszy wspólny termin” lub „najmniejsza wspólna liczba sztuk” zwykle prowadzą do NWW.
Rozkład na czynniki a Euklides
NWD można także znaleźć przez rozkład obu liczb na czynniki pierwsze i pomnożenie wspólnych czynników z mniejszymi wykładnikami. Dla małych liczb ta metoda dobrze pokazuje strukturę. Dla dużych argumentów pełny rozkład może jednak być znacznie trudniejszy niż kolejne dzielenia z resztą.
Algorytm Euklidesa nie musi znać czynników pierwszych. Operuje bezpośrednio na resztach i szybko redukuje liczby. Dlatego jest naturalnym wyborem w kalkulatorze, a taśma kroków pozwala sprawdzić proces bez ukrywania go za gotową odpowiedzią.
Zakres bezpiecznych liczb całkowitych
Formularz przyjmuje dodatnie liczby naturalne nie większe niż 9 007 199 254 740 991. Jest to największa liczba całkowita, którą JavaScript może reprezentować bez utraty jednostkowej dokładności w standardowym typie Number. Wpis z przecinkiem, kropką, minusem lub notacją wykładniczą jest odrzucany.
Nawet jeśli oba argumenty mieszczą się w zakresie, ich NWW może być większe. Kalkulator sprawdza możliwość mnożenia przed jego wykonaniem. W takim przypadku pokazuje komunikat o przekroczeniu bezpiecznego zakresu zamiast pozornie konkretnej, lecz zaokrąglonej liczby.
Jak sprawdzić odpowiedź ręcznie?
Po otrzymaniu NWD podziel przez niego obie liczby. Obie reszty powinny wynosić zero. Następnie sprawdź, czy skrócone ilorazy są względnie pierwsze; możesz uruchomić kalkulator ponownie dla tej pary i oczekiwać NWD równego 1.
Dla NWW sprawdź podzielność przez oba wejścia. Sama podzielność nie dowodzi jeszcze minimalności, ale połączenie z tożsamością NWD × NWW = a × b potwierdza rachunek dla dodatnich liczb. Każdy wiersz taśmy można również zweryfikować, mnożąc iloraz przez dzielnik i dodając resztę.
Najczęstsze pomyłki w zadaniach
Pierwszy błąd to pomylenie dzielnika z wielokrotnością. Dzielnik nie przekracza liczby, którą dzieli, natomiast wielokrotności rosną bez końca. Drugi błąd to uznanie ostatniej reszty zero za NWD. Odpowiedzią jest ostatni niezerowy dzielnik, nie zero.
Kolejna pomyłka polega na pominięciu największej liczby w sortowaniu dzielników albo dwukrotnym wpisaniu pierwiastka dla kwadratu. Kalkulator dodaje parę dzielników tylko wtedy, gdy jej elementy są różne. Zachowuje też kolejność argumentów wyłącznie w stosunku, nie w samej taśmie dzielenia.
Najczęstsze pytania o NWD
Czy kolejność wpisania liczb zmienia NWD?
Nie. NWD(a, b) jest taki sam jak NWD(b, a). Kolejność zmienia jedynie zapis skróconego stosunku pokazywanego przez stronę.
Czy NWD może być większy od mniejszej liczby?
Nie dla dodatnich argumentów. Wspólny dzielnik musi dzielić mniejszą liczbę, więc nie może jej przekraczać.
Co oznacza NWD równy 1?
Liczby są względnie pierwsze: nie mają wspólnego dodatniego dzielnika większego niż 1, choć same mogą być złożone.
Dlaczego kalkulator nie przyjmuje zera?
Ta strona celowo pracuje na dodatnich liczbach naturalnych, aby przykłady NWW, stosunku i listy dzielników miały jednoznaczną postać. Szkolne konwencje dla zera bywają omawiane osobno.
Czy mogę wpisać ułamek dziesiętny?
Nie. NWD w tym narzędziu dotyczy liczb naturalnych. Dla ułamków najpierw przedstaw wartości jako ilorazy liczb całkowitych.
Czy NWD i NWW są tym samym?
Nie. NWD jest największym wspólnym dzielnikiem, a NWW najmniejszą wspólną wielokrotnością. Łączy je podany wzór iloczynowy.