Kalkulator węzłów i nok z rozwiązaniem. Znajdowanie NWD za pomocą algorytmu Euklidesa i korzystania z rozkładu na czynniki pierwsze

Kalkulator internetowy pozwala szybko znaleźć największy wspólny dzielnik i najmniejszą wspólną wielokrotność zarówno dwóch, jak i dowolnej innej liczby liczb.

Kalkulator do znajdowania GCD i LCM

Znajdź GCD i LOC

Znaleziono GCD i LOC: 5806

Jak korzystać z kalkulatora

  • Wprowadź liczby w polu wejściowym
  • Jeśli wprowadzisz nieprawidłowe znaki, pole wprowadzania zostanie podświetlone na czerwono
  • kliknij przycisk „Znajdź GCD i LCM”.

Jak wprowadzać liczby

  • Liczby wprowadza się oddzielając spacją, kropką lub przecinkiem
  • Długość wprowadzanych numerów nie jest ograniczona, więc znalezienie GCD i LCM długich liczb nie jest trudne

Co to są GCD i NOC?

Największy wspólny dzielnik kilka liczb to największa naturalna liczba całkowita, przez którą wszystkie liczby pierwotne są podzielne bez reszty. Największy wspólny dzielnik jest skracany jako GCD.
Najmniejsza wspólna wielokrotność kilka liczb jest najmniejsza liczba, która jest podzielna przez każdą z liczb pierwotnych bez reszty. Najmniejsza wspólna wielokrotność jest skracana jako NOC.

Jak sprawdzić, czy liczba jest podzielna przez inną liczbę bez reszty?

Aby dowiedzieć się, czy jedna liczba jest podzielna przez inną bez reszty, możesz skorzystać z niektórych właściwości podzielności liczb. Następnie łącząc je, można sprawdzić podzielność niektórych z nich i ich kombinacji.

Niektóre oznaki podzielności liczb

1. Test podzielności liczby przez 2
Aby ustalić, czy liczba jest podzielna przez dwa (czy jest parzysta), wystarczy spojrzeć na ostatnią cyfrę tej liczby: jeśli jest równa 0, 2, 4, 6 lub 8, to liczba jest parzysta, co oznacza, że ​​jest podzielna przez 2.
Przykład: ustalić, czy liczba 34938 jest podzielna przez 2.
Rozwiązanie: spójrz na ostatnią cyfrę: 8 oznacza, że ​​liczba jest podzielna przez dwa.

2. Test podzielności liczby przez 3
Liczba jest podzielna przez 3, gdy suma jej cyfr jest podzielna przez trzy. Zatem, aby ustalić, czy liczba jest podzielna przez 3, należy obliczyć sumę cyfr i sprawdzić, czy jest ona podzielna przez 3. Nawet jeśli suma cyfr jest bardzo duża, można powtórzyć ten sam proces jeszcze raz.
Przykład: ustalić, czy liczba 34938 jest podzielna przez 3.
Rozwiązanie: Liczymy sumę liczb: 3+4+9+3+8 = 27. 27 jest podzielne przez 3, co oznacza, że ​​liczba ta jest podzielna przez trzy.

3. Test podzielności liczby przez 5
Liczba jest podzielna przez 5, gdy jej ostatnią cyfrą jest zero lub pięć.
Przykład: ustalić, czy liczba 34938 jest podzielna przez 5.
Rozwiązanie: spójrz na ostatnią cyfrę: 8 oznacza, że ​​liczba NIE jest podzielna przez pięć.

4. Test podzielności liczby przez 9
Znak ten jest bardzo podobny do znaku podzielności przez trzy: liczba jest podzielna przez 9, gdy suma jej cyfr jest podzielna przez 9.
Przykład: ustalić, czy liczba 34938 jest podzielna przez 9.
Rozwiązanie: Liczymy sumę liczb: 3+4+9+3+8 = 27. 27 jest podzielne przez 9, co oznacza, że ​​liczba ta jest podzielna przez dziewięć.

Jak znaleźć GCD i LCM dwóch liczb

Jak znaleźć gcd dwóch liczb

Bardzo w prosty sposób Obliczanie największego wspólnego dzielnika dwóch liczb polega na znalezieniu wszystkich możliwych dzielników tych liczb i wybraniu największego z nich.

Rozważmy tę metodę na przykładzie znalezienia NWD(28, 36):

  1. Rozliczamy obie liczby na czynniki: 28 = 1,2,2,7, 36 = 1,2,2,3,3
  2. Znajdujemy wspólne czynniki, czyli takie, które mają obie liczby: 1, 2 i 2.
  3. Obliczamy iloczyn tych czynników: 1 2 2 = 4 - jest to największy wspólny dzielnik liczb 28 i 36.

Jak znaleźć LCM dwóch liczb

Istnieją dwa najczęstsze sposoby znajdowania najmniejszej wielokrotności dwóch liczb. Pierwsza metoda polega na tym, że możesz zapisać pierwsze wielokrotności dwóch liczb, a następnie wybrać spośród nich liczbę, która będzie wspólna dla obu liczb i jednocześnie najmniejsza. Drugim jest znalezienie gcd tych liczb. Rozważmy tylko to.

Aby obliczyć LCM, należy obliczyć iloczyn liczb pierwotnych, a następnie podzielić go przez wcześniej znaleziony GCD. Znajdźmy LCM dla tych samych liczb 28 i 36:

  1. Znajdź iloczyn liczb 28 i 36: 28,36 = 1008
  2. NWD(28, 36), jak już wiadomo, jest równe 4
  3. LCM(28, 36) = 1008 / 4 = 252 .

Znajdowanie GCD i LCM dla kilku liczb

Największy wspólny dzielnik można znaleźć dla kilku liczb, a nie tylko dwóch. W tym celu liczby, które należy znaleźć dla największego wspólnego dzielnika, rozkłada się na czynniki pierwsze, a następnie oblicza się iloczyn wspólnych czynników pierwszych tych liczb. Możesz także użyć poniższej relacji, aby znaleźć gcd kilku liczb: NWD(a, b, c) = NWD(NWD(a, b), c).

Podobna zależność dotyczy najmniejszej wspólnej wielokrotności: LCM(a, b, c) = LCM(LCM(a, b), c)

Przykład: znajdź GCD i LCM dla liczb 12, 32 i 36.

  1. Najpierw rozłóżmy liczby na czynniki: 12 = 1,2,2,3, 32 = 1,2,2,2,2,2, 36 = 1,2,2,3,3.
  2. Znajdźmy wspólne czynniki: 1, 2 i 2.
  3. Ich produkt da NWD: 1,2,2 = 4
  4. Teraz znajdźmy LCM: w tym celu najpierw znajdźmy LCM(12, 32): 12·32 / 4 = 96 .
  5. Aby znaleźć LCM wszystkich trzech liczb, musisz znaleźć GCD(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , GCD = 1,2 · 2 3 = 12.
  6. LCM(12, 32, 36) = 96,36 / 12 = 288.



















Wstecz Naprzód

Uwaga! Podglądy slajdów służą wyłącznie celom informacyjnym i mogą nie odzwierciedlać wszystkich funkcji prezentacji. Jeśli jesteś zainteresowany tę pracę, pobierz pełną wersję.

Z pojęciami największego wspólnego dzielnika (NWD) i najmniejszej wspólnej wielokrotności (LCM) uczniowie szkół średnich spotykają się już w szóstej klasie. Ten temat jest zawsze trudny do zrozumienia. Dzieci często mylą te pojęcia i nie rozumieją, dlaczego należy się ich uczyć. W ostatnio a w literaturze popularnonaukowej pojawiają się pojedyncze stwierdzenia, że ​​materiał ten powinien zostać wyłączony z programu szkolnego. Myślę, że nie jest to do końca prawdą i należy się tego uczyć, jeśli nie w klasie, to na zajęciach pozalekcyjnych podczas zajęć elementarnych, ponieważ przyczynia się to do rozwoju logicznego myślenia u dzieci w wieku szkolnym, zwiększając szybkość operacji obliczeniowych, i umiejętność rozwiązywania problemów pięknymi metodami.

Studiując temat „Dodawanie i odejmowanie ułamków za pomocą różne mianowniki„uczymy dzieci znajdować wspólny mianownik dwóch lub więcej liczb. Na przykład trzeba dodać ułamki 1/3 i 1/5. Uczniowie z łatwością potrafią znaleźć liczbę podzielną przez 3 i 5 bez reszty. To to liczba 15. Rzeczywiście, jeśli liczby są małe, to łatwo jest znaleźć ich wspólny mianownik, jeśli dobrze znasz tabliczkę mnożenia. Jedno z dzieci zauważa, że ​​ta liczba jest iloczynem liczb 3 i 5. Dzieci tak opinia, że ​​​​w ten sposób zawsze można znaleźć wspólny mianownik liczb. Na przykład odejmujemy ułamki 7/. Znajdźmy iloczyn liczb 18 i 24. Jest to równe 432 Otrzymaliśmy już dużą liczbę i jeśli potrzebne są dalsze obliczenia (szczególnie dla przykładów dla wszystkich działań), to prawdopodobieństwo błędu wzrasta, ale wzrasta najmniejsza znaleziona wspólna wielokrotność liczb (LCD). odpowiada najmniejszemu wspólnemu mianownikowi (LCD) - liczbie 72 - znacznie ułatwi obliczenia i doprowadzi do szybszego rozwiązania przykładu, a tym samym zaoszczędzi czas przeznaczony na wykonanie tego zadania, co odgrywa ważną rolę podczas wykonywania testów końcowych, testy zwłaszcza podczas oceny końcowej.

Studiując temat „Redukcja ułamków”, możesz poruszać się sekwencyjnie, dzieląc licznik i mianownik ułamka przez tę samą liczbę naturalną, używając znaków podzielności liczb, ostatecznie uzyskując ułamek nieredukowalny. Na przykład musisz zmniejszyć ułamek 128/344. Najpierw podziel licznik i mianownik ułamka przez liczbę 2, otrzymamy ułamek 64/172. Jeszcze raz podziel licznik i mianownik powstałego ułamka przez 2, otrzymamy ułamek 32/86. Podziel ponownie licznik i mianownik ułamka przez 2, otrzymamy ułamek nieredukowalny 16/43. Ale skrócenie ułamka można zrobić znacznie łatwiej, jeśli znajdziemy największy wspólny dzielnik liczb 128 i 344. GCD(128, 344) = 8. Dzieląc licznik i mianownik ułamka przez tę liczbę, natychmiast otrzymujemy ułamek nieredukowalny .

Trzeba pokazać dzieciom różne sposoby znajdowanie największego wspólnego dzielnika (GCD) i najmniejszej wspólnej wielokrotności (LCM) liczb. W prostych przypadkach wygodnie jest znaleźć największy wspólny dzielnik (GCD) i najmniejszą wspólną wielokrotność (LCD) liczb poprzez proste wyliczenie. Gdy liczby stają się coraz większe, można zastosować faktoryzację pierwszą. Podręcznik dla szóstej klasy (autor N.Ya. Vilenkin) pokazuje następującą metodę znajdowania największego wspólnego dzielnika (NWD) liczb. Rozłóżmy liczby na czynniki pierwsze:

  • 16 = 2*2*2*2
  • 120 = 2*2*2*3*5

Następnie z czynników wchodzących w skład rozwinięcia jednej z tych liczb skreślamy te, które nie wchodzą w rozwinięcie drugiej liczby. Iloczyn pozostałych czynników będzie największym wspólnym dzielnikiem tych liczb. W tym przypadku jest to liczba 8. Z własnego doświadczenia jestem przekonana, że ​​dla dzieci będzie bardziej zrozumiałe, jeśli w rozkładach liczb podkreślimy te same czynniki, a następnie w jednym z rozkładów znajdziemy iloczyn podkreślone czynniki. Jest to największy wspólny dzielnik tych liczb. W szóstej klasie dzieci są aktywne i dociekliwe. Możesz postawić im następujące zadanie: spróbuj zastosować opisaną metodę, aby znaleźć największy wspólny dzielnik liczb 343 i 287. Nie jest od razu oczywiste, jak rozłożyć je na czynniki pierwsze. A tutaj możesz opowiedzieć im o wspaniałej metodzie wymyślonej przez starożytnych Greków, która pozwala znaleźć największy wspólny dzielnik (NWD) bez rozkładania go na czynniki pierwsze. Ta metoda znajdowania największego wspólnego dzielnika została po raz pierwszy opisana w książce Euklidesa Elementy. Nazywa się to algorytmem euklidesowym. Składa się z następujących elementów: Najpierw podziel większą liczbę przez mniejszą. Jeśli uzyskana zostanie reszta, podziel mniejszą liczbę przez resztę. Jeśli resztę uzyskasz ponownie, podziel pierwszą resztę przez drugą. Kontynuuj dzielenie w ten sposób, aż reszta wyniesie zero. Ostatnim dzielnikiem jest największy wspólny dzielnik (NWD) tych liczb.

Wróćmy do naszego przykładu i dla przejrzystości zapisz rozwiązanie w formie tabeli.

Dywidenda Rozdzielacz Prywatny Reszta
343 287 1 56
287 56 5 7
56 7 8 0

Zatem gcd(344,287) = 7

Jak znaleźć najmniejszą wspólną wielokrotność (LCM) tych samych liczb? Czy jest na to jakiś sposób, który nie wymaga wcześniejszego rozkładu tych liczb na czynniki pierwsze? Okazuje się, że istnieje i to bardzo prosty sposób. Musimy pomnożyć te liczby i podzielić iloczyn przez największy wspólny dzielnik (NWD), jaki udało nam się znaleźć. W w tym przykładzie iloczyn liczb wynosi 98441. Podziel go przez 7 i otrzymamy liczbę 14063. LCM(343,287) = 14063.

Jednym z trudnych tematów w matematyce jest rozwiązywanie problemów tekstowych. Musimy pokazać uczniom, w jaki sposób pojęcia największego wspólnego dzielnika (GCD) i najmniejszej wspólnej wielokrotności (LCM) można wykorzystać do rozwiązywania problemów, które czasami są trudne do rozwiązania. w zwykły sposób. W tym miejscu należy rozważyć z uczniami, wraz z zadaniami zaproponowanymi przez autorów podręcznika szkolnego, starożytne i zabawne zadania, które rozwijają ciekawość dzieci i zwiększają zainteresowanie studiowaniem tego tematu. Umiejętne opanowanie tych pojęć pozwala uczniom zobaczyć piękne rozwiązanie niestandardowego problemu. A jeśli nastrój dziecka poprawi się po rozwiązaniu dobrego problemu, jest to oznaka udanej pracy.

Zatem uczenie się w szkole takich pojęć jak „największy wspólny dzielnik (GCD)” i „najmniejsza wspólna wielokrotność (LCD)” liczb

Pozwala zaoszczędzić czas przeznaczony na realizację pracy, co prowadzi do znacznego wzrostu wolumenu wykonanych zadań;

Zwiększa szybkość i dokładność wykonywania operacji arytmetycznych, co prowadzi do znacznego zmniejszenia liczby błędów obliczeniowych;

Pozwala znaleźć piękne sposoby rozwiązywanie niestandardowych problemów tekstowych;

Rozwija ciekawość uczniów, poszerza ich horyzonty;

Stwarza warunki do wychowania wszechstronnej osobowości twórczej.

GCD jest największym wspólnym dzielnikiem.

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

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

Przykład znalezienia GCD:

Znajdźmy gcd liczb 315 i 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Zapiszmy czynniki wspólne obu liczb:

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

NWD(315, 245) = 5 * 7 = 35.

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

Znalezienie NOC

LCM jest najmniejszą wspólną wielokrotnością.

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

  • rozłóż liczby na czynniki pierwsze;
  • zapisz czynniki składające się na rozwinięcie jednej z liczb;
  • Dodajmy do nich brakujące czynniki z rozwinięcia drugiej liczby;
  • znajdź iloczyn otrzymanych czynników.

Przykład znalezienia LOC:

Znajdźmy LCM liczb 236 i 328:

1. Rozłóżmy liczby na czynniki pierwsze:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Zapiszmy czynniki biorące udział w rozwinięciu jednej z liczb i dodajmy do nich brakujące czynniki z rozwinięcia drugiej liczby:

2; 2; 59; 2; 41.

3. Znajdź iloczyn uzyskanych czynników:

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

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

Aby znaleźć GCD (największy wspólny dzielnik) dwóch liczb, należy:

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. Podziel podane liczby na czynniki pierwsze.

2. Rozwinięcie jednej z nich uzupełnia się o te czynniki rozwinięcia drugiej liczby, które nie występują w rozwinięciu pierwszej.

3. Oblicz iloczyn uzyskanych czynników.

Odtąd będziemy zakładać, że przynajmniej jedna z tych liczb jest różna od zera. Jeśli wszystkie podane liczby są równe zero, to ich wspólnym dzielnikiem jest dowolna liczba całkowita, a ponieważ liczb całkowitych jest nieskończenie wiele, nie można mówić o największej z nich. Dlatego nie możemy mówić o największym wspólnym dzielniku liczb, z których każdy jest równy zero.

Teraz możemy dać określenie największego wspólnego dzielnika dwie liczby.

Definicja.

Największy wspólny dzielnik dwie liczby całkowite to największa liczba całkowita dzieląca dwie dane liczby całkowite.

Aby krótko napisać największy wspólny dzielnik, często używany jest skrót GCD - Greatest Common Divisor. Również największy wspólny dzielnik dwóch liczb aib jest często oznaczany jako NWD(a, b).

Dajmy przykład największego wspólnego dzielnika (NWD) dwie liczby całkowite. Największym wspólnym dzielnikiem liczb 6 i –15 jest 3. Uzasadnijmy to. Zapiszmy wszystkie dzielniki liczby szóstej: ±6, ±3, ±1, a dzielnikami liczby −15 są liczby ±15, ±5, ±3 i ±1. Teraz możesz znaleźć wszystko wspólne dzielniki liczby 6 i -15 to liczby -3, -1, 1 i 3. Od -3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Wyznaczanie największego wspólnego dzielnika trzech i więcej integers jest podobne do określania gcd dwóch liczb.

Definicja.

Największy wspólny dzielnik trzy lub więcej liczb całkowitych to największa liczba całkowita dzieląca wszystkie podane liczby w tym samym czasie.

Największy wspólny dzielnik n liczb całkowitych będziemy oznaczać a 1 , a 2 , …, an jako NWD(a 1 , a 2 , …, a n) . Jeśli zostanie znaleziona wartość b największego wspólnego dzielnika tych liczb, wówczas możemy pisać NWD(a 1 , a 2 , …, a n)=b.

Jako przykład podamy gcd czterech liczb całkowitych -8, 52, 16 i -12, jest ono równe 4, czyli gcd(-8, 52, 16, -12)=4. Można to sprawdzić zapisując wszystkie dzielniki danych liczb, wybierając z nich wspólne i wyznaczając największy wspólny dzielnik.

Należy pamiętać, że największy wspólny dzielnik liczb całkowitych może być równy jednej z tych liczb. To stwierdzenie jest prawdziwe, jeśli wszystkie podane liczby są podzielne przez jedną z nich (dowód znajduje się w następnym akapicie tego artykułu). Na przykład NWD(15, 60, -45)=15. To prawda, ponieważ 15 dzieli zarówno liczbę 15, jak i liczbę 60 oraz liczbę -45 i nie ma wspólnego dzielnika liczb 15, 60 i -45 przekraczającego 15.

Szczególnie interesujące są tzw. liczby względnie pierwsze – liczby całkowite, których największy wspólny dzielnik jest równy jeden.

Własności największego wspólnego dzielnika, algorytm euklidesowy

Największy wspólny dzielnik ma wiele charakterystycznych wyników, innymi słowy, wiele właściwości. Teraz wymienimy główne właściwości największego wspólnego dzielnika (NWD), sformułowamy je w formie twierdzeń i od razu przedstawimy dowody.

Sformułujemy wszystkie właściwości największego wspólnego dzielnika dla dodatnich liczb całkowitych i rozważymy tylko dodatnie dzielniki tych liczb.

    Największy wspólny dzielnik liczb a i b jest równy największemu wspólnemu dzielnikowi liczb b i a, czyli gcd(a, b) = gcd(a, b) .

    Ta właściwość NWD wynika bezpośrednio z definicji największego wspólnego dzielnika.

    Jeżeli a jest podzielne przez b, to zbiór wspólnych dzielników liczb a i b pokrywa się ze zbiorem dzielników liczby b, w szczególności gcd(a, b)=b.

    Dowód.

    Dowolny wspólny dzielnik liczb aib jest dzielnikiem każdej z tych liczb, łącznie z liczbą b. Natomiast skoro a jest wielokrotnością b, to każdy dzielnik liczby b jest dzielnikiem liczby a ze względu na fakt, że podzielność ma właściwość przechodniości, zatem każdy dzielnik liczby b jest wspólny dzielnik liczb a i b. Dowodzi to, że jeśli a jest podzielne przez b, to zbiór dzielników liczb a i b pokrywa się ze zbiorem dzielników jednej liczby b. A ponieważ największym dzielnikiem liczby b jest sama liczba b, to największy wspólny dzielnik liczb aib jest również równy b, czyli gcd(a, b)=b.

    W szczególności, jeśli liczby a i b są równe, to gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. Na przykład NWD(132, 132)=132.

    Sprawdzona właściwość największego dzielnika pozwala nam znaleźć gcd dwóch liczb, gdy jedna z nich jest dzielona przez drugą. W tym przypadku GCD jest równe jednej z tych liczb, która jest podzielona przez inną liczbę. Na przykład NWD(8, 24)=8, ponieważ 24 jest wielokrotnością ośmiu.

    Jeżeli a=b·q+c, gdzie a, b, c i q są liczbami całkowitymi, to zbiór wspólnych dzielników liczb a i b pokrywa się ze zbiorem wspólnych dzielników liczb b i c, w szczególności gcd (a, b)=gcd (b, c) .

    Uzasadnijmy tę właściwość NWD.

    Ponieważ zachodzi równość a=b·q+c, to każdy wspólny dzielnik liczb aib dzieli także c (wynika to z własności podzielności). Z tego samego powodu każdy wspólny dzielnik b i c dzieli a. Zatem zbiór wspólnych dzielników liczb a i b pokrywa się ze zbiorem wspólnych dzielników liczb b i c. W szczególności największy z tych wspólnych dzielników również musi się pokrywać, to znaczy, że następująca równość GCD(a, b) = NWD(b, c) musi być prawdziwa.

    Teraz sformułowamy i udowodnimy twierdzenie, które jest Algorytm euklidesowy. Algorytm Euclid pozwala znaleźć GCD dwóch liczb (patrz znajdowanie GCD za pomocą algorytmu Euclid). Ponadto algorytm Euklidesa pozwoli nam udowodnić następujące właściwości największego wspólnego dzielnika.

    Przed podaniem sformułowania twierdzenia zalecamy odświeżenie pamięci o twierdzeniu z części teoretycznej, która stwierdza, że ​​dywidenda a może być przedstawiona jako b q + r, gdzie b jest dzielnikiem, q jest liczbą całkowitą zwaną niepełnym ilorazem, oraz r jest liczbą całkowitą spełniającą warunek, zwaną resztą.

    Niech więc szereg równości będzie prawdziwy dla dwóch niezerowych dodatnich liczb całkowitych a i b

    kończąc, gdy r k+1 =0 (co jest nieuniknione, ponieważ b>r 1 >r 2 >r 3 , ... jest ciągiem malejących liczb całkowitych, a szereg ten nie może zawierać więcej niż skończoną liczbę liczb dodatnich), wówczas r k – jest to największy wspólny dzielnik liczb a i b, czyli r k = gcd(a, b) .

    Dowód.

    Najpierw udowodnijmy, że r k jest wspólnym dzielnikiem liczb aib, a następnie pokażemy, że r k jest nie tylko dzielnikiem, ale największym wspólnym dzielnikiem liczb aib.

    Po zapisanych równościach będziemy poruszać się od dołu do góry. Z ostatniej równości możemy powiedzieć, że r k−1 jest podzielne przez rk. Biorąc pod uwagę ten fakt, a także poprzednią własność NWD, przedostatnia równość r k−2 =r k−1 ·q k +r k pozwala stwierdzić, że r k−2 jest podzielne przez r k, gdyż r k−1 jest podzielne przez r k oraz r k jest podzielne przez r k. Przez analogię z trzeciej równości od dołu wnioskujemy, że r k−3 jest podzielne przez rk . I tak dalej. Z drugiej równości wynika, że ​​b jest podzielne przez rk, a z pierwszej równości wynika, że ​​a jest podzielne przez rk. Dlatego r k jest wspólnym dzielnikiem liczb a i b.

    Pozostaje udowodnić, że r k = NWD(a, b) . Wystarczy bowiem pokazać, że dowolny wspólny dzielnik liczb a i b (oznaczmy go r 0 ) dzieli r k .

    Po pierwotnych równościach będziemy poruszać się od góry do dołu. Z poprzedniej własności wynika, że ​​z pierwszej równości r 1 jest podzielne przez r 0 . Następnie z drugiej równości otrzymujemy, że r 2 jest podzielne przez r 0 . I tak dalej. Z ostatniej równości wynika, że ​​r k jest podzielne przez r 0 . Zatem r k = NWD(a, b) .

    Z rozważanej własności największego wspólnego dzielnika wynika, że ​​zbiór wspólnych dzielników liczb a i b pokrywa się ze zbiorem dzielników największego wspólnego dzielnika tych liczb. Ten wniosek z algorytmu Euklidesa pozwala nam znaleźć wszystkie wspólne dzielniki dwóch liczb jako dzielniki gcd tych liczb.

    Niech a i b będą liczbami całkowitymi, które nie są jednocześnie równe zeru, wówczas istnieją liczby całkowite u 0 i v 0, to równość GCD(a, b)=a·u 0 +b·v 0 jest prawdziwa. Ostatnia równość jest liniowym przedstawieniem największego wspólnego dzielnika liczb aib, równość ta nazywana jest relacją Bezouta, a liczby u 0 i v 0 nazywane są współczynnikami Bezouta.

    Dowód.

    Korzystając z algorytmu Euklidesa, możemy napisać następujące równości

    Z pierwszej równości mamy r 1 =a−b·q 1 i oznaczając 1=s 1 oraz −q 1 =t 1, równość ta przyjmuje postać r 1 =s 1 ·a+t 1 ·b, oraz liczby s 1 i t 1 są liczbami całkowitymi. Następnie z drugiej równości otrzymujemy r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b. Oznaczając −s 1 ·q 2 =s 2 i 1−t 1 ·q 2 =t 2, ostatnią równość można zapisać jako r 2 = s 2 ·a+t 2 ·b, a s 2 i t 2 są liczbami całkowitymi (ponieważ suma, różnica i iloczyn liczb całkowitych jest liczbą całkowitą). Podobnie z trzeciej równości otrzymujemy r 3 =s 3 ·a+t 3 ·b, z czwartej równości r 4 =s 4 ·a+t 4 ·b i tak dalej. Wreszcie r k =s k ·a+t k ·b, gdzie s k i t k są liczbami całkowitymi. Ponieważ r k =NWD(a, b) , i oznaczając s k =u 0 i t k =v 0 , otrzymujemy liniową reprezentację NWD o wymaganej postaci: NWD(a, b)=a·u 0 +b·v 0 .

    Jeśli m jest dowolną liczbą naturalną, to NWD(m a, m b)=m NWD(a, b).

    Uzasadnienie tej własności największego wspólnego dzielnika jest następujące. Jeśli pomnożymy przez m obie strony każdej równości algorytmu euklidesowego, otrzymamy, że GCD(m·a, m·b)=m·r k , a r k to GCD(a, b) . Stąd, NWD(m a, m b)=m NWD(a, b).

    Metoda znajdowania NWD za pomocą rozkładu na czynniki pierwsze opiera się na własności największego wspólnego dzielnika.

    Niech p będzie zatem dowolnym wspólnym dzielnikiem liczb aib gcd(a:p, b:p)=gcd(a, b):p, w szczególności, jeśli p=NWD(a, b) mamy gcd(a:gcd(a, b), b:gcd(a, b))=1, to znaczy, że liczby a:NWD(a, b) i b:GCD(a, b) są względnie pierwsze.

    Ponieważ a=p·(a:p) i b=p·(b:p) , a także dzięki poprzedniej własności, możemy zapisać łańcuch równości w postaci NWD(a, b)=NWD(p (a:p), p (b:p))= p·GCD(a:p, b:p) , z czego wynika dowodzenie równości.

    Własność największego wspólnego dzielnika, którą właśnie udowodniliśmy, jest podstawą .

    Porozmawiajmy teraz o własności NWD, która redukuje problem znalezienia największego wspólnego dzielnika trzech lub więcej liczb do sekwencyjnego znajdowania NWD dwóch liczb.

    Największy wspólny dzielnik liczb a 1 , a 2 , …, a k jest równy liczbie d k , którą można znaleźć poprzez kolejne obliczenie NWD(a 1 , a 2)=d 2 , NWD(d 2 , a 3)= re 3 , NWD(d 3 , za 4)=d 4 , …, NWD(d k-1 , a k)=d k .

    Dowód opiera się na następstwie algorytmu Euklidesa. Wspólne dzielniki liczb a 1 i a 2 pokrywają się z dzielnikami d 2. Następnie wspólne dzielniki liczb a 1, a 2 i a 3 pokrywają się ze wspólnymi dzielnikami liczb d 2 i a 3, dlatego pokrywają się z dzielnikami d 3. Wspólne dzielniki liczb a 1, a 2, a 3 i a 4 pokrywają się ze wspólnymi dzielnikami d 3 i a 4, dlatego pokrywają się z dzielnikami d 4. I tak dalej. Wreszcie wspólne dzielniki liczb a 1, a 2, ..., a k pokrywają się z dzielnikami d k. A ponieważ największym dzielnikiem liczby d k jest sama liczba d k NWD(a 1 , a 2 , …, a k)=d k.

Na tym kończy się nasz przegląd podstawowych właściwości największego wspólnego dzielnika.

Referencje.

  • Vilenkin N.Ya. i inne. Klasa 6: podręcznik dla placówek kształcenia ogólnego.
  • Winogradow I.M. Podstawy teorii liczb.
  • Mikhelovich Sh.H. Teoria liczb.
  • Kulikov L.Ya. i inne. Zbiór problemów z algebry i teorii liczb: Seminarium dla studentów fizyki i matematyki. specjalności instytutów pedagogicznych.

Aby zrozumieć, jak obliczyć LCM, należy najpierw określić znaczenie terminu „wielokrotność”.


Wielokrotność A jest liczbą naturalną, która dzieli się przez A bez reszty. Zatem liczby będące wielokrotnością 5 można uznać za 15, 20, 25 i tak dalej.


Liczba dzielników określonej liczby może być ograniczona, ale istnieje nieskończona liczba wielokrotności.


Wspólna wielokrotność liczby naturalne- liczba, która jest przez nie podzielna bez reszty.

Jak znaleźć najmniejszą wspólną wielokrotność liczb

Najmniejsza wspólna wielokrotność (LCM) liczb (dwa, trzy lub więcej) to najmniejsza liczba naturalna, która dzieli się przez wszystkie te liczby.


Aby znaleźć LOC, możesz skorzystać z kilku metod.


W przypadku małych liczb wygodnie jest zapisać wszystkie wielokrotności tych liczb w jednym wierszu, aż znajdziesz wśród nich coś wspólnego. Wielokrotności oznacza się wielką literą K.


Na przykład wielokrotności liczby 4 można zapisać w następujący sposób:


K. (4) = (8,12, 16, 20, 24, ...)


K. (6) = (12, 18, 24, ...)


Zatem widać, że najmniejszą wspólną wielokrotnością liczb 4 i 6 jest liczba 24. Zapis ten wykonuje się w następujący sposób:


LCM(4, 6) = 24


Jeśli liczby są duże, znajdź wspólną wielokrotność trzech lub więcej liczb, wtedy lepiej zastosować inną metodę obliczenia LCM.


Aby wykonać zadanie, należy rozłożyć podane liczby na czynniki pierwsze.


Najpierw musisz zapisać rozkład największej liczby na linii, a poniżej - resztę.


W rozwinięciu każdej liczby może być inna ilość mnożniki.


Na przykład, rozłóżmy liczby 50 i 20 na czynniki pierwsze.




Przy rozwinięciu mniejszej liczby należy zaznaczyć czynniki, których brakuje przy rozwinięciu pierwszej największej liczby, a następnie dodać je do niej. W przedstawionym przykładzie brakuje dwójki.


Teraz możesz obliczyć najmniejszą wspólną wielokrotność 20 i 50.


LCM(20, 50) = 2 * 5 * 5 * 2 = 100


Zatem iloczyn czynników pierwszych więcej a czynniki drugiej liczby, które nie zostały uwzględnione w rozwinięciu większej liczby, będą najmniejszą wspólną wielokrotnością.


Aby znaleźć LCM trzech lub więcej liczb, należy je wszystkie rozłożyć na czynniki pierwsze, tak jak w poprzednim przypadku.


Jako przykład możesz znaleźć najmniejszą wspólną wielokrotność liczb 16, 24, 36.


36 = 2 * 2 * 3 * 3


24 = 2 * 2 * 2 * 3


16 = 2 * 2 * 2 * 2


Zatem tylko dwie dwójki z rozwinięcia szesnastu nie zostały uwzględnione w faktoryzacji większej liczby (jedna jest w rozwinięciu dwudziestu czterech).


Należy je zatem dodać do rozwinięcia większej liczby.


LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9


Istnieją szczególne przypadki wyznaczania najmniejszej wspólnej wielokrotności. Jeśli więc jedną z liczb można podzielić bez reszty przez inną, wówczas większa z tych liczb będzie najmniejszą wspólną wielokrotnością.


Na przykład LCM wynoszący dwanaście i dwadzieścia cztery to dwadzieścia cztery.


Jeśli konieczne jest znalezienie najmniejszej wspólnej wielokrotności liczb względnie pierwszych, które nie mają identycznych dzielników, wówczas ich LCM będzie równa ich iloczynowi.


Na przykład LCM (10, 11) = 110.