Nwd

NWD – Największy Wspólny Dzielnik – jest to największa liczba naturalna dzieląca każdą z dwóch lub więcej liczb całkowitych.

Największy wspólny dzielnik liczb a i b możemy zapisać jako nwd(a, b) lub NWD(a, b)

Jeżeli największym wspólnym dzielnikiem liczb a i b jest 1 to nazywamy te liczby względnie pierwszymi.
Przykładowo liczby 9 i 28. Zaraz dowiemy się dlaczego.

Zastosowanie największego wspólnego dzielnika:
> skracanie ułamków
> rozwiązywanie układów równań
> rozwiązywanie układów kongruencji
> obliczanie reszty z dzielenie dużych liczb

Co oznacza wspólny dzielnik?
Powiemy, że liczba całkowita a jest dzielnikiem liczby całkowitej b, gdy istnieje liczba całkowita c taka, że b = a c.
Kiedy tak będzie możemy skorzystać z zapisu a|b.
Natomiast wspólny dzielnik jest to jakaś liczba całkowita d, która dzieli obie te liczby. Wtedy skorzystamy z zapisu d = nwd (a, b)
Własność:
jeśli c|a i c|b to c|d

Największy wspólny dzielnik możemy obliczać dla dowolnej ilości liczb, możemy go również obliczyć dla zbioru. A mianowicie:
Największym wspólnym dzielnikiem zbioru liczb całkowitych A będzie liczba nieujemna c, która spełnia warunki:
dla każdego elementu a ze zbioru A zachodzi: c|a
Dla zbioru skończonego stosuje się oznaczenie

Ciekawostki:
> największym wspólnym dzielnikiem zbioru liczb pierwszych jest 1
> nie istnieje największy wspólny dzielnik zbioru liczb całkowitych
> zbiór pusty również ma największy wspólny dzielnik, a jest nim 0

Obliczanie największego wspólnego dzielnika:

Sposób 1. Czyli tak jak robiliśmy to w szkole.
Rozkład na czynniki pierwsze. Przykładowo obliczmy największy wspólny dzielnik liczb 18 i 84.
Najpierw rozłóżmy liczbę 18 na czynniki pierwsze.
18 | 2
9 | 3
3 | 3
1 |
Teraz to samo zrobimy z liczbą 84.
84 | 2
42 | 2
21 | 3
7 | 7
1 |
Patrzymy jakie dzielniki się „pokrywają” w obu liczbach. Tutaj będzie to 2 oraz 3. Zatem ich iloczyn będzie największym wspólnym dzielnikiem naszych liczb.

Sposób 2. Algorytm Euklidesa.
Algorytm Euklidesa opiera się na dzieleniu z resztą, a dokładniej opiera się o fakt, że największy wspólny dzielnik dwóch liczb dzieli również ich różnicę. Zatem przykładowo największy wspólny dzielnik liczb 30 i 42 będzie równy największemu wspólnemu dzielnikowi liczb (42 – 30) i 30, zatem 8 i 30 i tak dalej. Odejmujemy mniejszą liczbę od większej do momentu aż liczby będą sobie równe.
Wygląda to tak:
obliczmy nwd (56, 32)
56 – 32 = 24
32 – 24 = 8
24 – 8 = 16
16 – 8 = 8
Mamy takie same liczby 8 i 8, zatem nwd (56, 32) = 8

Sposób 3. Sposób ten opiera się na wykorzystaniu funkcji modulo (reszta z dzielenia), Jest to równoważny sposób, który wykorzystuje Algorytm Euklidesa. Jest jednak nieco szybszy.
Na tym samym przykładzie pokażę inny sposób. Moim zdaniem jest lepszy, bo zajmuje mniej miejsca oraz będzie się bardziej sprawdzał przy dużych liczbach.
chcemy obliczyć nwd (18, 84)
Bierzemy większą liczbę i zapisujemy ją jako wielokrotność mniejszej liczby plus reszta.
84 = 4 18 + 12
teraz to samo z mniejszą liczbą, zapisujemy ją jako wielokrotność poprzedniej reszty plus nowa reszta.
18 = 1 12 + 6
Kontynuujemy aż reszta będzie równa 0.
12 = 2 6 + 0
Otrzymaliśmy resztę 0 zatem nwd będzie równe ostatniej niezerowej reszcie. A mianowicie nwd (18, 84) = 6

Ta sama metoda na przykładzie większych liczb.
nwd (1710, 276)
1710 = 6 276 + 54
276 = 5 54 + 6
54 = 9 6 + 0
Zatem nwd (1710, 276) = 6

Przykład obliczenia tą metodą największego wspólnego dzielnika trzech liczb.
nwd (42, 75, 130)
Jeżeli chcemy obliczyć największy wspólny dzielnik trzech liczb, najpierw obliczamy największy wspólny dzielnik dwóch liczb, a potem obliczamy największy wspólny dzielnik wyniku i trzeciej liczby. Możemy w ten sposób również obliczyć największy wspólny dzielnik więcej niż 3 liczb.
A mianowicie:
nwd (42, 75, 130) = nwd( nwd(42, 75) , 130)
Zacznijmy od nwd (42, 75)
75 = 1 42 + 33
42 = 1 33 + 9
33 = 3 9 + 6
9 = 1 6 + 3
6 = 2 3 + 0
Zatem nwd (42, 75) = 3

Teraz nwd (3, 130)
130 = 43 3 + 1
3 = 3 1 + 0
zatem nwd (3, 130) = 1

A więc ostatecznie nwd (42, 75, 130) = 1

Zadanie A. Przedstaw największy wspólny dzielnik liczb 476 i 840 w postaci ich kombinacji liniowej o współczynnikach całkowitych.
Rozwiązanie:
Zaczynamy od obliczenia największego wspólnego dzielnika tych liczb.
nwd (467,840)
840 = 1 467 + 364 (1) 364 = 840 – 1 467
467 = 1 364 + 112 (2) 112 = 467 – 1 364
364 = 3 112 + 28 (3) 28 = 364 – 3 112
112 = 4 28 + 0
nwd(467, 840) = 28
Teraz korzystając z poprzednich zapisów przedstawimy liczbę 28 w postaci kombinacji liniowej liczb 476 i 840. Dla ułatwienia ponumerowałam kroki. A mianowicie, nad znakiem równości zapisuję, z którego kroku wzięłam dane przejście:
(3) (2) (1)
28 = 364 – 3 112 = 364 – 3 (467 – 1 364) = 364 – 3 467 + 3 364 = -3 467 + 4 364 = -3 467 + 4 (840 – 1 467) = -3 467 + 4 840 – 4 467 = 4 840 – 7 467

Ostatecznie:
28 = 4 840 – 7 467

Spróbuj swoich sił w poniższych zadaniach:
Odpowiedzi znajdziesz na końcu wypracowania.

Zadanie 1.
Oblicz za pomocą szkolnej metody największy wspólny dzielnik liczb 72 i 88.

Zadanie 2.
Z pomocą Algorytmu Euklidesa oblicz największy wspólny dzielnik liczb 610 i 377

Zadanie 3.
Oblicz największy wspólny dzielnik liczb 1842 i 654 korzystając z trzeciego sposobu.

Zadanie 4.
Przedstaw największy wspólny dzielnik liczb z zadania 3 w postaci kombinacji liniowej tych liczb o współczynnikach całkowitych

Zadanie 5.*
Oblicz największy wspólny dzielnik liczb 1080, 792, 630, 561.

Wykorzystamy teraz Algorytm Euklidesa do policzenia trudniejszego typu zadań. A mianowicie.
Zadanie B. Podaj wszystkie możliwe wartość podanych wyrażeń, gdzie n jest liczbą naturalną.
a) nwd (n, n + 1)
b) nwd (2n + 1, 3n – 1)

Rozwiązanie:
a) nwd (n, n + 1) = nwd (n, n + 1 – n) = nwd (n, 1) = 1
b) nwd (2n + 1, 3n – 1) = nwd [2n + 1, 3n – 1 – (2n + 1)] = nwd [2n + 1, n – 2] = nwd [2n + 1 – (n – 2), n – 2] = nwd [n + 3, n – 2] = nwd [n + 3 – (n – 2), n – 2] =
= nwd [5, n – 2]
I teraz w zależności od n otrzymamy inny wynik.
Odpowiedź:
nwd(5, n – 2) = 5, gdy 5|(n-2) (5 dzieli n – 2)
nwd(5, n – 2) = 1, w przeciwnym przypadku (5 nie dzieli n – 2)

Rozwiązywanie kongruencji. Kongruencja oznacza przystawanie.
Przykład 1.
Podaj najmniejsze rozwiązanie dodatnie poniższej kongruencji.
10x – 21 10 (mod 17) porządkujemy poprzez dodanie 21 stronami
10x 31 (mod 17) oraz mnożymy, przez odwrotność 10
x 10-1 31 (mod 17)
teraz musimy zapisać największy wspólny dzielnik liczb 10 i 17 w postaci ich kombinacji liniowej o współczynnikach całkowitych. Zatem liczymy nwd(10, 17)
17 = 1 10 + 7
10 = 1 7 + 3
7 = 2 3 + 1
3 = 3 1 + 0
zatem nwd (10, 17) = 1 = 7 – 2 3 = 7 – 2 (10 – 1 7) = -2 10 + 3 7 = -2 10 + 3 (17 – 1 10) = 3 17 – 5 10
Patrzymy teraz jaka liczba całkowita 'stoi’ przy liczbie 10. Tą liczbą jest (-5), zatem wstawiamy -5 zamiast 10-1 w naszej kongruencji.
Mieliśmy: x 10-1 31 (mod 17)
i teraz mamy x -5 31 (mod 17)
zatem x -155 (mod 17)
ponieważ w treści zadania mamy powiedziane, że jako wynik musimy podać najmniejszą liczbę dodatnią, musimy teraz dodać do -155 liczbę 17 tyle razy aż otrzymamy najmniejszą możliwą liczbę dodatnią. A mianowicie będzie to
x -155 15 (mod 17)
Odpowiedź: x jest kongruentne z liczbą 15 modulo 17.
lub możemy powiedzieć: x przystaje modulo 17 do liczby 15.

Odpowiedzi do zadań.
Ad. 1 Odp.: nwd (72, 88) = 23 = 8
Ad. 2 Odp.: nwd (610, 377) = 1
Ad. 3. Odp.: nwd (1842, 654) = 6
Ad. 4. Odp.: 6 = 49 1842 – 138 654
Ad 5. Odp.: nwd (1080, 792, 630, 561) = 3