Znajdowanie węzłów za pomocą algorytmu Euklidesa i faktoryzacji liczb pierwszych. Znajdowanie nok przez rozłożenie liczb na czynniki pierwsze Algorytm Euklidesa do znajdowania gcd

Rozważ dwa sposoby na znalezienie największego wspólnego dzielnika.

Wyszukiwanie przez faktoring

Pierwszym sposobem jest znalezienie największego wspólnego dzielnika przez rozłożenie podanych liczb na czynniki pierwsze.

Aby znaleźć NWD kilku liczb, wystarczy rozłożyć je na czynniki pierwsze i pomnożyć między sobą te z nich, które są wspólne dla wszystkich danych liczb.

Przykład 1 Znajdźmy GCD (84, 90).

Rozkładamy liczby 84 i 90 na czynniki pierwsze:

Tak więc podkreśliliśmy wszystkie wspólne czynniki pierwsze, pozostaje pomnożyć je między sobą: 1 2 3 = 6.

Więc gcd(84, 90) = 6.

Przykład 2 Znajdźmy GCD (15, 28).

Rozkładamy 15 i 28 na czynniki pierwsze:

Liczby 15 i 28 są względnie pierwsze, ponieważ ich największym wspólnym dzielnikiem jest jeden.

gcd (15, 28) = 1.

Algorytm Euklidesa

Druga metoda (inaczej nazywana metodą Euklidesa) polega na znalezieniu GCD przez kolejne dzielenie.

Najpierw przyjrzymy się tej metodzie jako zastosowanej tylko do dwóch podanych liczb, a następnie dowiemy się, jak zastosować ją do trzech lub więcej liczb.

Jeżeli większa z dwóch podanych liczb jest podzielna przez mniejszą, to liczba mniejsza będzie ich największym wspólnym dzielnikiem.

Przykład 1 Weźmy dwie liczby 27 i 9. Ponieważ 27 jest podzielne przez 9, a 9 jest podzielne przez 9, to 9 jest wspólnym dzielnikiem liczb 27 i 9. Ten dzielnik jest również największy, ponieważ 9 nie może być podzielne przez żadną liczbę, większą niż 9. Zatem NWD (27, 9) = 9.

W innych przypadkach do znalezienia największego wspólnego dzielnika dwóch liczb stosuje się następne zamówienie działania:

1. Z dwóch podanych liczb, większa liczba jest dzielona przez mniejszą.
2. Następnie mniejsza liczba jest dzielona przez resztę wynikającą z dzielenia jeszcze za mniej.
3. Ponadto pierwsza reszta jest dzielona przez drugą resztę, którą otrzymuje się dzieląc mniejszą liczbę przez pierwszą resztę.
4. Druga reszta jest dzielona przez trzecią, którą otrzymuje się dzieląc pierwszą resztę przez drugą i tak dalej.
5. W ten sposób dzielenie trwa do momentu, gdy reszta wynosi zero. Ostatni dzielnik będzie największym wspólnym dzielnikiem.

Przykład 2 Znajdźmy największy wspólny dzielnik liczb 140 i 96:

1) 140: 96 = 1 (pozostałe 44)

2) 96: 44 = 2 (pozostałe 8)

3) 44: 8 = 5 (pozostałe 4)

Ostatnim dzielnikiem jest 4, co oznacza gcd(140, 96) = 4.

Podział sekwencyjny można również zapisać w kolumnie:

Aby znaleźć największy wspólny dzielnik trzech lub więcej podanych liczb, zastosuj następującą procedurę:

1. Najpierw znajdź największy wspólny dzielnik dowolnych dwóch liczb z wielu zbiorów danych.
2. Następnie znajdujemy NWD znalezionego dzielnika i jakąś trzecią podaną liczbę.
3. Następnie znajdujemy NWD ostatniego znalezionego dzielnika i czwartej podanej liczby, i tak dalej.

Przykład 3 Znajdźmy największy wspólny dzielnik liczb 140, 96 i 48. Znaleźliśmy już NWD liczb 140 i 96 w poprzednim przykładzie (jest to liczba 4). Pozostaje znaleźć największy wspólny dzielnik liczby 4 i trzeciej podanej liczby - 48:

48 jest podzielne przez 4 bez reszty. Więc gcd(140, 96, 48) = 4.

Reprezentowanie liczby jako iloczynu liczb pierwszych nazywa się rozkładając tę ​​liczbę na czynniki pierwsze.

Na przykład wpis 110 = 2 5 11 wskazuje, że liczba 110 jest rozłożona na czynniki pierwsze 2, 5 i 11.

Ogólnie wszystko można rozłożyć na czynniki pierwsze numer złożony ponadto dowolną metodą uzyskuje się jeden i ten sam rozkład, jeśli nie bierze się pod uwagę kolejności czynników. Zatem reprezentacje liczby 110 jako iloczyn 2 · 5 · 11 lub iloczyn 5 · 2 · 11 są w istocie tym samym rozkładem liczby 110 na czynniki pierwsze.

Rozkładając liczby na czynniki pierwsze, korzystając ze znaków dzielenia przez 2, 3, 5 itd., przypomnijmy sobie sposób zapisywania rozkładu liczby na czynniki pierwsze. Rozłóżmy na przykład liczbę 720 na czynniki pierwsze. Liczba 720 jest podzielna przez 2. Stąd 2 jest jednym z czynników pierwszych w rozkładzie liczby 720. Podziel 720 przez 2. Liczba 2 jest zapisywana jako na prawo od znaku równości, a iloraz 360 zapisujemy pod liczbą 720. Liczba 360 podzielona przez 2, otrzymamy 180. Podziel 180 przez 2, otrzymamy 90, podzielmy 90 przez 2, otrzymamy 45, podzielimy 45 przez 3, otrzymujemy 15, dzielimy 15 przez 3, otrzymujemy 5. Liczba 5 jest liczbą pierwszą, po podzieleniu przez 5 otrzymujemy 1. Rozkład na czynniki jest zakończony.

720 = 2 2 2 2 3 3 5

Zwyczajowo zastępuje się iloczyn identycznych czynników potęgą: 720 = 5. Taka reprezentacja liczby 720 nazywa się widok kanoniczny ten numer.

Rozkład liczby na czynniki pierwsze służy do znalezienia ich największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności.

Znajdź na przykład największy wspólny dzielnik i najmniejszą wspólną wielokrotność liczb 3600 i 288.

Reprezentujmy każdą z tych liczb w Forma kanoniczna.

3600 = 2 2 2 2 3 3 5 5 = ; 288 = 2 2 2 2 2 3 3 =

W rozłożeniu na czynniki pierwsze największego wspólnego dzielnika liczb 3600 i 288 wszystkie wspólne proste mnożenie, które są zawarte w rozwinięciach danych liczb, a każda z nich musi być wzięta z najniższy wskaźnik z którym wchodzi w oba rozszerzenia. Dlatego rozszerzenie największego wspólnego dzielnika liczb 3600 i 288 będzie obejmować czynniki i . Więc D (3600? 288) = · = 144.

Rozkład na czynniki pierwsze najmniejszej wspólnej wielokrotności 3600 i 288 musi obejmować wszystkie zawarte czynniki pierwsze w co najmniej jednym z rozwinięć liczb 3600 i 288, a każdy z nich musi być wzięty z najwyższym wynikiem, zawarte w obu rozszerzeniach tych liczb. Zatem rozwinięcie najmniejszej wspólnej wielokrotności 3600 i 288 będzie uwzględniało czynniki , , 5. Stąd,

K (3600, 288) = 5 = 7200.

Ogólnie, aby znaleźć największy wspólny dzielnik podanych liczb:

2) Tworzymy iloczyn czynników pierwszych wspólnych dla wszystkich podanych liczb, a każda z nich jest brana z najmniejszym wykładnikiem, z którym wchodzi we wszystkie rozwinięcia tych liczb;

3) Znajdujemy wartość tego produktu - będzie to największy wspólny dzielnik tych liczb.

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

1) Każdą podaną liczbę przedstawiamy w formie kanonicznej;

2) Tworzymy iloczyn ze wszystkich czynników pierwszych, które są w rozwinięciach tych liczb, i każdy jest brany z największym wykładnikiem, z którym wchodzi we wszystkie rozwinięcia tych liczb;

3) Znajdujemy wartość tego produktu - będzie to najmniejsza wspólna wielokrotność tych liczb.

Numer biletu 45. Najmniejsza wspólna wielokrotność liczb. Jego właściwości i metody znajdowania. Przykłady.

Obliczanie najmniejszej wspólnej wielokrotności (LCM) za pomocą gcd (najmniejszego wspólnego dzielnika)

Jednym ze sposobów znalezienia najmniejszej wspólnej wielokrotności jest związek między LCM a GCD. Istniejąca zależność między LCM a NWD pozwala obliczyć najmniejszą wspólną wielokrotność dwóch dodatnich liczb całkowitych przez znany największy wspólny dzielnik. Odpowiednia formuła ma postać LCM(a, b)=a b: NWD(a, b) . Rozważ przykłady znalezienia LCM zgodnie z powyższym wzorem.

Przykład.

Znajdź najmniejszą wspólną wielokrotność dwóch liczb 126 oraz 70 .

Rozwiązanie.

W tym przykładzie a=126, b=70. Wykorzystajmy zależność między LCM a NWD wyrażoną wzorem LCM(a, b)=a b: NWD(a, b). Oznacza to, że najpierw musimy znaleźć największy wspólny dzielnik liczb 70 oraz 126 , po czym możemy obliczyć LCM tych liczb zgodnie z zapisanym wzorem.

Znajdźmy NWD(126, 70), używając algorytmu Euclid: 126=70 1+56, 70=56 1+14, 56=14 4, W konsekwencji, gcd(126, 70)=14.

Teraz znajdujemy wymaganą najmniejszą wspólną wielokrotność: LCM(126, 70)=126 70: MCM(126, 70)=126 70:14=630.

Odpowiadać:

LCM(126, 70)=630.

Przykład.

Co jest równe NOC(68, 34)?

Rozwiązanie.

Dlatego 68 podzielona w całości na 34 , następnie NWD(68, 34)=34. Teraz obliczamy najmniejszą wspólną wielokrotność: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.

Odpowiadać:

LCM(68, 34)=68.

Zauważ, że poprzedni przykład pasuje do następującej zasady znajdowania LCM dla dodatnich liczb całkowitych a oraz b: jeśli liczba a podzielony przez b, wtedy najmniejszą wspólną wielokrotnością tych liczb jest a.

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

Innym sposobem znalezienia najmniejszej wspólnej wielokrotności jest rozłożenie liczb na czynniki pierwsze. Jeśli zrobimy iloczyn wszystkich czynników pierwszych tych liczb, po czym wykluczymy z tego iloczynu wszystkie wspólne czynniki pierwsze, które występują w rozwinięciach tych liczb, to otrzymany iloczyn będzie równy najmniejszej wspólnej wielokrotności tych liczb.

Ogłoszona zasada znajdowania LCM wynika z równości LCM(a, b)=a b: NWD(a, b). Rzeczywiście, iloczyn liczb a oraz b jest równy iloczynowi wszystkich czynników biorących udział w rozwinięciach liczb a oraz b. Z kolei gcd(a, b) jest równy iloczynowi wszystkich czynników pierwszych, które są jednocześnie obecne w rozwinięciach liczb a oraz b(co jest opisane w sekcji dotyczącej znajdowania GCD przez rozłożenie liczb na czynniki pierwsze).

Weźmy przykład. Daj nam znać, że 75=3 5 5 oraz 210=2 3 5 7. Skomponuj iloczyn wszystkich czynników tych rozszerzeń: 2 3 3 5 5 5 7. Teraz wykluczamy z tego produktu wszystkie czynniki, które są również obecne w rozszerzeniu liczby 75 i w rozszerzeniu liczby 210 (takie czynniki to 3 oraz 5 ), wtedy produkt przyjmie formę 2 3 5 5 7. Wartość tego iloczynu jest równa najmniejszej wspólnej wielokrotności liczb 75 oraz 210 , to znaczy, LCM(75, 210)= 2 3 5 5 7=1 050.

Przykład.

Rozszerzanie liczb 441 oraz 700 na czynniki pierwsze, znajdź najmniejszą wspólną wielokrotność tych liczb.

Rozwiązanie.

Rozłóżmy liczby 441 oraz 700 dla czynników pierwszych:

dostajemy 441=3 3 7 7 oraz 700=2 2 5 5 7.

Teraz zróbmy iloczyn wszystkich czynników związanych z rozwinięciami tych liczb: 2 2 3 3 5 5 7 7 7. Wykluczmy z tego iloczynu wszystkie czynniki, które występują jednocześnie w obu rozszerzeniach (jest tylko jeden taki czynnik - jest to liczba 7 ): 2 2 3 3 5 5 7 7. W ten sposób, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Odpowiadać:

LCM(441, 700)= 44 100.

Nieco inaczej można sformułować zasadę znajdowania LCM za pomocą rozkładu liczb na czynniki pierwsze. Jeśli do czynników z ekspansji liczby a dodaj brakujące czynniki z rozszerzenia liczby b, to wartość otrzymanego iloczynu będzie równa najmniejszej wspólnej wielokrotności liczb a oraz b .

Weźmy na przykład te same liczby 75 oraz 210 , ich faktoryzacja jest następująca: 75=3 5 5 oraz 210=2 3 5 7. Do mnożników 3 , 5 oraz 5 z rozkładu liczby 75 2 oraz 7 z rozkładu liczby 210 , otrzymujemy produkt 2 3 5 5 7, którego wartość to NOC(75, 210).

Przykład.

Znajdź najmniejszą wspólną wielokrotność liczb 84 oraz 648 .

Rozwiązanie.

Najpierw otrzymujemy rozkład liczb 84 oraz 648 na czynniki pierwsze. Wyglądają na 84=2 2 3 7 oraz 648=2 2 2 3 3 3 3. Do mnożników 2 , 2 , 3 oraz 7 z rozkładu liczby 84 dodawanie brakujących czynników 2 , 3 , 3 oraz 3 z rozkładu liczby 648 , otrzymujemy produkt 2 2 2 3 3 3 3 7, co jest równe 4 536 . Zatem pożądana najmniejsza wspólna wielokrotność liczb 84 oraz 648 równa się 4 536 .

Odpowiadać:

LCM(84, 648)=4536.

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

Yandex.RTB R-A-339285-1

Algorytm Euklidesa do znajdowania GCD

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

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

a = 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

Podział możemy zakończyć, gdy rk + 1 = 0, w którym r k = gcd (a , b).

Przykład 1

64 oraz 48 .

Rozwiązanie

Wprowadźmy notację: a = 64 , b = 48 .

Na podstawie algorytmu Euclid dokonamy podziału 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 znaczy q2 = 3, a r 2 = 0 . Zatem liczba 16 jest największym wspólnym dzielnikiem liczb z warunku.

Odpowiadać: gcd(64, 48) = 16.

Przykład 2

Co to jest NWD liczb 111 oraz 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 oraz 432 wynosi 3 .

Odpowiadać: gcd(111, 432) = 3.

Przykład 3

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

Rozwiązanie

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

Odpowiadać: gcd(661, 113) = 1.

Znalezienie GCD 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 otrzymuje się przez rozkład tych dwóch liczb i są dla nich wspólne.

Przykład 4

Jeśli rozłożymy liczby 220 i 600 na czynniki pierwsze, otrzymamy dwa iloczyny: 220 = 2 2 5 11 oraz 600 = 2 2 2 3 5 5. Wspólne czynniki w tych dwóch produktach 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 oraz 96 .

Rozwiązanie

Znajdź wszystkie czynniki pierwsze liczb 72 oraz 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.

Odpowiadać: gcd(72, 96) = 24.

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

Znajdowanie GCD trzech lub więcej liczb

Niezależnie od liczby liczb, dla których musimy znaleźć NWD, zastosujemy ten sam algorytm, który polega na znalezieniu NWD dwóch kolejnych liczb. Algorytm ten opiera się na zastosowaniu następującego twierdzenia: NWD kilku liczb a 1 , a 2 , … , a k jest równa liczbie dk, który znajduje się w sekwencyjnym obliczaniu gcd (a 1 , a 2) = d 2, NWD (d 2 , a 3) = d 3 , NWD (d 3 , a 4) = d 4 , … , NWD (d k - 1 , a k) = d 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 Euclid 570 = 6 95 . To znaczy, że d 3 = GCD (6 , 570) = 6 .

Znajdź d 4 \u003d GCD (d 3, a 4) \u003d GCD (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 .

Odpowiadać:

A teraz spójrzmy na inny sposób obliczania GCD dla tych i innych 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.

Odpowiadać: gcd(78 , 294 , 570 , 36) = 6 .

Znajdowanie 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 oraz -n mają te same dzielniki.

Przykład 8

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

Rozwiązanie

Aby wykonać obliczenia, weźmy moduły liczb podanych w warunku. Będą to liczby 231 i 140. Ujmijmy to krótko: GCD (− 231 , − 140) = GCD (231, 140). Teraz zastosujmy algorytm Euklidesa do znalezienia czynników pierwszych 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) , to gcd liczb − 231 oraz − 140 równa się 7 .

Odpowiadać: 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ści bezwzględne, otrzymujemy GCD (− 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 tych trzech liczb. Okazuje się, że gcd (585 , 81 , 189) = gcd (-585 , 81 , - 189) = 9 .

Odpowiadać: GCD (-585, 81, - 189) = 9 .

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