Co to NWD i NWW?

NWD - (największy wspólny dzielnik dwóch liczb)

NWD(20, 40) = 20

NWD(12, 13) = 1

NWD(90, 9) = 9

NWW - (największa wspólna wielokrotność dwóch liczb)

NWW(20, 40) = 40

NWW(12, 13) = 12⋅13 = 156

NWW(90, 9) = 90

NWD

Zauważmy, że jeżeli a>b, to NWD(a, b) ≤ a - b. (w przeciwnym razie, wiemy, że NWD(a, b) = NWD(b, a))

Co więcej, Euklides zobaczył, że jeśli a>b to NWD(a, b) = NWD(a, b - a)!

20 | 40

20 | 20

20 | 0

co robimy gdy któraś z liczb jest równa 0?

Zwracamy tą drugą (20)

12 | 13

12 | 1

11 | 1

10 | 1

9 | 1

[...]

1 | 1

1 | 0

90 | 9

81 | 9

72 | 9

63 | 9

54 | 9

[...]

9 | 9

9 | 0

Zamiast odejmowania można urzyć reszty z dzielenia (%) - jest szybciej.

NWW(a, b)= $\frac{ab}{NWD(a, b)}$

Dzięki temu wzorowi jesteśmy w stanie wyznaczać NWW w dosyć szybki sposób.

NWW(20, 40) = $\frac{20⋅40}{NWD(20, 40)}$ = $\frac{800}{20}$ = 40

NWW(12, 13) = $\frac{12⋅13}{NWD(12, 13)}$ = $\frac{156}{1}$ = 156

NWW(90, 9) = $\frac{90⋅9}{NWD(90, 9)}$ = $\frac{9⋅90}{9}$ = 90

NWD(, ) = 1

NWW(, ) = $\frac{1⋅1}{NWD(1, 1)}$ = $\frac{1}{1}$ = 1