Liczby Nod i Nok - największy wspólny dzielnik i najmniejsza wspólna wielokrotność kilku liczb. Nod i nok z trzech lub więcej liczb Przykłady definicji Nod

Definicja. Nazywa się największą liczbę naturalną, przez którą liczby a i b są podzielne bez reszty największy wspólny dzielnik (gcd) te liczby.

Znajdźmy największy wspólny dzielnik liczb 24 i 35.
Dzielnikami liczby 24 będą liczby 1, 2, 3, 4, 6, 8, 12, 24, a dzielnikami liczby 35 będą liczby 1, 5, 7, 35.
Widzimy, że liczby 24 i 35 mają tylko jeden wspólny dzielnik - liczbę 1. Takie liczby nazywane są względnie pierwsze.

Definicja. Liczby naturalne nazywamy względnie pierwsze jeśli ich największy wspólny dzielnik (gcd) wynosi 1.

Największy wspólny dzielnik (NWD) można znaleźć bez wypisywania wszystkich dzielników podanych liczb.

Rozkładając liczby 48 i 36 na czynniki, otrzymujemy:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Z czynników wchodzących w skład rozwinięcia pierwszej z tych liczb usuwamy te, które nie wchodzą w rozwinięcie drugiej liczby (tj. dwie dwójki).
Pozostają czynniki 2 * 2 * 3. Ich iloczyn wynosi 12. Ta liczba jest największym wspólnym dzielnikiem liczb 48 i 36. Znaleziono również największy wspólny dzielnik trzech lub więcej liczb.

Znaleźć Największy wspólny dzielnik

2) spośród czynników wchodzących w skład rozszerzenia jednej z tych liczb wykreślić te, które nie wchodzą w skład rozszerzenia innych liczb;
3) znaleźć iloczyn pozostałych czynników.

Jeśli wszystkie podane liczby są podzielne przez jedną z nich, to ta liczba jest podzielna Największy wspólny dzielnik podane liczby.
Na przykład największym wspólnym dzielnikiem 15, 45, 75 i 180 jest 15, ponieważ dzieli wszystkie inne liczby: 45, 75 i 180.

Najmniejsza wspólna wielokrotność (LCM)

Definicja. Najmniejsza wspólna wielokrotność (LCM) liczby naturalne a i b to najmniejsza liczba naturalna, która jest wielokrotnością zarówno a, jak i b. Najmniejszą wspólną wielokrotność (LCM) liczb 75 i 60 można znaleźć bez wypisywania wielokrotności tych liczb z rzędu. Aby to zrobić, rozkładamy 75 i 60 na proste czynniki: 75 \u003d 3 * 5 * 5 i 60 \u003d 2 * 2 * 3 * 5.
Wypisujemy czynniki zawarte w rozwinięciu pierwszej z tych liczb i dodajemy do nich brakujące czynniki 2 i 2 z rozwinięcia drugiej liczby (czyli łączymy czynniki).
Otrzymujemy pięć czynników 2 * 2 * 3 * 5 * 5, których iloczyn wynosi 300. Ta liczba jest najmniejszą wspólną wielokrotnością liczb 75 i 60.

Znajdź również najmniejszą wspólną wielokrotność trzech lub więcej liczb.

Do znaleźć najmniejszą wspólną wielokrotność kilka liczb naturalnych, potrzebujesz:
1) rozłożyć je na czynniki pierwsze;
2) wypisz czynniki zawarte w rozwinięciu jednej z liczb;
3) dodać do nich brakujące czynniki z rozwinięć pozostałych liczb;
4) znaleźć iloczyn otrzymanych czynników.

Zauważ, że jeśli jedna z tych liczb jest podzielna przez wszystkie inne liczby, to ta liczba jest najmniejszą wspólną wielokrotnością tych liczb.
Na przykład najmniejszą wspólną wielokrotnością 12, 15, 20 i 60 byłoby 60, ponieważ jest podzielna przez wszystkie podane liczby.

Pitagoras (VI wiek p.n.e.) i jego uczniowie badali kwestię podzielności liczb. Liczbę równą sumie wszystkich jej dzielników (bez samej liczby), nazywali liczbą doskonałą. Na przykład liczby 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) są idealne. Kolejne liczby doskonałe to 496, 8128, 33 550 336. Pitagorejczycy znali tylko trzy pierwsze liczby doskonałe. Czwarty - 8128 - stał się znany w I wieku. N. mi. Piąty - 33 550 336 - został znaleziony w XV wieku. Do 1983 roku znanych było już 27 liczb doskonałych. Ale do tej pory naukowcy nie wiedzą, czy istnieją nieparzyste liczby doskonałe, czy istnieje największa liczba doskonała.
Zainteresowanie starożytnych matematyków liczbami pierwszymi wynika z faktu, że każda liczba jest albo pierwszą, albo może być przedstawiona jako iloczyn liczb pierwszych, to znaczy liczby pierwsze są jak cegły, z których zbudowana jest reszta liczb naturalnych.
Zapewne zauważyłeś, że liczby pierwsze w szeregu liczb naturalnych występują nierównomiernie - w niektórych częściach szeregu jest ich więcej, w innych mniej. Ale im dalej posuwamy się w szeregu liczb, tym rzadsze są liczby pierwsze. Powstaje pytanie: czy istnieje ostatnia (największa) liczba pierwsza? Starożytny grecki matematyk Euklides (III wiek p.n.e.) w swojej książce „Początki”, która przez dwa tysiące lat była głównym podręcznikiem matematyki, udowodnił, że istnieje nieskończenie wiele liczb pierwszych, to znaczy za każdą liczbą pierwszą stoi parzysta liczba większa liczba pierwsza.
Aby znaleźć liczby pierwsze, inny grecki matematyk z tego samego czasu, Eratostenes, wymyślił taką metodę. Zapisał wszystkie liczby od 1 do jakiejś liczby, a następnie skreślił jednostkę, która nie jest ani liczbą pierwszą, ani złożoną, a następnie przekreślił przez jedynkę wszystkie liczby po 2 (liczby, które są wielokrotnościami 2, czyli 4, 6, 8 itd.). Pierwszą pozostałą liczbą po 2 było 3. Następnie po dwóch skreślono wszystkie liczby po 3 (liczby, które są wielokrotnościami 3, tj. 6, 9, 12 itd.). ostatecznie tylko liczby pierwsze pozostały nie przekreślone.

Aby znaleźć NWD (największy wspólny dzielnik) dwóch liczb, potrzebujesz:

2. Znajdź (podkreśl) wszystkie wspólne czynniki pierwsze w otrzymanych rozwinięciach.

3. Znajdź iloczyn wspólnych czynników pierwszych.

Aby znaleźć LCM (najmniejszą wspólną wielokrotność) dwóch liczb, potrzebujesz:

1. Rozłóż te liczby na czynniki pierwsze.

2. Uzupełnij ekspansję jednej z nich o te czynniki ekspansji drugiej liczby, których nie ma w ekspansji pierwszej.

3. Oblicz iloczyn otrzymanych współczynników.

Znalezienie GCD

NWD to największy wspólny dzielnik.

Aby znaleźć największy wspólny dzielnik kilku liczb:

• określić czynniki wspólne dla obu liczb;
• znaleźć iloczyn wspólnych czynników.

Przykład znalezienia GCD:

Znajdź NWD liczb 315 i 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Wypisz czynniki wspólne dla obu liczb:

3. Znajdź iloczyn wspólnych czynników:

gcd(315; 245) = 5 * 7 = 35.

Odpowiedź: NWD(315; 245) = 35.

Znalezienie NOC

LCM to najmniejsza wspólna wielokrotność.

Aby znaleźć najmniejszą wspólną wielokrotność kilku liczb:

• rozkładać liczby na czynniki pierwsze;
• wypisz czynniki zawarte w rozwinięciu jednej z liczb;
• dodaj do nich brakujące czynniki z rozwinięcia drugiej liczby;
• znajdź iloczyn otrzymanych czynników.

Przykład znalezienia NOC:

Znajdź LCM liczb 236 i 328:

1. Rozkładamy liczby na czynniki pierwsze:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Zapisz czynniki zawarte w rozwinięciu jednej z liczb i dodaj do nich brakujące czynniki z rozwinięcia drugiej liczby:

2; 2; 59; 2; 41.

3. Znajdź iloczyn otrzymanych czynników:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Odpowiedź: LCM(236; 328) = 19352.

Największy wspólny dzielnik to kolejny wskaźnik ułatwiający pracę z ułamkami. Bardzo często w wyniku obliczeń otrzymuje się ułamki o bardzo dużych wartościach licznika i mianownika. Możliwe jest stopniowe zmniejszanie takich liczb, ale jest to bardzo długie, więc łatwiej jest od razu znaleźć NWD i go zmniejszyć. Przyjrzyjmy się bliżej tematowi.

Co to jest NOD?

Największy wspólny dzielnik (NWD) szeregu liczb to największa liczba, przez którą każdą z liczb w szeregu można podzielić bez reszty.

Jak znaleźć NOD?

Aby znaleźć NWD, należy każdą z liczb rozłożyć na czynniki pierwsze i zaznaczyć część wspólną.

Nie wymyślili na to specjalnej formuły, ale istnieje algorytm obliczeniowy.

Podajmy przykład znajdowania największego wspólnego dzielnika dwóch liczb naturalnych: 540 i 252. Rozłóżmy 640 na czynniki pierwsze. Sekwencja działań jest następująca:

• Liczbę dzielimy przez najmniejszą możliwą liczbę pierwszą. Oznacza to, że jeśli liczbę można podzielić przez 2, 3 lub 5, musisz najpierw podzielić przez 5. Tylko po to, żeby się nie pomylić.
• Otrzymany wynik jest dzielony przez najmniejszą możliwą liczbę pierwszą.
• Powtarzamy dzielenie każdego otrzymanego wyniku, aż otrzymamy liczbę pierwszą.

Teraz przeprowadzimy tę samą procedurę w praktyce.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

Zapiszmy wynik jako równanie 540=2*2*3*3*3*5. Aby zapisać wynik, musisz pomnożyć ostatnią wynikową liczbę przez wszystkie dzielniki.

Zróbmy to samo z liczbą 252:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

Zapiszmy wynik: 252=2*2*3*3*7.

Każde rozszerzenie ma te same numery. Znajdźmy je, to są dwie liczby 2 i dwie liczby 3. Różnią się tylko 7 i 3 * 5.

Aby znaleźć NWD, musisz pomnożyć wspólne czynniki. Oznacza to, że w produkcie będą dwie dwójki i dwie trójki.

NWD=2*2*3*3=36

Jak można go używać?

Zadanie: skróć ułamek $$252\ponad540$$.

Znaleźliśmy już NWD dla tych dwóch liczb, teraz po prostu użyjemy już obliczonej wartości.

Zmniejszmy licznik i mianownik ułamka o 36 i otrzymamy odpowiedź.

$$(252\over540) =(7\over15)$$ - aby szybko zmniejszyć, wystarczy spojrzeć na rozwinięcie liczb.

Jeśli 540=2*2*3*3*3*5 i NWD=36=2*2*3*3, to 540 = 36*3*5. A jeśli podzielimy 540 przez 36, otrzymamy 3*5=15.

Bez GCD musielibyśmy pisać skróty w jednym długim wierszu. Ponadto zdarzają się przypadki, w których nie jest jasne, czy ułamek można w ogóle zmniejszyć. W takich sytuacjach w matematyce wymyślili rozkład liczb na czynniki pierwsze i NWD.

Czego się nauczyliśmy?

Dowiedzieliśmy się, jaki jest największy wspólny dzielnik pary liczb, zorientowaliśmy się, jak używać wskaźnika w praktyce, rozwiązaliśmy problem znalezienia NWD i wykorzystania NWD do zmniejszenia ułamków. Zdaliśmy sobie sprawę, że za pomocą NWD łatwiej i szybciej można zredukować ułamki objętościowe, znajdując NWD dla licznika i mianownika.

Kwiz tematyczny

Ocena artykułu

Średnia ocena: 4.3. Łączna liczba otrzymanych ocen: 204.

Jednym z zadań sprawiających problemy współczesnym uczniom, którzy są przyzwyczajeni do używania kalkulatorów wbudowanych w gadżety w miejscu i poza nim, jest znalezienie największego wspólnego dzielnika (NWD) dwóch lub więcej liczb.

Nie da się rozwiązać żadnego problemu matematycznego, jeśli nie wiadomo, o co właściwie pytamy. Aby to zrobić, musisz wiedzieć, co oznacza to lub inne wyrażenie. stosowane w matematyce.

Ogólne pojęcia i definicje

Potrzebuję wiedzieć:

1. Jeśli pewnej liczby można użyć do policzenia różnych przedmiotów, na przykład dziewięciu filarów, szesnastu domów, to jest to naturalne. Najmniejszy z nich będzie jeden.
2. Kiedy liczba naturalna jest podzielna przez inną liczbę naturalną, mówi się, że mniejsza liczba jest dzielnikiem większej.
3. Jeśli dwie lub więcej różnych liczb jest podzielnych przez pewną liczbę bez reszty, to mówią, że ta ostatnia będzie ich wspólnym dzielnikiem (OD).
4. Największa z OD nazywana jest największym wspólnym dzielnikiem (GCD).
5. W takim przypadku, gdy liczba ma tylko dwa dzielniki naturalne (siebie i jedynkę), nazywa się ją liczbą pierwszą. Najmniejszą z nich jest dwójka, poza tym jest to jedyna liczba parzysta w ich szeregu.
6. Jeśli dwie liczby mają maksymalny wspólny dzielnik równy jeden, to będą względnie pierwsze.
7. Liczbę, która ma więcej niż dwa dzielniki, nazywamy liczbą złożoną.
8. Proces, w którym zostaną znalezione wszystkie czynniki pierwsze, które po pomnożeniu przez siebie dadzą początkową wartość produktu w matematyce, nazywa się rozkładem na czynniki pierwsze. Co więcej, te same czynniki w ekspansji mogą wystąpić więcej niż jeden raz.

W matematyce akceptowane są następujące zapisy:

1. Dzielniki D (45) = (1; 3; 5; 9; 45).
2. OD (8;18) = (1;2).
3. NWD (8;18) = 2.

Różne sposoby na znalezienie GCD

Najłatwiej odpowiedzieć na pytanie jak znaleźć NOD gdy mniejsza liczba jest dzielnikiem większej. W tym przypadku będzie to największy wspólny dzielnik.

Na przykład NWD (15;45) = 15, NWD (48;24) = 24.

Ale takie przypadki w matematyce są bardzo rzadkie, dlatego w celu znalezienia NWD stosuje się bardziej złożone techniki, chociaż nadal zaleca się sprawdzenie tej opcji przed rozpoczęciem pracy.

Metoda rozkładu na czynniki pierwsze

Jeśli chcesz znaleźć GCD dwóch lub więcej różnych numerów, wystarczy rozłożyć każdy z nich na czynniki proste, a następnie przeprowadzić proces mnożenia tych z nich, które znajdują się w każdej z liczb.

Przykład 1

Zastanów się, jak znaleźć NWD 36 i 90:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

NWD (36;90) = 1*2*3*3 = 18.

Zobaczmy teraz, jak znaleźć to samo w przypadku trzech liczb, weźmy na przykład 54; 162; 42.

Wiemy już, jak rozłożyć 36, zajmijmy się resztą:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Zatem NWD (36;162;42) = 1*2*3 = 6.

Należy zauważyć, że zapisanie jednostki w rozkładzie jest całkowicie opcjonalne.

Rozważ sposób jak łatwo rozłożyć na czynniki, w tym celu po lewej stronie napiszemy potrzebną nam liczbę, a po prawej proste dzielniki.

Kolumny mogą być oddzielone znakiem podziału lub prostą pionową kreską.

1. 36 / 2 będziemy kontynuować proces podziału;
2. 18/2 dalej;
3. 9 / 3 i ponownie;
4. 3 / 3 jest teraz dość elementarne;
5. 1 - wynik jest gotowy.

Żądane 36 \u003d 2 * 2 * 3 * 3.

sposób euklidesowy

Ta opcja jest znana ludzkości od czasów starożytnej cywilizacji greckiej, jest znacznie prostsza i przypisywana jest wielkiemu matematykowi Euklidesowi, chociaż wcześniej stosowano bardzo podobne algorytmy. Ta metoda polega na użyciu następującego algorytmu, większą liczbę dzielimy z resztą przez mniejszą. Następnie dzielimy nasz dzielnik przez resztę i dalej postępujemy w ten sposób w kółko, aż podział się zakończy. Ostatnia wartość okaże się pożądanym największym wspólnym dzielnikiem.

Podajmy przykład użycia tego algorytmu:

Spróbujmy dowiedzieć się, który GCD dla 816 i 252:

1. 816/252 = 3, a reszta to 60. Teraz dzielimy 252 przez 60;
2. 252 / 60 = 4 reszta tym razem będzie równa 12. Kontynuujmy nasz okrągły proces, dzieląc sześćdziesiąt przez dwanaście;
3. 60 / 12 = 5. Ponieważ tym razem nie otrzymaliśmy żadnej reszty, wynik mamy gotowy, dwanaście będzie wartością, której szukamy.

A więc na koniec naszego procesu otrzymaliśmy NOD (816;252) = 12.

Akcje, jeśli konieczne jest określenie GCD, jeśli określono więcej niż dwie wartości

Już wymyśliliśmy, co zrobić w przypadku, gdy są dwie różne liczby, teraz nauczymy się, jak postępować, jeśli takie istnieją. 3 lub więcej.

Mimo pozornej złożoności zadanie to nie sprawi nam żadnych problemów. Teraz wybieramy dowolne dwie liczby i ustalamy dla nich szukaną wartość. Kolejnym krokiem jest znalezienie NWD dla otrzymanego wyniku oraz trzeciej z podanych wartości. Następnie ponownie postępujemy zgodnie ze znaną nam już zasadą dla czwartej piątej i tak dalej.

Wniosek

Tak więc, z pozorną wielką złożonością zadania postawionego przed nami na początku, w rzeczywistości wszystko jest proste, najważniejsze jest, aby móc przeprowadzić proces podziału bez błędów i trzymaj się jednego z dwóch algorytmów opisanych powyżej.

Chociaż obie metody są całkiem do przyjęcia, w szkole ogólnokształcącej znacznie częściej stosowana jest pierwsza metoda.. Wynika to z faktu, że rozkład na czynniki pierwsze będzie potrzebny podczas studiowania kolejnego tematu edukacyjnego - definicji największej wspólnej wielokrotności (LCM). Ale nadal warto ponownie zauważyć - użycie algorytmu Euclid w żaden sposób nie może być uznane za błędne.

Wideo

Za pomocą filmu możesz dowiedzieć się, jak znaleźć największy wspólny dzielnik.

Rozważmy dwie główne metody znajdowania NWD na dwa główne sposoby: za pomocą algorytmu Euclid i przez faktoring. Zastosujmy obie metody dla dwóch, trzech i więcej liczb.

Algorytm Euklidesa do znajdowania GCD

Algorytm Euclida ułatwia obliczenie największego wspólnego dzielnika dwóch liczb dodatnich. Podaliśmy sformułowania i dowód algorytmu Euklidesa w sekcji Największy wspólny dzielnik: wyznacznik, w sekcji Przykłady.

Istotą algorytmu jest konsekwentne przeprowadzanie dzielenia z resztą, podczas którego uzyskuje się szereg równości postaci:

za = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Możemy zakończyć dzielenie, kiedy rk + 1 = 0, w której r k = gcd (a , b).

Przykład 1

64 I 48 .

Rozwiązanie

Wprowadźmy zapis: a = 64 , b = 48 .

W oparciu o algorytm Euclid przeprowadzimy dzielenie 64 NA 48 .

Otrzymujemy 1, a resztę 16 . Okazuje się, że q 1 = 1, r 1 = 16.

Drugim krokiem jest podzielenie 48 do 16 otrzymujemy 3 . To jest q2 = 3, A r 2 = 0 . Zatem liczba 16 jest największym wspólnym dzielnikiem liczb z warunku.

Odpowiedź: gcd(64, 48) = 16.

Przykład 2

Co to jest NWD liczb 111 I 432 ?

Rozwiązanie

Dzielić 432 NA 111 . Zgodnie z algorytmem Euklidesa otrzymujemy łańcuch równości 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Zatem największy wspólny dzielnik liczb 111 I 432 jest 3 .

Odpowiedź: gcd(111, 432) = 3.

Przykład 3

Znajdź największy wspólny dzielnik 661 i 113 .

Rozwiązanie

Będziemy sekwencyjnie dzielić liczby i uzyskać NWD (661 , 113) = 1 . Oznacza to, że 661 i 113 są względnie pierwszymi liczbami. Moglibyśmy to rozgryźć przed rozpoczęciem obliczeń, gdybyśmy spojrzeli na tabelę liczb pierwszych.

Odpowiedź: gcd(661, 113) = 1.

Znalezienie NWD przez rozłożenie liczb na czynniki pierwsze

Aby znaleźć największy wspólny dzielnik dwóch liczb przez faktoring, konieczne jest pomnożenie wszystkich czynników pierwszych, które uzyskuje się przez rozłożenie tych dwóch liczb i które są dla nich wspólne.

Przykład 4

Jeśli rozłożymy liczby 220 i 600 na czynniki pierwsze, otrzymamy dwa produkty: 220 = 2 2 5 11 I 600 = 2 2 2 3 5 5. Wspólne czynniki w tych dwóch iloczynach to 2 , 2 i 5 . Oznacza to, że NOD (220, 600) = 2 2 5 = 20.

Przykład 5

Znajdź największy wspólny dzielnik liczb 72 I 96 .

Rozwiązanie

Znajdź wszystkie czynniki pierwsze liczb 72 I 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Wspólne czynniki pierwsze dla dwóch liczb: 2 , 2 , 2 i 3 . Oznacza to, że NOD (72, 96) = 2 2 2 3 = 24.

Odpowiedź: gcd(72, 96) = 24.

Reguła znajdowania największego wspólnego dzielnika dwóch liczb opiera się na własnościach największego wspólnego dzielnika, zgodnie z którymi gcd (m a 1 , mb 1) = m gcd (a 1 , b 1) , gdzie m jest dowolną dodatnią liczbą całkowitą .

Znalezienie NWD trzech lub więcej liczb

Niezależnie od liczby liczb, dla których musimy znaleźć NWD, będziemy postępować według tego samego algorytmu, który polega na znalezieniu NWD dwóch kolejnych liczb. Algorytm ten opiera się na zastosowaniu następującego twierdzenia: NWD kilku liczb za 1 , za 2 , … , za k jest równa liczbie dk, który znajduje się w sekwencyjnym obliczeniu gcd (za 1 , za 2) = re 2, NWD (re 2 , za 3) = re 3 , NWD (re 3 , za 4) = re 4 , … , NWD (re k - 1 , za k) = re k .

Przykład 6

Znajdź największy wspólny dzielnik czterech liczb 78 , 294 , 570 i 36 .

Rozwiązanie

Wprowadźmy zapis: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Zacznijmy od znalezienia NWD liczb 78 i 294: d2= GCD (78 , 294) = 6 .

Teraz zacznijmy szukać d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Zgodnie z algorytmem Euklidesa 570 = 6 95 . To znaczy, że re 3 = GCD (6 , 570) = 6 .

Znajdź d 4 \u003d NWD (d 3, a 4) \u003d NWD (6, 36) . 36 jest podzielna przez 6 bez reszty. To pozwala nam uzyskać d4= GCD (6 , 36) = 6 .

d4 = 6, czyli GCD (78 , 294 , 570 , 36) = 6 .

Odpowiedź:

A teraz spójrzmy na inny sposób obliczania NWD dla tych i więcej liczb. Możemy znaleźć gcd, mnożąc wszystkie wspólne czynniki pierwsze liczb.

Przykład 7

Oblicz gcd liczb 78 , 294 , 570 i 36 .

Rozwiązanie

Rozłóżmy te liczby na czynniki pierwsze: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

Dla wszystkich czterech liczb wspólnymi czynnikami pierwszymi będą liczby 2 i 3.

Okazuje się, że NOD (78, 294, 570, 36) = 2 3 = 6.

Odpowiedź: gcd(78, 294, 570, 36) = 6.

Znalezienie gcd liczb ujemnych

Jeśli mamy do czynienia z liczbami ujemnymi, możemy użyć modułów tych liczb, aby znaleźć największy wspólny dzielnik. Możemy to zrobić, znając właściwość liczb o przeciwnych znakach: liczby N I -N mają takie same dzielniki.

Przykład 8

Znajdź gcd ujemnych liczb całkowitych − 231 I − 140 .

Rozwiązanie

Do obliczeń weźmy moduły liczb podanych w warunku. Będą to liczby 231 i 140. Ujmijmy to krótko: GCD (− 231 , − 140) = NWD (231, 140). Teraz zastosujmy algorytm Euklidesa, aby znaleźć czynniki pierwsze dwóch liczb: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 i 42 = 7 6. Otrzymujemy, że gcd (231, 140) = 7 .

A ponieważ NOD (− 231 , − 140) = GCD (231 , 140) , a następnie gcd liczb − 231 I − 140 równa się 7 .

Odpowiedź: gcd (− 231 , − 140) = 7 .

Przykład 9

Określ gcd trzech liczb - 585, 81 i − 189 .

Rozwiązanie

Zastąpmy liczby ujemne na powyższej liście ich wartościami bezwzględnymi, otrzymamy NWD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Następnie rozkładamy wszystkie podane liczby na czynniki pierwsze: 585 = 3 3 5 13, 81 = 3 3 3 3 i 189 = 3 3 3 7. Czynniki pierwsze 3 i 3 są wspólne dla trzech liczb. Okazuje się, że gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

Odpowiedź: NWD (- 585 , 81 , - 189) = 9 .

Jeśli zauważysz błąd w tekście, zaznacz go i naciśnij Ctrl+Enter