Znalezienie wspólnej wielokrotności dwóch liczb. Sposoby znajdowania najmniejszej wspólnej wielokrotności, nok is i wszystkie wyjaśnienia

Drugi numer: b=

Separator cyfr Brak separatora spacji „ ´

Wynik:

Najmniejsza wspólna wielokrotność LCM( a,b)=468

Największy Liczba naturalna, przez którą liczby a i b są podzielne bez reszty, nazywa się Największy wspólny dzielnik(gcd) tych liczb. Oznaczane gcd(a,b), (a,b), gcd(a,b) lub hcf(a,b).

Najmniejsza wspólna wielokrotność(LCM) dwóch liczb całkowitych aib to najmniejsza liczba naturalna, która jest podzielna przez aib bez reszty. Oznaczone LCM(a,b) lub lcm(a,b).

Liczby całkowite a i b są nazywane względnie pierwsze jeśli nie mają wspólnych dzielników innych niż +1 i −1.

Największy wspólny dzielnik

Niech dane będą dwie liczby dodatnie a 1 i a 2 1). Należy znaleźć wspólny dzielnik tych liczb, tj. znaleźć taką liczbę λ , która dzieli liczby a 1 i a 2 w tym samym czasie. Opiszmy algorytm.

1) W tym artykule słowo liczba będzie oznaczać liczbę całkowitą.

Wynajmować a 1 ≥ a 2 i niech

gdzie m 1 , a 3 to pewne liczby całkowite, a 3 <a 2 (reszta z podziału a 1 na a 2 powinno być mniej a 2).

Udawajmy, że λ dzieli a 1 i a 2, w takim razie λ dzieli m 1 a 2 i λ dzieli a 1 −m 1 a 2 =a 3 (Twierdzenie 2 artykułu „Podzielność liczb. Znak podzielności”). Wynika z tego, że każdy wspólny dzielnik a 1 i a 2 jest wspólnym dzielnikiem a 2 i a 3 . Odwrotność jest również prawdziwa, jeśli λ wspólny dzielnik a 2 i a 3, w takim razie m 1 a 2 i a 1 =m 1 a 2 +a 3 są również podzielone na λ . Stąd wspólny dzielnik a 2 i a 3 jest również wspólnym dzielnikiem a 1 i a 2. Dlatego a 3 <a 2 ≤a 1 , to możemy powiedzieć, że rozwiązanie problemu znalezienia wspólnego dzielnika liczb a 1 i a 2 zredukowane do prostszego problemu znalezienia wspólnego dzielnika liczb a 2 i a 3 .

Jeśli a 3 ≠0, to możemy podzielić a 2 na a 3 . Następnie

gdzie m 1 i a 4 to niektóre liczby całkowite, ( a 4 reszta z dzielenia a 2 na a 3 (a 4 <a 3)). Z podobnego rozumowania dochodzimy do wniosku, że wspólne dzielniki liczb a 3 i a 4 jest tym samym, co wspólne dzielniki liczb a 2 i a 3 , a także ze wspólnymi dzielnikami a 1 i a 2. Dlatego a 1 , a 2 , a 3 , a 4 , ... liczby, które stale maleją, a ponieważ istnieje skończona liczba liczb całkowitych między nimi a 2 i 0, a następnie w pewnym kroku n, reszta z podziału a n wł a n+1 będzie równe zeru ( a n+2=0).

Każdy wspólny dzielnik λ liczby a 1 i a 2 jest również dzielnikiem liczb a 2 i a 3 , a 3 i a 4 , .... a n i a n+1 . Odwrotność jest również prawdziwa, wspólne dzielniki liczb a n i a n+1 są również dzielnikami liczb a n−1 i a n , .... , a 2 i a 3 , a 1 i a 2. Ale wspólny dzielnik a n i a n+1 to liczba a n+1 , ponieważ a n i a n+1 są podzielne przez a n+1 (pamiętaj, że a n+2=0). w konsekwencji a n+1 jest również dzielnikiem liczb a 1 i a 2 .

Zwróć uwagę, że liczba a n+1 to największy dzielnik liczby a n i a n+1 , od największego dzielnika a n+1 jest sobą a n+1 . Jeśli a n + 1 można przedstawić jako iloczyn liczb całkowitych, wtedy liczby te są również wspólnymi dzielnikami liczb a 1 i a 2. Numer a nazywa się n+1 Największy wspólny dzielnik liczby a 1 i a 2 .

Liczby a 1 i a 2 mogą być zarówno liczbami dodatnimi, jak i ujemnymi. Jeżeli jedna z liczb jest równa zeru, to największy wspólny dzielnik tych liczb będzie równy wartości bezwzględnej drugiej liczby. Największy wspólny dzielnik liczb zerowych nie jest zdefiniowany.

Powyższy algorytm nazywa się Algorytm Euklidesa znaleźć największy wspólny dzielnik dwóch liczb całkowitych.

Przykład znajdowania największego wspólnego dzielnika dwóch liczb

Znajdź największy wspólny dzielnik dwóch liczb 630 i 434.

Krok 1. Podziel liczbę 630 przez 434. Reszta to 196.
Krok 2. Podziel liczbę 434 przez 196. Reszta to 42.
Krok 3. Podziel liczbę 196 przez 42. Reszta to 28.
Krok 4. Podziel liczbę 42 przez 28. Reszta to 14.
Krok 5. Podziel liczbę 28 przez 14. Reszta to 0.

W kroku 5 reszta z dzielenia wynosi 0. Zatem największym wspólnym dzielnikiem liczb 630 i 434 jest 14. Zauważ, że liczby 2 i 7 są również dzielnikami liczb 630 i 434.

Liczby względnie pierwsze

Definicja 1. Niech największy wspólny dzielnik liczb a 1 i a 2 równa się jeden. Następnie te numery są wywoływane liczby względnie pierwsze które nie mają wspólnego dzielnika.

Twierdzenie 1. Jeśli a 1 i a 2 względnie pierwsze liczby i λ jakąś liczbę, a następnie dowolny wspólny dzielnik liczb λa 1 i a 2 jest również wspólnym dzielnikiem liczb λ oraz a 2 .

Dowód. Rozważ algorytm Euklidesa do znajdowania największego wspólnego dzielnika liczb a 1 i a 2 (patrz wyżej).

Z warunków twierdzenia wynika, że największy wspólny dzielnik liczb a 1 i a 2, a zatem a n i a n+1 to 1. Tj. a n+1=1.

Pomnóżmy wszystkie te równości przez λ , następnie

Niech wspólny dzielnik a 1 λ oraz a 2 jest δ . Następnie δ wchodzi jako czynnik a 1 λ , m 1 a 2 λ i w a 1 λ -m 1 a 2 λ =a 3 λ (Patrz „Podzielność liczb”, Stwierdzenie 2). Dalej δ wchodzi jako czynnik a 2 λ oraz m 2 a 3 λ , a zatem wchodzi jako czynnik w a 2 λ -m 2 a 3 λ =a 4 λ .

Rozumując w ten sposób, jesteśmy o tym przekonani δ wchodzi jako czynnik a n−1 λ oraz m n−1 a n λ , a więc w a n−1 λ −m n−1 a n λ =a n+1 λ . Dlatego a zatem n+1 = 1 δ wchodzi jako czynnik λ . Stąd liczba δ jest wspólnym dzielnikiem liczb λ oraz a 2 .

Rozważ szczególne przypadki Twierdzenia 1.

Konsekwencja 1. Wynajmować a oraz c liczby pierwsze są względne b. Potem ich produkt ak jest liczbą pierwszą względem b.

Naprawdę. Z Twierdzenia 1 ak oraz b mają takie same wspólne dzielniki jak c oraz b. Ale liczby c oraz b względnie pierwsze, tj. mają jeden wspólny dzielnik 1. Wtedy ak oraz b mają również jeden wspólny dzielnik 1. Stąd ak oraz b wzajemnie proste.

Konsekwencja 2. Wynajmować a oraz b liczby względnie pierwsze i niech b dzieli tak. Następnie b dzieli i k.

Naprawdę. Z warunku asercji tak oraz b mają wspólny dzielnik b. Na mocy Twierdzenia 1, b musi być wspólnym dzielnikiem b oraz k. w konsekwencji b dzieli k.

Wniosek 1 można uogólnić.

Konsekwencja 3. 1. Niech liczby a 1 , a 2 , a 3 , ..., a m są liczbami pierwszymi względem liczby b. Następnie a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m , iloczyn tych liczb jest liczbą pierwszą względem tej liczby b.

2. Niech mamy dwa rzędy liczb

tak, że każda liczba w pierwszym rzędzie jest pierwsza względem każdej liczby w drugim rzędzie. Następnie produkt

Wymagane jest znalezienie takich liczb, które są podzielne przez każdą z tych liczb.

Jeżeli liczba jest podzielna przez a 1, tak to wygląda sa 1, gdzie s jakiś numer. Jeśli q jest największym wspólnym dzielnikiem liczb a 1 i a 2, w takim razie

gdzie s 1 to pewna liczba całkowita. Następnie

jest najmniejsza wspólna wielokrotność liczb a 1 i a 2 .

a 1 i a 2 względnie pierwsze, a następnie najmniejsza wspólna wielokrotność tych liczb a 1 i a 2:

Znajdź najmniejszą wspólną wielokrotność tych liczb.

Z powyższego wynika, że dowolna wielokrotność liczb a 1 , a 2 , a 3 musi być wielokrotnością liczby ε oraz a 3 i odwrotnie. Niech najmniejsza wspólna wielokrotność liczb ε oraz a 3 jest ε jeden . Ponadto wielokrotność liczb a 1 , a 2 , a 3 , a 4 musi być wielokrotnością liczby ε 1 i a cztery . Niech najmniejsza wspólna wielokrotność liczb ε 1 i a 4 jest ε 2. W ten sposób dowiedzieliśmy się, że wszystkie wielokrotności liczb a 1 , a 2 , a 3 ,...,a m pokrywają się z wielokrotnościami określonej liczby ε n , która jest nazywana najmniejszą wspólną wielokrotnością podanych liczb.

W szczególnym przypadku, gdy liczby a 1 , a 2 , a 3 ,...,a m względnie pierwsza, to najmniejsza wspólna wielokrotność tych liczb a 1 , a 2, jak pokazano powyżej, ma postać (3). Dalej, ponieważ a 3 pierwsze w odniesieniu do liczb a 1 , a 2, w takim razie a 3 to pierwsza liczba względna a jeden · a 2 (Wniosek 1). Czyli najmniejsza wspólna wielokrotność tych liczb a 1 ,a 2 ,a 3 to liczba a jeden · a 2 · a 3 . Argumentując w podobny sposób, dochodzimy do następujących twierdzeń.

Oświadczenie 1. Najmniejsza wspólna wielokrotność liczb względnie pierwszych a 1 , a 2 , a 3 ,...,a m jest równe ich iloczynowi a jeden · a 2 · a 3 ··· a m .

Oświadczenie 2. Dowolna liczba, która jest podzielna przez każdą z liczb względnie pierwszych a 1 , a 2 , a 3 ,...,a m jest również podzielna przez ich iloczyn a jeden · a 2 · a 3 ··· a m .

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.

Wspólne wielokrotności

Mówiąc najprościej, każda liczba całkowita podzielna przez każdą z podanych liczb jest wspólna wielokrotność podane liczby całkowite.

Możesz znaleźć wspólną wielokrotność dwóch lub więcej liczb całkowitych.

Przykład 1

Oblicz wspólną wielokrotność dwóch liczb: 2 $ i 5 $.

Rozwiązanie.

Z definicji wspólna wielokrotność 2 $ i 5 $ to 10 $, ponieważ jest to wielokrotność 2$ i 5$:

Wspólnymi wielokrotnościami liczb $2$ i $5$ będą również liczby $–10, 20, –20, 30, –30$ itd., ponieważ wszystkie są podzielne przez 2 $ i 5 $.

Uwaga 1

Zero jest wspólną wielokrotnością dowolnej liczby niezerowej liczby całkowitej.

Zgodnie z właściwościami podzielności, jeśli pewna liczba jest wspólną wielokrotnością kilku liczb, to liczba znajdująca się naprzeciwko znaku będzie również wspólną wielokrotnością danych liczb. Widać to na rozważanym przykładzie.

Dla danych liczb całkowitych zawsze możesz znaleźć ich wspólną wielokrotność.

Przykład 2

Oblicz wspólną wielokrotność 111 $ i 55 $.

Rozwiązanie.

Pomnóż podane liczby: $111\div 55=6105$. Łatwo sprawdzić, że liczba 6105 $ jest podzielna przez liczbę 111 $ i liczbę 55 $:

$6105\div 111=55$;

6105 $ \ dział 55 = 111 $.

Zatem 6105 $ to wspólna wielokrotność 111 $ i 55 $.

Odpowiadać: wspólna wielokrotność 111 $ i 55 $ to 6105 $.

Ale, jak już widzieliśmy z poprzedniego przykładu, ta wspólna wielokrotność nie jest jedynką. Inne wspólne wielokrotności to -6105 $, 12210, -12210, 61050, -61050 $ i tak dalej. W ten sposób doszliśmy do następującego wniosku:

Uwaga 2

Każdy zbiór liczb całkowitych ma nieskończoną liczbę wspólnych wielokrotności.

W praktyce ograniczają się one do znajdowania wspólnych wielokrotności tylko dodatnich liczb całkowitych (naturalnych), ponieważ zbiory wielokrotności danej liczby i jej przeciwieństwa pokrywają się.

Znalezienie najmniejszej wspólnej wielokrotności

Najczęściej ze wszystkich wielokrotności danej liczby używana jest najmniejsza wspólna wielokrotność (LCM).

Definicja 2

Najmniejszą dodatnią wspólną wielokrotnością podanych liczb całkowitych jest najmniejsza wspólna wielokrotność te liczby.

Przykład 3

Oblicz LCM liczb $4$ i $7$.

Rozwiązanie.

Dlatego te liczby nie mają wspólnych dzielników, wtedy $LCM(4,7)=28$.

Odpowiadać: $LCM(4,7)=28$.

Znalezienie NOC przez NOD

Dlatego istnieje związek między LCM i NWD, za jego pomocą można obliczyć LCM dwóch dodatnich liczb całkowitych:

Uwaga 3

Przykład 4

Oblicz LCM liczb 232 $ i 84 $.

Rozwiązanie.

Użyjmy wzoru na znalezienie LCM za pomocą NWD:

$LCD (a,b)=\frac(a\cdot b)(gcd(a,b))$

Znajdźmy gcd liczb 232 $ i 84 $ za pomocą algorytmu Euklidesa:

232$=84\cdot 2+64$,

$84=64\cdot 1+20$,

64 $=20\cdot 3+4$,

Tych. $gcd (232, 84)=4$.

Znajdźmy $LCM (232, 84)$:

$LCC(232,84)=\frac(232\cdot 84)(4)=58\cdot 84=4872$

Odpowiadać: $NOK(232,84)=4872$.

Przykład 5

Oblicz $LCM (23, 46) $.

Rozwiązanie.

Dlatego 46 $ jest równo podzielne przez 23 $, więc $gcd(23, 46) = 23 $. Znajdźmy NOC:

$LCC(23,46)=\frac(23\cdot 46)(23)=46$

Odpowiadać: $NOK(23,46)=46$.

W ten sposób można sformułować reguła:

Uwaga 4

Przedstawiony poniżej materiał jest logiczną kontynuacją teorii z artykułu pod nagłówkiem LCM – najmniejsza wspólna wielokrotność, definicja, przykłady, zależność pomiędzy LCM a NWD. Tutaj porozmawiamy o znajdowanie najmniejszej wspólnej wielokrotności (LCM) i zwróć szczególną uwagę na rozwiązywanie przykładów. Najpierw pokażmy, jak oblicza się LCM dwóch liczb na podstawie NWD tych liczb. Następnie rozważ znalezienie najmniejszej wspólnej wielokrotności przez rozłożenie liczb na czynniki pierwsze. Następnie skupimy się na znalezieniu LCM trzech lub więcej liczb, a także zwrócimy uwagę na obliczenie LCM liczb ujemnych.

Nawigacja po stronie.

Obliczanie najmniejszej wspólnej wielokrotności (LCM) przez gcd

Jednym ze sposobów znalezienia najmniejszej wspólnej wielokrotności jest relacja między LCM i NWD. Istniejąca zależność między LCM i 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: GCM(a, b) . Rozważ przykłady znajdowania LCM według powyższego wzoru.

Przykład.

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

Rozwiązanie.

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

Znajdź gcd(126, 70) za pomocą algorytmu Euklidesa: 126=70 1+56 , 70=56 1+14 , 56=14 4 , stąd gcd(126, 70)=14 .

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

Odpowiadać:

LCM(126, 70)=630 .

Przykład.

Co to jest LCM(68, 34)?

Rozwiązanie.

Dlatego 68 jest równo podzielne przez 34 , to gcd(68, 34)=34 . Teraz obliczamy najmniejszą wspólną wielokrotność: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .

Odpowiadać:

LCM(68, 34)=68 .

Zauważ, że poprzedni przykład pasuje do następującej reguły znajdowania LCM dla dodatnich liczb całkowitych a i b : jeśli liczba a jest podzielna przez b , to 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 wynikowy iloczyn będzie równy najmniejszej wspólnej wielokrotności tych liczb.

Ogłoszona reguła znajdowania LCM wynika z równości LCM(a, b)=a b: GCM(a, b). Rzeczywiście, iloczyn liczb aib jest równy iloczynowi wszystkich czynników zaangażowanych w rozwinięcia liczb aib. Z kolei gcd(a, b) jest równe iloczynowi wszystkich czynników pierwszych występujących jednocześnie w rozwinięciach liczb a i b (co jest opisane w części dotyczącej znajdowania gcd z rozkładu liczb na czynniki pierwsze ).

Weźmy przykład. Powiedzmy, że 75=3 5 5 i 210=2 3 5 7 . Skomponuj iloczyn wszystkich czynników tych rozszerzeń: 2 3 3 5 5 5 7 . Teraz wyłączymy z tego iloczynu wszystkie czynniki, które występują zarówno w rozwinięciu liczby 75, jak iw rozwinięciu liczby 210 (takimi czynnikami są 3 i 5), wtedy iloczyn przyjmie postać 2 3 5 5 7 . Wartość tego iloczynu jest równa najmniejszej wspólnej wielokrotności liczb 75 i 210, czyli LCM(75, 210)= 2 3 5 5 7=1 050.

Przykład.

Po rozłożeniu liczb 441 i 700 na czynniki pierwsze, znajdź najmniejszą wspólną wielokrotność tych liczb.

Rozwiązanie.

Rozłóżmy liczby 441 i 700 na czynniki pierwsze:

Otrzymujemy 441=3 3 7 7 i 700=2 2 5 5 7 .

Teraz zróbmy iloczyn wszystkich czynników zaangażowanych w rozwinięcia tych liczb: 2 2 3 3 5 5 7 7 7 . Wykluczmy z tego iloczynu wszystkie czynniki występujące jednocześnie w obu rozwinięciach (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 .

Regułę znajdowania LCM na podstawie rozkładu liczb na czynniki pierwsze można sformułować nieco inaczej. Jeśli do czynników z rozwinięcia liczby a dodamy brakujące czynniki z rozwinięcia liczby b, to wartość otrzymanego iloczynu będzie równa najmniejszej wspólnej wielokrotności liczb a i b.

Weźmy na przykład te same liczby 75 i 210, ich rozwinięcia na czynniki pierwsze są następujące: 75=3 5 5 i 210=2 3 5 7 . Do czynników 3, 5 i 5 z rozkładu liczby 75 dodamy brakujące czynniki 2 i 7 z rozkładu liczby 210, otrzymamy iloczyn 2 3 5 5 7 , którego wartość to LCM(75 , 210).

Przykład.

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

Rozwiązanie.

Najpierw otrzymujemy rozkład liczb 84 i 648 na czynniki pierwsze. Wyglądają jak 84=2 2 3 7 i 648=2 2 2 3 3 3 3 . Do czynników 2 , 2 , 3 i 7 z rozkładu liczby 84 dodajemy brakujące czynniki 2 , 3 , 3 i 3 z rozkładu liczby 648 , otrzymujemy iloczyn 2 2 2 3 3 3 3 7 , co równa się 4 536 . Zatem pożądana najmniejsza wspólna wielokrotność liczb 84 i 648 wynosi 4536.

Odpowiadać:

LCM(84, 648)=4 536 .

Znalezienie LCM trzech lub więcej liczb

Najmniejszą wspólną wielokrotność trzech lub więcej liczb można znaleźć, znajdując kolejno LCM dwóch liczb. Przypomnij sobie odpowiednie twierdzenie, które pozwala znaleźć LCM trzech lub więcej liczb.

Twierdzenie.

Niech dodatnie liczby całkowite a 1 , a 2 , …, a k to najmniejsza wspólna wielokrotność m k tych liczb znajduje się w obliczeniu sekwencyjnym m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , za k) .

Rozważ zastosowanie tego twierdzenia na przykładzie znalezienia najmniejszej wspólnej wielokrotności czterech liczb.

Przykład.

Znajdź LCM czterech liczb 140 , 9 , 54 i 250 .

Rozwiązanie.

W tym przykładzie a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .

Najpierw znajdujemy m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). Aby to zrobić, używając algorytmu Euklidesa, wyznaczamy gcd(140, 9) , mamy 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , zatem gcd( 140, 9)=1 , skąd LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . To znaczy m 2 = 1 260 .

Teraz znajdujemy m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Obliczmy to za pomocą funkcji gcd(1 260, 54) , która jest również określona przez algorytm Euklidesa: 1 260=54 23+18 , 54=18 3 . Wtedy gcd(1 260, 54)=18 , skąd LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . To znaczy m 3 \u003d 3 780.

Pozostało znaleźć m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). Aby to zrobić, znajdujemy NWD(3 780, 250) za pomocą algorytmu Euklidesa: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Dlatego gcd(3 780, 250)=10 , skąd gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . To znaczy m 4 \u003d 94 500.

Tak więc najmniejszą wspólną wielokrotnością czterech oryginalnych liczb jest 94 500.

Odpowiadać:

LCM(140, 9, 54, 250)=94500.

W wielu przypadkach najmniejszą wspólną wielokrotność trzech lub więcej liczb można wygodnie znaleźć za pomocą rozkładu na czynniki pierwsze podanych liczb. W takim przypadku należy przestrzegać następującej zasady. Najmniejsza wspólna wielokrotność kilku liczb jest równa iloczynowi, który składa się z następujących elementów: brakujące czynniki z rozwinięcia drugiej liczby dodaje się do wszystkich czynników z rozwinięcia pierwszej liczby, brakujące czynniki z rozwinięcia do otrzymanych współczynników dodaje się trzecią liczbę i tak dalej.

Rozważmy przykład znajdowania najmniejszej wspólnej wielokrotności za pomocą rozkładu liczb na czynniki pierwsze.

Przykład.

Znajdź najmniejszą wspólną wielokrotność pięciu liczb 84 , 6 , 48 , 7 , 143 .

Rozwiązanie.

Najpierw otrzymujemy rozwinięcia tych liczb na czynniki pierwsze: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 czynników pierwszych) i 143=11 13 .

Aby znaleźć LCM tych liczb, do czynników pierwszej liczby 84 (są to 2 , 2 , 3 i 7 ) należy dodać brakujące czynniki z rozwinięcia drugiej liczby 6 . Rozwinięcie liczby 6 nie zawiera brakujących czynników, ponieważ zarówno 2, jak i 3 są już obecne w rozwinięciu pierwszej liczby 84 . Oprócz czynników 2 , 2 , 3 i 7 dodajemy brakujące czynniki 2 i 2 z rozwinięcia trzeciej liczby 48 , otrzymujemy zbiór czynników 2 , 2 , 2 , 2 , 3 i 7 . Nie ma potrzeby dodawania czynników do tego zestawu w następnym kroku, ponieważ 7 jest już w nim zawarte. Na koniec do czynników 2 , 2 , 2 , 2 , 3 i 7 dodajemy brakujące czynniki 11 i 13 z rozwinięcia liczby 143 . Otrzymujemy iloczyn 2 2 2 2 3 7 11 13 , co jest równe 48 048 .

Największy wspólny dzielnik

Definicja 2

Jeśli liczba naturalna a jest podzielna przez liczbę naturalną $b$, to $b$ nazywamy dzielnikiem $a$, a liczbę $a$ nazywamy wielokrotnością $b$.

Niech $a$ i $b$ będą liczbami naturalnymi. Liczba $c$ jest nazywana wspólnym dzielnikiem zarówno dla $a$, jak i dla $b$.

Zbiór wspólnych dzielników liczb $a$ i $b$ jest skończony, ponieważ żaden z tych dzielników nie może być większy niż $a$. Oznacza to, że wśród tych dzielników jest największy, który nazywany jest największym wspólnym dzielnikiem liczb $a$ i $b$, a do jego oznaczenia służy notacja:

$gcd \ (a;b) \ lub \ D \ (a;b)$

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

Znajdź iloczyn liczb znalezionych w kroku 2. Wynikowa liczba będzie pożądanym największym wspólnym dzielnikiem.

Przykład 1

Znajdź gcd liczb $121$ i $132.$

242 $=2\ckropka 11\ckropka 11$

$132=2\ckropka 2\ckropka 3\ckropka 11$

Wybierz liczby, które są zawarte w rozwinięciu tych liczb

242 $=2\ckropka 11\ckropka 11$

$132=2\ckropka 2\ckropka 3\ckropka 11$

Znajdź iloczyn liczb znalezionych w kroku 2. Wynikowa liczba będzie pożądanym największym wspólnym dzielnikiem.

$gcd=2\cdot 11=22$

Przykład 2

Znajdź NWD jednomianów $63$ i $81$.

Znajdziemy według przedstawionego algorytmu. Dla tego:

Rozłóżmy liczby na czynniki pierwsze

$63=3\cdot 3\cdot 7$

$81=3\ckropka 3\ckropka 3\ckropka 3$

Wybieramy liczby, które są zawarte w rozwinięciu tych liczb

$63=3\cdot 3\cdot 7$

$81=3\ckropka 3\ckropka 3\ckropka 3$

Znajdźmy iloczyn liczb znalezionych w kroku 2. Wynikowa liczba będzie pożądanym największym wspólnym dzielnikiem.

$gcd=3\cdot 3=9$

Możesz znaleźć NWD dwóch liczb w inny sposób, używając zestawu dzielników liczb.

Przykład 3

Znajdź gcd liczb $48$ i $60$.

Rozwiązanie:

Znajdź zbiór dzielników $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Teraz znajdźmy zbiór dzielników $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

Znajdźmy przecięcie tych zbiorów: $\left$(\rm 1,2,3,4,6,12)\right$$ - ten zbiór wyznaczy zbiór wspólnych dzielników liczb $48$ i $60 $. Największym elementem w tym zestawie będzie liczba $12$. Więc największym wspólnym dzielnikiem 48$ i 60$ jest 12$.

Definicja NOC

Definicja 3

wspólna wielokrotność liczb naturalnych$a$ i $b$ to liczba naturalna będąca wielokrotnością zarówno $a$, jak i $b$.

Wspólne wielokrotności liczb to liczby, które są podzielne przez oryginał bez reszty. Na przykład dla liczb 25 $ i 50 $ wspólnymi wielokrotnościami będą liczby 50 100 150 200 $ itd.

Najmniejsza wspólna wielokrotność będzie nazywana najmniejszą wspólną wielokrotnością i oznaczona jako LCM$(a;b)$ lub K$(a;b).$

Aby znaleźć LCM dwóch liczb, potrzebujesz:

Rozłóż liczby na czynniki pierwsze
Wypisz czynniki, które są częścią pierwszej liczby i dodaj do nich czynniki, które są częścią drugiej i nie przechodzą do pierwszej

Przykład 4

Znajdź LCM liczb 99 $ i 77 $.

Znajdziemy według przedstawionego algorytmu. Dla tego

Rozłóż liczby na czynniki pierwsze

99 $=3\ckropka 3\ckropka 11$

Zapisz czynniki zawarte w pierwszym

dodaj do nich czynniki, które są częścią drugiego i nie przechodzą do pierwszego

Znajdź iloczyn liczb znalezionych w kroku 2. Otrzymana liczba będzie najmniejszą wspólną wielokrotnością

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Sporządzanie list dzielników liczb jest często bardzo czasochłonne. Istnieje sposób na znalezienie GCD zwany algorytmem Euclida.

Stwierdzenia, na których opiera się algorytm Euklidesa:

Jeśli $a$ i $b$ są liczbami naturalnymi, a $a\vkropki b$, to $D(a;b)=b$

Jeśli $a$ i $b$ są liczbami naturalnymi takimi, że $b

Używając $D(a;b)= D(a-b;b)$, możemy sukcesywnie zmniejszać rozważane liczby, aż dojdziemy do takiej pary liczb, że jedna z nich jest podzielna przez drugą. Wtedy mniejsza z tych liczb będzie pożądanym największym wspólnym dzielnikiem dla liczb $a$ i $b$.

Własności NWD i LCM

Każda wspólna wielokrotność $a$ i $b$ jest podzielna przez K$(a;b)$
Jeśli $a\vdots b$ , to K$(a;b)=a$

Jeżeli K$(a;b)=k$ i $m$-liczba naturalna, to K$(am;bm)=km$

Jeśli $d$ jest wspólnym dzielnikiem dla $a$ i $b$, to K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Jeśli $a\vdots c$ i $b\vdots c$ , to $\frac(ab)(c)$ jest wspólną wielokrotnością $a$ i $b$

Dla dowolnych liczb naturalnych $a$ i $b$ równość

$D(a;b)\cdot K(a;b)=ab$

Każdy wspólny dzielnik $a$ i $b$ jest dzielnikiem $D(a;b)$