Dla dowolnych liczb naturalnych a i b zachodzi następująca równość: (*) a * b = NWD(a,b) * NWW(a,b) Stąd: NWD(a,b) = a * b / NWW(a,b) = 2028 / 156 = 13 Teraz jeszcze wytłumaczenie, dlaczego zawsze zachodzi równość (*) Otóż, każdą liczbę naturalną można przedstawić jednoznacznie w formie iloczynu liczb pierwszych.. n = d1 * d2 * d3 * ... * dk Zatem, mając dane liczby a i b przedstawiamy je w formie iloczynu liczb pierwszych: a = a1 * a2 * ... * ak b = b1 * b2 * ... * bl Teraz szukamy pewnych liczb (czynników), które występują w obu liczbach a i b. Iloczyn tych liczb oznaczamy jako d. Będzie to największy wspólny dzielnik. Pozostałe czynniki w zapisach obu liczb wymnażamy i dostajemy coś takiego: a = d * x b = d * y Najważniejsze w tym wszystkim jest to, że liczby x i y są względnie pierwsze (czyli NWD(x,y) = 1) W takim układzie NWD(a,b) = d oraz NWW(a,b) = d * x * y Teraz mamy: NWD(a,b) * NWW(a,b) = d * d * x * y = d * x * d * y = = (d * x) * (d * y) = a * b Przykład: a = 24 b = 90 a = 2 * 2 * 2 * 3 b = 2 * 3 * 3 * 5 d = 2 * 3 a = (2 * 3) * 2 * 2 b = (2 * 3) * 3 * 5 x = 2 * 2 = 4 y = 3 * 5 = 15 a = 6 * 4 b = 6 * 15 NWD(24,90) = 6 NWW(24,90) = 6 * 4 * 15 = 360
