# 9 NWD
Największy Wspólny Dzielnik (NWD)

Dla zadanych liczb a,b
chcemy znaleźć najwiekszą liczbę c taką, że dzieli ona zarówno a jak i b

. Na przykład NWD(18, 24) = 6 oraz NWD(6, 8) = 2.

## Obserwacja 1
Łatwo zauważyć, że każda liczba dzieli 0
, więc dla każdego a zachodzi **NWD(a,0)=a**

## Twierdzenie 1
Jeśli c
jest największym wspólnym dzielnikiem a,b oraz a≤b, to c jest też największym wspólnym dzielnikiem a−b,b.
Zapisane inaczej:
**NWD(a,b)=NWD(a−b,b)**

## Obserwacja 2
Weźmy a=23
oraz b=4. Wtedy z poprzedniego twierdzenia:
NWD(23,4)=NWD(19,4)=NWD(15,4)=NWD(11,4)=NWD(7,4)=NWD(3,4)
Zauważmy, że to samo możemy osiągnąć w jednej operacji zamiast odejmowania robiąc modulo, bo 23%4=3

## Twierdzenie 2
**NWD(a,b)=NWD(a%b,b)**

Algorytm (Euklidesa)
Mamy dwie zmienne a,b
. Zamieniamy je miejscami tak, aby w a była większa liczba, a w b mniejsza. Potem w pętli dopóki obie są różne od 0 robimy a=a%b, a następnie (skoro nasze nowe a jest mniejsze od b) zamieniami te zmienne miejscami. Kiedy jedna z tych zmiennych jest równa 0

, przerywamy pętlę i wypisujemy drugą liczbę jako NWD.

## NWW
Mając NWD umiemy obliczyć Najwiekszą Wspólną Wielokrotność (NWW) dwóch liczb ze wzoru:
**NWW(a,b)=(a⋅b)/NWD(a,b)**