Kalkulator NWD i NWW

NWD to największa dodatnia liczba całkowita, która dzieli wszystkie podane liczby bez reszty.

Użyj algorytmu Euklidesa do wydajnych obliczeń: dziel wielokrotnie i bierz resztę z dzielenia, aż uzyskasz 0.

NWW to najmniejsza dodatnia liczba całkowita podzielna przez wszystkie podane liczby.

Oblicz ją za pomocą rozkładu na czynniki pierwsze (biorąc najwyższe potęgi) lub według wzoru: NWW = (a × b) / NWD.

NWD (największy wspólny dzielnik) to największa liczba całkowita, która dokładnie dzieli każdą z podanych liczb, podczas gdy NWW (najmniejsza wspólna wielokrotność) to najmniejsza dodatnia liczba całkowita, przez którą każda z podanych liczb dzieli się bez reszty.

Działają one w przeciwnych kierunkach: NWD patrzy w dół na największy wspólny czynnik, a NWW patrzy w górę na najmniejszą wspólną wielokrotność. Dla 12 i 18 NWD wynosi 6, a NWW wynosi 36.

Według serwisu Wolfram MathWorld, NWD zapisuje się również jako gcd(a, b) lub (a, b), a określenie "największy wspólny czynnik" (HCF) to powszechny brytyjski synonim tej samej wielkości.

Algorytm Euklidesa znajduje NWD poprzez wielokrotne zastępowanie większej liczby resztą z dzielenia jej przez mniejszą, aż reszta wyniesie zero; ostatnia niezerowa reszta to NWD.

Dla 48 i 18: 48 = 2×18 + 12, potem 18 = 1×12 + 6, a następnie 12 = 2×6 + 0, więc nwd(48, 18) = 6.

Encyclopaedia Britannica zauważa, że ta metoda pochodzi z „Elementów” Euklidesa (ok. 300 r. p.n.e.), co czyni ją jednym z najstarszych algorytmów nadal w powszechnym użyciu. Jej wydajność sprawia, że biblioteki programistyczne stosują ją zamiast rozkładu na czynniki pierwszego dużych liczb.

Aby znaleźć NWW metodą rozkładu na czynniki pierwsze, rozłóż każdą liczbę na czynniki pierwsze, a następnie pomnoż każdy czynnik w najwyższej potędze występującej w dowolnym rozkładzie.

Dla 12 = 2²×3 oraz 18 = 2×3², weź 2² i 3², co daje NWW = 4×9 = 36. W przypadku NWD weź zamiast tego każdy wspólny czynnik w jego najniższej potędze: 2¹×3¹ = 6.

Khan Academy uczy tego porównania obok siebie, ponieważ uwidacznia ono kontrast między NWW a NWD. Rozkład na czynniki pierwsze jest intuicyjny dla małych liczb, ale wolniejszy niż algorytm Euklidesa dla dużych, ponieważ faktoryzacja jest obliczeniowo trudna.

Dla dowolnych dwóch dodatnich liczb całkowitych a i b zachodzi równość NWW(a, b) × NWD(a, b) = a × b. Tażsamość ta pozwala obliczyć jedną wielkość za pomocą drugiej: NWW(a, b) = (a × b) / NWD(a, b).

Dla 12 i 18 NWD wynosi 6, więc NWW = (12 × 18) / 6 = 216 / 6 = 36, i faktycznie 6 × 36 = 216 = 12 × 18.

Wolfram MathWorld dokumentuje tę relację jako standardowy pomost między tymi dwoma funkcjami. Zauważ, że wzór ten dotyczy tylko dwóch liczb; dla trzech lub więcej stosuje się go parami, zamiast zakładać, że iloczyn jest równy NWW × NWD.

Dla trzech lub więcej liczb zastosuj NWD lub NWW parami: oblicz wynik dla dwóch pierwszych, a następnie połącz go z kolejną liczbą i tak dalej.

Na przykład nwd(12, 18, 24) = nwd(nwd(12, 18), 24) = nwd(6, 24) = 6, a nww(4, 6, 8) = nww(nww(4, 6), 8) = nww(12, 8) = 24. Obie operacje są łączne, więc kolejność grupowania nie zmienia wyniku.

Ten kalkulator obsługuje grupy automatycznie, jednak skrót NWW×NWD = iloczyn nie rozszerza się na trzy lub więcej argumentów, na co zwraca uwagę Wolfram MathWorld.

Dwie liczby są względnie pierwsze (koprime), gdy ich NWD wynosi 1, co oznacza, że nie mają wspólnych czynników pierwszych, nawet jeśli żadna z nich nie jest liczbą pierwszą.

Na przykład nwd(8, 15) = 1: 8 = 2³ oraz 15 = 3×5 nie mają wspólnego czynnika pierwszego, więc są względnie pierwsze. Gdy liczby są względnie pierwsze, ich NWW jest równe ich iloczynowi; nww(8, 15) = 120 = 8×15.

Wolfram MathWorld zauważa, że wzajemna pierwszość leży u podstaw arytmetyki modularnej i kryptografii RSA, gdzie generowanie kluczy wymaga wykładnika względnie pierwszego z funkcją totient Eulera. Wzajemna pierwszość to własność pary, a nie pojedynczych liczb.

NWW i NWD pojawiają się daleko poza podręcznikami.

NWD upraszcza ułamki do najprostszej postaci (12/18 redukuje się do 2/3 po podzieleniu przez 6) i znajduje największe grupy o tej samej wielkości przy rozdzielaniu przedmiotów — a gdy te grupy zostaną ustalone, kalkulator silni oblicza sposoby ułożenia elementów w każdej z nich.

NWW znajduje momenty, w których powtarzające się zdarzenia się zbiegają, takie jak dwa autobusy odjeżdżające co 12 i 18 minut spotykające się ponownie po 36 minutach, a także wyznacza wspólny mianownik do dodawania ułamków.

Inżynierowie używają NWD przy projektowaniu przełożeń przekładni i pasków rozrządu, podczas gdy kryptografowie polegają na sprawdzaniu wzajemnej pierwszości (NWD = 1) podczas konfiguracji klucza RSA, co opisuje Encyclopaedia Britannica w swoim opracowaniu zastosowań teorii liczb.

Tożsamość Bézouta stwierdza, że dla liczb całkowitych a i b istnieją takie liczby całkowite x i y, że ax + by = nwd(a, b).

Dla 12 i 18 NWD wynosi 6, a jednym z rozwiązań jest 12×(−1) + 18×(1) = −12 + 18 = 6. Rozszerzony algorytm Euklidesa oblicza te współczynniki w trakcie wyznaczania NWD, co jest dokładnie sposobem znajdowania odwrotności modularnych w kryptografii.

Wolfram MathWorld oraz NIST Digital Library of Mathematical Functions traktują tożsamość Bézouta jako kamień węgielny elementarnej teorii liczb, ponieważ gwarantuje ona, że zawsze istnieje kombinacja liniowa równa NWD.

Kilku powszechnych błędów ludzie dopuszczają się przy obliczaniu NWW i NWD:

• Częstą pomyłką jest zamiana tych pojęć miejscami: NWD nigdy nie jest większe od najmniejszego argumentu, podczas gdy NWW nigdy nie jest mniejsze od największego argumentu, więc sprawdź swój wynik względem tej granicy.

• Innym błędem jest zakładanie, że NWW × NWD = iloczyn działa dla trzech lub więcej liczb, co nie jest prawdą.

• Ludzie zapominają również, że NWD i NWW są zdefiniowane dla dodatnich liczb całkowitych, a nie ułamków czy dziesiętnych, więc dane wejściowe muszą być liczbami całkowitymi.

• Wreszcie, gdy liczby są względnie pierwsze, pamiętaj, że NWD wynosi 1 (a nie 0), a NWW jest równe ich iloczynowi.

Weryfikacja za pomocą tożsamości NWW×NWD = a×b wychwytuje większość pomyłek przy dwóch liczbach.