Definicja. Największy liczba naturalna, przez który liczby a i b są dzielone bez reszty, nazywa się największy wspólny dzielnik (GCD) te liczby.
Znajdźmy największy wspólny dzielnik numery 24 i 35.
Dzielnikami liczby 24 są liczby 1, 2, 3, 4, 6, 8, 12, 24, a dzielnikami liczby 35 są liczby 1, 5, 7, 35.
Widzimy, że liczby 24 i 35 mają tylko jeden wspólny dzielnik - liczbę 1. Takie liczby nazywane są wzajemnie pierwsze.
Definicja. Nazywa się liczby naturalne wzajemnie pierwsze, jeśli ich największy wspólny dzielnik (NWD) wynosi 1.
Największy wspólny dzielnik (GCD) można znaleźć bez wypisywania wszystkich dzielników danych liczb.
Rozłóżmy liczby 48 i 36 i otrzymajmy:
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 skreślamy te, które nie są uwzględnione w rozwinięciu drugiej liczby (tj. dwie dwójki).
Pozostałe czynniki to 2 * 2 * 3. Ich iloczyn wynosi 12. Liczba ta jest największym wspólnym dzielnikiem liczb 48 i 36. Znaleziono także największy wspólny dzielnik trzech lub więcej liczb.
Aby znaleźć największy wspólny dzielnik
2) spośród czynników wchodzących w skład rozwinięcia jednej z tych liczb skreślić te, które nie wchodzą w skład rozwinięcia innych liczb;
3) znajdź 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 liczb 15, 45, 75 i 180 jest liczba 15, ponieważ wszystkie inne liczby są przez nią podzielne: 45, 75 i 180.
Najmniejsza wspólna wielokrotność (LCM)
Definicja. Najmniejsza wspólna wielokrotność (LCM) liczby naturalne a i b to najmniejsza liczba naturalna będąca wielokrotnością obu a i b. Najmniejszą wspólną wielokrotność (LCM) liczb 75 i 60 można znaleźć bez zapisywania wielokrotności tych liczb z rzędu. Aby to zrobić, rozłóżmy 75 i 60 na czynniki pierwsze: 75 = 3 * 5 * 5 i 60 = 2 * 2 * 3 * 5.
Wypiszmy czynniki uwzględnione w rozwinięciu pierwszej z tych liczb i dodajmy 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.
Znajdują także najmniejszą wspólną wielokrotność trzech lub więcej liczb.
Do znajdź najmniejszą wspólną wielokrotność kilka liczb naturalnych, potrzebujesz:
1) rozłożyć je na czynniki pierwsze;
2) zapisz czynniki składające się na rozwinięcie jednej z liczb;
3) dodać do nich brakujące czynniki z rozwinięć pozostałych liczb;
4) znaleźć iloczyn uzyskanych czynników.
Zauważ, że jeśli jedna z tych liczb jest podzielna przez wszystkie inne liczby, to liczba ta jest najmniejszą wspólną wielokrotnością tych liczb.
Na przykład najmniejsza wspólna wielokrotność liczb 12, 15, 20 i 60 wynosi 60, ponieważ jest podzielna przez wszystkie te liczby.
Pitagoras (VI wiek p.n.e.) i jego uczniowie badali kwestię podzielności liczb. Numer, równa sumie Wszystkie jej dzielniki (bez samej liczby) nazwali 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 – odnaleziono w XV wieku. W 1983 roku znanych było już 27 liczb doskonałych. Ale naukowcy nadal nie wiedzą, czy istnieją liczby doskonałe nieparzyste, czy też istnieje największa liczba doskonała.
Zainteresowanie starożytnych matematyków liczbami pierwszymi wynika z faktu, że każda liczba jest albo pierwsza, albo można ją przedstawić w postaci iloczynu liczby pierwsze, czyli liczby pierwsze są jak cegły, z których zbudowane są pozostałe liczby naturalne.
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 posuniemy się w szeregu liczbowym, tym mniej popularne są liczby pierwsze. Powstaje pytanie: czy istnieje ostatnia (największa) liczba pierwsza? Starożytny grecki matematyk Euklides (III w. p.n.e.) w swojej książce „Elementy”, która przez dwa tysiące lat była głównym podręcznikiem matematyki, udowodnił, że liczb pierwszych jest nieskończenie wiele, czyli za każdą liczbą pierwszą kryje się jeszcze większa liczba pierwsza numer.
Aby znaleźć liczby pierwsze, inny grecki matematyk z tego samego okresu, Eratostenes, wymyślił tę metodę. Zapisał wszystkie liczby od 1 do jakiejś liczby, po czym skreślił jedynkę, która nie jest ani liczbą pierwszą, ani złożoną, następnie przekreślił przez jedynkę wszystkie liczby występujące po 2 (liczby będące wielokrotnością 2, czyli 4, 6, 8 itd.). Pierwszą pozostałą liczbą po 2 było 3. Następnie po dwójce wszystkie liczby występujące po 3 (liczby będące wielokrotnością 3, czyli 6, 9, 12 itd.) zostały przekreślone. w końcu tylko liczby pierwsze pozostały nieskrzyżowane.
Ale wiele liczb naturalnych dzieli się także przez inne liczby naturalne.
Na przykład:
Liczba 12 dzieli się przez 1, przez 2, przez 3, przez 4, przez 6, przez 12;
Liczba 36 dzieli się przez 1, przez 2, przez 3, przez 4, przez 6, przez 12, przez 18, przez 36.
Liczby, przez które liczba jest podzielna przez całość (dla 12 są to 1, 2, 3, 4, 6 i 12) nazywane są dzielniki liczb. Dzielnik liczby naturalnej A- jest liczbą naturalną, która dzieli podany numer A bez śladu. Nazywa się liczbę naturalną, która ma więcej niż dwa dzielniki złożony .
Należy pamiętać, że liczby 12 i 36 mają wspólne dzielniki. Te liczby to: 1, 2, 3, 4, 6, 12. Największym dzielnikiem tych liczb jest 12. Wspólnym dzielnikiem tych dwóch liczb A I B- jest to liczba, przez którą dzielone są obie podane liczby bez reszty A I B.
Wspólne wielokrotności kilka liczb to liczba, która jest podzielna przez każdą z tych liczb. Na przykład, liczby 9, 18 i 45 mają wspólną wielokrotność 180. Ale 90 i 360 są także ich wspólnymi wielokrotnościami. Wśród wszystkich wspólnych wielokrotności zawsze jest najmniejsza, np w tym przypadku to jest 90. Ten numer jest wywoływany najmniejszywspólna wielokrotność (CMM).
LCM jest zawsze liczbą naturalną, która musi być większa niż największa z liczb, dla których jest zdefiniowana.
Najmniejsza wspólna wielokrotność (LCM). Właściwości.
Przemienność:
Łączność:
W szczególności, jeśli i są liczbami względnie pierwszymi, to:
Najmniejsza wspólna wielokrotność dwóch liczb całkowitych M I N jest dzielnikiem wszystkich innych wspólnych wielokrotności M I N. Ponadto zbiór wspólnych wielokrotności m, rz pokrywa się ze zbiorem wielokrotności LCM( m, rz).
Asymptotykę można wyrazić w postaci niektórych funkcji teorii liczb.
Więc, Funkcja Czebyszewa. Taj:
Wynika to z definicji i własności funkcji Landaua g(n).
Co wynika z prawa rozkładu liczb pierwszych.
Znalezienie najmniejszej wspólnej wielokrotności (LCM).
NOC( a, b) można obliczyć na kilka sposobów:
1. Jeżeli znany jest największy wspólny dzielnik, można wykorzystać jego połączenie z LCM:
2. Niech będzie znany rozkład kanoniczny obu liczb na czynniki pierwsze:
Gdzie p 1 ,...,p k- różne liczby pierwsze i d 1 ,...,d k I e 1 ,...,e k— nieujemne liczby całkowite (mogą być zerami, jeśli odpowiadająca im liczba pierwsza nie występuje w rozwinięciu).
Następnie NOC ( A,B) oblicza się według wzoru:
Innymi słowy, rozkład LCM zawiera wszystkie czynniki pierwsze zawarte w co najmniej jednym z rozkładów liczb a, b, i bierze się pod uwagę największy z dwóch wykładników tego mnożnika.
Przykład:
Obliczanie najmniejszej wspólnej wielokrotności kilku liczb można sprowadzić do kilku kolejnych obliczeń LCM dwóch liczb:
Reguła. Aby znaleźć LCM serii liczb, potrzebujesz:
- rozkłada liczby na czynniki pierwsze;
- przenieść największe rozwinięcie (iloczyn czynników pożądanego produktu) na czynniki pożądanego produktu duża liczba z podanych), a następnie dodać czynniki z rozwinięcia innych liczb, które nie występują w pierwszej liczbie lub pojawiają się w niej rzadziej;
— wynikowy iloczyn czynników pierwszych będzie LCM podanych liczb.
Każde dwie lub więcej liczb naturalnych ma swój własny LCM. Jeśli liczby nie są wielokrotnościami siebie lub nie mają tych samych współczynników w rozwinięciu, to ich LCM jest równy iloczynowi tych liczb.
Do czynników pierwszych liczby 28 (2, 2, 7) dodaje się współczynnik 3 (liczba 21), otrzymany iloczyn (84) będzie najmniejsza liczba, który jest podzielny przez 21 i 28.
Do czynników pierwszych największej liczby 30 dodaje się współczynnik 5 liczby 25, otrzymany iloczyn 150 jest większy od największej liczby 30 i jest podzielny przez wszystkie podane liczby bez reszty. Ten najmniej produktu możliwych (150, 250, 300...), których wszystkie podane liczby są wielokrotnościami.
Liczby 2,3,11,37 są liczbami pierwszymi, więc ich LCM jest równy iloczynowi danych liczb.
Reguła. Aby obliczyć LCM liczb pierwszych, należy pomnożyć wszystkie te liczby przez siebie.
Inna opcja:
Aby znaleźć najmniejszą wspólną wielokrotność (LCM) kilku liczb, potrzebujesz:
1) przedstaw każdą liczbę jako iloczyn jej czynników pierwszych, na przykład:
504 = 2 2 2 3 3 7,
2) zapisz potęgi wszystkich czynników pierwszych:
504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,
3) zapisz wszystkie pierwsze dzielniki (mnożniki) każdej z tych liczb;
4) wybrać największy stopień każdej z nich, występujący we wszystkich rozwinięciach tych liczb;
5) pomnóż te potęgi.
Przykład. Znajdź LCM liczb: 168, 180 i 3024.
Rozwiązanie. 168 = 2 2 2 3 7 = 2 3 3 1 7 1,
180 = 2 2 3 3 5 = 2 2 3 2 5 1,
3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1.
Wypisujemy największe stopnie wszystkie dzielniki pierwsze i pomnóż je:
NOC = 2 4 3 3 5 1 7 1 = 15120.
Zaprezentowany poniżej materiał stanowi logiczną kontynuację teorii z artykułu LCM - najmniejsza wspólna wielokrotność, definicja, przykłady, powiązanie LCM z GCD. Tutaj będziemy rozmawiać znajdowanie najmniejszej wspólnej wielokrotności (LCM), I szczególną uwagę Skupmy się na rozwiązywaniu przykładów. Najpierw pokażemy, jak oblicza się LCM dwóch liczb za pomocą NWD tych liczb. Następnie przyjrzymy się znajdowaniu najmniejszej wspólnej wielokrotności poprzez 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 strony.
Obliczanie najmniejszej wspólnej wielokrotności (LCM) za pomocą GCD
Jednym ze sposobów znalezienia najmniejszej wspólnej wielokrotności jest relacja między LCM i GCD. Istniejące połączenie pomiędzy LCM i GCD pozwala obliczyć najmniejszą wspólną wielokrotność dwóch dodatnich liczb całkowitych przy użyciu znanego największego wspólnego dzielnika. Odpowiednia formuła to LCM(a, b)=a b:GCD(a, b) . Rozważmy przykłady znajdowania LCM za pomocą podanego 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 związku pomiędzy LCM i NWD wyrażonego wzorem LCM(a, b)=a b:GCD(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 za pomocą zapisanego wzoru.
Znajdźmy NWD(126, 70) korzystając z algorytmu Euklidesa: 126=70·1+56, 70=56·1+14, 56=14·4, zatem GCD(126, 70)=14.
Teraz znajdujemy wymaganą najmniejszą wspólną wielokrotność: NWD(126, 70)=126·70:NWD(126, 70)= 126·70:14=630.
Odpowiedź:
LCM(126, 70)=630 .
Przykład.
Ile wynosi LCM(68, 34)?
Rozwiązanie.
Ponieważ 68 jest podzielne przez 34, wówczas NWD(68, 34)=34. Teraz obliczamy najmniejszą wspólną wielokrotność: NWD(68, 34)=68·34:NWD(68, 34)= 68.34:34=68.
Odpowiedź:
LCM(68, 34)=68.
Należy zauważyć, ż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 poprzez 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 ułożysz iloczyn ze wszystkich czynników pierwszych danych liczb, a następnie wykluczysz z tego iloczynu wszystkie wspólne czynniki pierwsze występujące w rozwinięciach danych liczb, to otrzymany iloczyn będzie równy najmniejszej wspólnej wielokrotności danych liczb .
Podana zasada znajdowania LCM wynika z równości LCM(a, b)=a b:GCD(a, b). Rzeczywiście, iloczyn liczb aib jest równy iloczynowi wszystkich czynników biorących udział w rozszerzaniu liczb aib. Z kolei NWD(a, b) jest równe iloczynowi wszystkich czynników pierwszych występujących jednocześnie w rozwinięciach liczb a i b (co opisano w rozdziale o znajdowaniu NWD za pomocą rozwinięcia liczb na czynniki pierwsze).
Podajmy przykład. Powiedz nam, że 75=3,5,5 i 210=2,3,5,7. Utwórzmy iloczyn ze wszystkich czynników tych rozwinięć: 2,3,3,5,5,5,7 . Teraz z tego iloczynu wykluczymy wszystkie czynniki występujące zarówno w rozwinięciu liczby 75, jak i rozwinięciu liczby 210 (takie czynniki to 3 i 5), wtedy iloczyn przyjmie postać 2,3,5,5,7 . Wartość tego iloczynu jest równa najmniejszej wspólnej wielokrotności 75 i 210, czyli NOC(75, 210)= 2,3,5,5,7=1050.
Przykład.
Rozłóż liczby 441 i 700 na czynniki pierwsze i 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.
Zróbmy teraz iloczyn wszystkich czynników biorących udział w rozwinięciu 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 rozwinięciach (jest tylko jeden taki czynnik – jest to liczba 7): 2,2,3,3,5,5,7,7. Zatem, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100.
Odpowiedź:
NOC(441, 700)= 44 100 .
Regułę znajdowania LCM za pomocą faktoryzacji liczb na czynniki pierwsze można sformułować nieco inaczej. Jeśli brakujące czynniki z rozwinięcia liczby b dodamy do czynników z rozwinięcia liczby a, wówczas 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 rozkład na czynniki pierwsze wygląda następująco: 75=3,5,5 i 210=2,3,5,7. Do czynników 3, 5 i 5 z rozwinięcia liczby 75 dodajemy brakujące czynniki 2 i 7 z rozwinięcia liczby 210 i otrzymujemy iloczyn 2,3,5,5,7, którego wartość wynosi równe LCM(75, 210).
Przykład.
Znajdź najmniejszą wspólną wielokrotność 84 i 648.
Rozwiązanie.
Najpierw uzyskujemy 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 rozwinięcia liczby 84 dodajemy brakujące czynniki 2, 3, 3 i 3 z rozwinięcia liczby 648 i otrzymujemy iloczyn 2 2 2 3 3 3 3 7, co jest równe 4 536 . Zatem pożądana najmniejsza wspólna wielokrotność 84 i 648 wynosi 4536.
Odpowiedź:
LCM(84, 648) = 4536.
Znajdowanie 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. Przypomnijmy odpowiednie twierdzenie, które pozwala znaleźć LCM trzech lub więcej liczb.
Twierdzenie.
Niech zostaną podane dodatnie liczby całkowite a 1 , a 2 , …, a k, najmniejsza wspólna wielokrotność m k tych liczb zostanie znaleziona poprzez kolejne obliczenie m 2 = LCM(a 1 , a 2) , m 3 = LCM(m 2 , a 3) , … , m k = LCM(m k−1 , a k) .
Rozważmy 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 = LOC(a 1 , a 2) = LOC(140, 9). Aby to zrobić, korzystając z algorytmu Euklidesa, wyznaczamy NWD(140, 9), mamy 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, dlatego NWD(140, 9)=1, skąd NWD(140, 9)=140 9:NWD(140, 9)= 140·9:1=1260. Oznacza to, że m 2 = 1 260.
Teraz znajdujemy m 3 = LOC (m 2 , a 3) = LOC (1 260, 54). Obliczmy to poprzez NWD(1 260, 54), które również wyznaczamy za pomocą algorytmu Euklidesa: 1 260=54·23+18, 54=18·3. Wtedy gcd(1260, 54)=18, skąd gcd(1260, 54)= 1260·54:gcd(1260, 54)= 1260·54:18=3780. Oznacza to, że m 3 =3 780.
Pozostaje tylko znaleźć m 4 = LOC(m 3, a 4) = LOC(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. Zatem GCM(3780, 250)=10, skąd GCM(3780, 250)= 3 780 250: NWD(3 780, 250)= 3780·250:10=94500. Oznacza to, że m 4 = 94 500.
Zatem najmniejsza wspólna wielokrotność pierwotnych czterech liczb wynosi 94 500.
Odpowiedź:
LCM(140, 9, 54, 250) = 94 500.
W wielu przypadkach wygodnie jest znaleźć najmniejszą wspólną wielokrotność trzech lub więcej liczb, stosując rozkład 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ącego wzoru: brakujące czynniki z rozwinięcia drugiej liczby dodawane są do wszystkich czynników z rozwinięcia pierwszej liczby, brakujące czynniki z rozwinięcia trzecia liczba jest dodawana do otrzymanych czynników i tak dalej.
Spójrzmy na przykład znajdowania najmniejszej wspólnej wielokrotności przy użyciu rozkładu na czynniki pierwsze.
Przykład.
Znajdź najmniejszą wspólną wielokrotność pięciu liczb 84, 6, 48, 7, 143.
Rozwiązanie.
Najpierw otrzymujemy rozkłady tych liczb na czynniki pierwsze: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (7 jest liczbą pierwszą, pokrywa się z rozkładem na czynniki pierwsze) i 143=11·13.
Aby znaleźć LCM tych liczb, do współczynników pierwszej liczby 84 (są to 2, 2, 3 i 7), należy dodać brakujące czynniki z rozwinięcia drugiej liczby 6. Rozkład liczby 6 nie zawiera brakujących czynników, ponieważ zarówno 2, jak i 3 są już obecne w rozkładzie pierwszej liczby 84. Następnie do czynników 2, 2, 3 i 7 dodajemy brakujące czynniki 2 i 2 z rozwinięcia trzeciej liczby 48 i otrzymujemy zbiór czynników 2, 2, 2, 2, 3 i 7. W następnym kroku nie będzie potrzeby dodawania mnożników do tego zestawu, ponieważ 7 jest już w nim zawarte. Na koniec do współ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, który jest równy 48,048.
Drugi numer: b=
Separator tysięcy Bez separatora spacji „”.
Wynik:
Największy wspólny dzielnik gcd( A,B)=6
Najmniejsza wspólna wielokrotność LCM ( A,B)=468
Nazywa się największą liczbę naturalną, którą można podzielić bez reszty przez liczby a i b największy wspólny dzielnik(GCD) tych liczb. Oznaczone przez gcd(a,b), (a,b), gcd(a,b) lub hcf(a,b).
Najmniejsza wspólna wielokrotność LCM dwóch liczb całkowitych aib jest najmniejszą liczbą naturalną, która dzieli się przez aib bez reszty. Oznaczone jako LCM(a,b) lub lcm(a,b).
Nazywa się liczby całkowite a i b wzajemnie pierwsze, jeśli nie mają wspólnych dzielników innych niż +1 i -1.
Największy wspólny dzielnik
Niech zostaną podane dwie liczby dodatnie A 1 i A 2 1). Konieczne jest znalezienie wspólnego dzielnika tych liczb, tj. znajdź taką liczbę λ , który dzieli liczby A 1 i A 2 jednocześnie. Opiszmy algorytm.
1) W tym artykule liczba słów będzie rozumiana jako liczba całkowita.
Pozwalać A 1 ≥ A 2 i niech
Gdzie M 1 , A 3 to niektóre liczby całkowite, A 3 <A 2 (reszta z dzielenia A 1 os A 2 powinno być mniej A 2).
Załóżmy, że λ dzieli A 1 i A 2 wtedy λ dzieli M 1 A 2 i λ dzieli A 1 −M 1 A 2 =A 3 (Stwierdzenie 2 artykułu „Podzielność liczb. Test na podzielność”). Wynika z tego, że każdy wspólny dzielnik A 1 i A 2 jest wspólnym dzielnikiem A 2 i A 3. Odwrotna sytuacja jest również prawdą, jeśli λ wspólny dzielnik A 2 i A 3 wtedy M 1 A 2 i A 1 =M 1 A 2 +A 3 jest również podzielne przez λ . Dlatego wspólny dzielnik A 2 i A 3 jest także wspólnym dzielnikiem A 1 i A 2. Ponieważ A 3 <A 2 ≤A 1, to możemy powiedzieć, że jest to rozwiązanie problemu znalezienia wspólnego dzielnika liczb A 1 i A 2 zredukowano do prostszego problemu znalezienia wspólnego dzielnika liczb A 2 i A 3 .
Jeśli A 3 ≠0, to możemy dzielić A 2 os A 3. Następnie
,
Gdzie M 1 i A 4 to niektóre liczby całkowite, ( A 4 pozostałe z dzielenia A 2 os A 3 (A 4 <A 3)). Z podobnego rozumowania dochodzimy do wniosku, że wspólne dzielniki liczb A 3 i A 4 pokrywa się ze wspólnymi dzielnikami liczb A 2 i A 3, a także ze wspólnymi dzielnikami A 1 i A 2. Ponieważ A 1 , A 2 , A 3 , A 4, ... to liczby, które stale maleją, a ponieważ istnieje skończona liczba liczb całkowitych pomiędzy nimi A 2 i 0, a potem w pewnym momencie N, reszta z dzielenia A n A n+1 będzie równe zero ( A n+2 =0).
.
Każdy wspólny dzielnik λ takty muzyczne A 1 i A 2 jest także dzielnikiem liczb A 2 i A 3 , A 3 i A 4 , .... A n i A n+1 . Odwrotna sytuacja jest również prawdą, wspólne dzielniki liczb A n i A n+1 są także dzielnikami liczb A n-1 i A N , .... , A 2 i A 3 , A 1 i A 2. Ale wspólny dzielnik liczb A n i A n+1 to liczba A n+1 , ponieważ A n i A n+1 jest podzielne przez A n+1 (pamiętaj o tym A n+2 =0). Stąd A n+1 jest także dzielnikiem liczb A 1 i A 2 .
Należy pamiętać, że liczba A n+1 to największy dzielnik liczb A n i A n+1 , ponieważ największy dzielnik A n+1 jest sobą A n+1 . Jeśli A n+1 można przedstawić jako iloczyn liczb całkowitych, wówczas 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 takty muzyczne A 1 i A 2 .
Takty muzyczne A 1 i A 2 może być liczbą dodatnią lub ujemną. Jeżeli jedna z liczb jest równa zero, 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 jest nieokreślony.
Powyższy algorytm nazywa się Algorytm euklidesowy znaleźć największy wspólny dzielnik dwóch liczb całkowitych.
Przykład znalezienia 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 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 wywoływane są te liczby liczby względnie pierwsze, nie mający wspólnego dzielnika.
Twierdzenie 1. Jeśli A 1 i A 2 liczby względnie pierwsze i λ pewna liczba, a następnie dowolny wspólny dzielnik liczb λa 1 i A 2 jest także wspólnym dzielnikiem liczb λ I A 2 .
Dowód. Rozważmy algorytm Euklidesa służący 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 i dlatego A n i A n+1 równa się 1. To znaczy A n+1 =1.
Pomnóżmy wszystkie te równości przez λ , Następnie
.
Niech wspólny dzielnik A 1 λ I A 2 tak δ . Następnie δ jest uwzględniany jako mnożnik w A 1 λ , M 1 A 2 λ i w A 1 λ -M 1 A 2 λ =A 3 λ (patrz „Podzielność liczb”, stwierdzenie 2). Następny δ jest uwzględniany jako mnożnik w A 2 λ I M 2 A 3 λ , a zatem jest czynnikiem A 2 λ -M 2 A 3 λ =A 4 λ .
Rozumując w ten sposób, jesteśmy o tym przekonani δ jest uwzględniany jako mnożnik w A n-1 λ I M n-1 A N λ , a zatem w A n-1 λ −M n-1 A N λ =A n+1 λ . Ponieważ A n+1 =1, zatem δ jest uwzględniany jako mnożnik w λ . Dlatego liczba δ jest wspólnym dzielnikiem liczb λ I A 2 .
Rozważmy szczególne przypadki twierdzenia 1.
Konsekwencja 1. Pozwalać A I C Liczby pierwsze są względne B. Potem ich produkt AC jest liczbą pierwszą względem B.
Naprawdę. Z twierdzenia 1 AC I B mają takie same wspólne dzielniki jak C I B. Ale liczby C I B stosunkowo proste, tj. mają jeden wspólny dzielnik 1. Następnie AC I B mają również jeden wspólny dzielnik 1. Dlatego AC I B wzajemnie proste.
Konsekwencja 2. Pozwalać A I B liczby względnie pierwsze i niech B dzieli ok. Następnie B dzieli i k.
Naprawdę. Od warunku zatwierdzenia ok I B mają wspólny dzielnik B. Na mocy Twierdzenia 1, B musi być wspólnym dzielnikiem B I k. Stąd B dzieli k.
Wniosek 1 można uogólnić.
Konsekwencja 3. 1. Niech liczby A 1 , A 2 , A 3 , ..., A m są liczbą pierwszą w stosunku do 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ą B.
2. Miejmy dwa rzędy liczb
tak, że każda liczba z pierwszego szeregu jest liczbą pierwszą w stosunku do każdej liczby z drugiego szeregu. Następnie produkt
Musisz znaleźć liczby podzielne przez każdą z tych liczb.
Jeśli liczba jest podzielna przez A 1, to ma postać sa 1 gdzie S jakiś numer. Jeśli Q jest największym wspólnym dzielnikiem liczb A 1 i A 2, zatem
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 są względnie pierwsze, to najmniejsza wspólna wielokrotność liczb A 1 i A 2:
Musimy znaleźć najmniejszą wspólną wielokrotność tych liczb.
Z powyższego wynika, że dowolna wielokrotność liczb A 1 , A 2 , A 3 musi być wielokrotnością liczb ε I A 3 i z powrotem. Niech najmniejsza wspólna wielokrotność liczb ε I A 3 tak ε 1. Następnie wielokrotności liczb A 1 , A 2 , A 3 , A Liczba 4 musi być wielokrotnością liczb ε 1 i A 4. Niech najmniejsza wspólna wielokrotność liczb ε 1 i A 4 tak ε 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 pewnej liczby ε n, co nazywa się najmniejszą wspólną wielokrotnością danych liczb.
W szczególnym przypadku, gdy liczby A 1 , A 2 , A 3 ,...,A m są względnie pierwsze, to najmniejsza wspólna wielokrotność liczb A 1 , A 2, jak pokazano powyżej, ma postać (3). Następny, od A 3 liczby pierwsze w odniesieniu do liczb A 1 , A 2 wtedy A 3 liczba pierwsza A 1 · A 2 (wniosek 1). Oznacza najmniejszą wspólną wielokrotność liczb A 1 ,A 2 ,A 3 to liczba A 1 · A 2 · A 3. Rozumując w podobny sposób, dochodzimy do następujących stwierdzeń.
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 1 · A 2 · A 3 ··· A M.
Oświadczenie 2. Dowolna liczba, która jest podzielna przez każdą z liczb stosunkowo pierwszych A 1 , A 2 , A 3 ,...,A m jest również podzielne przez ich iloczyn A 1 · A 2 · A 3 ··· A M.
Największy wspólny dzielnik i najmniejsza wspólna wielokrotność to kluczowe pojęcia arytmetyczne, dzięki którym praca z ułamkami nie wymaga wysiłku. LCM i są najczęściej używane do znalezienia wspólnego mianownika kilku ułamków.
Podstawowe pojęcia
Dzielnik liczby całkowitej X to inna liczba całkowita Y, przez którą X jest dzielone bez pozostawiania reszty. Na przykład dzielnik liczby 4 to 2, a 36 to 4, 6, 9. Wielokrotność liczby całkowitej X to liczba Y, która dzieli się przez X bez reszty. Na przykład 3 jest wielokrotnością 15, a 6 jest wielokrotnością 12.
Dla każdej pary liczb możemy znaleźć ich wspólne dzielniki i wielokrotności. Na przykład dla liczb 6 i 9 wspólna wielokrotność wynosi 18, a wspólny dzielnik wynosi 3. Oczywiście pary mogą mieć kilka dzielników i wielokrotności, dlatego w obliczeniach używany jest największy dzielnik GCD i najmniejsza wielokrotność LCM.
Najmniejszy dzielnik nie ma znaczenia, ponieważ dla dowolnej liczby jest zawsze jeden. Największa wielokrotność również nie ma znaczenia, ponieważ ciąg wielokrotności zmierza do nieskończoności.
Znalezienie gcd
Istnieje wiele metod znajdowania największego wspólnego dzielnika, z których najbardziej znane to:
- sekwencyjne wyszukiwanie dzielników, wybór wspólnych dla pary i poszukiwanie największego z nich;
- rozkład liczb na czynniki niepodzielne;
- algorytm euklidesowy;
- algorytm binarny.
Obecnie w placówkach oświatowych najpopularniejszymi metodami są rozkład na czynniki pierwsze i algorytm Euklidesa. To drugie z kolei wykorzystuje się przy rozwiązywaniu równań diofantyny: poszukiwanie NWD jest wymagane, aby sprawdzić równanie pod kątem możliwości rozwiązania w liczbach całkowitych.
Znalezienie NOC
Najmniejszą wspólną wielokrotność wyznacza się również poprzez kolejne wyliczenie lub rozkład na czynniki niepodzielne. Ponadto łatwo jest znaleźć LCM, jeśli został już określony największy dzielnik. Dla liczb X i Y LCM i GCD są powiązane następującą zależnością:
LCD(X,Y) = X × Y / GCD(X,Y).
Na przykład, jeśli GCM(15,18) = 3, to LCM(15,18) = 15 × 18 / 3 = 90. Najbardziej oczywistym przykładem użycia LCM jest znalezienie wspólnego mianownika, który jest najmniejszą wspólną wielokrotnością dane ułamki.
Liczby względnie pierwsze
Jeżeli para liczb nie ma wspólnych dzielników, wówczas taką parę nazywamy względnie pierwszą. Współczynnik gcd dla takich par jest zawsze równy jeden, a na podstawie połączenia między dzielnikami i wielokrotnościami, gcd dla par względnie pierwszych jest równy ich iloczynowi. Na przykład liczby 25 i 28 są względnie pierwsze, ponieważ nie mają wspólnych dzielników, a LCM(25, 28) = 700, co odpowiada ich iloczynowi. Każde dwie niepodzielne liczby zawsze będą względnie pierwsze.
Wspólny dzielnik i kalkulator wielokrotny
Za pomocą naszego kalkulatora możesz obliczyć GCD i LCM dla dowolnej liczby liczb do wyboru. Zadania dotyczące obliczania wspólnych dzielników i wielokrotności znajdują się w arytmetyce w piątej i szóstej klasie, ale GCD i LCM są kluczowymi pojęciami w matematyce i są wykorzystywane w teorii liczb, planimetrii i algebrze komunikacyjnej.
Przykłady z życia wzięte
Wspólny mianownik ułamków
Najmniejsza wspólna wielokrotność jest używana przy znajdowaniu wspólnego mianownika wielu ułamków. Załóżmy, że w zadaniu arytmetycznym musisz zsumować 5 ułamków:
1/8 + 1/9 + 1/12 + 1/15 + 1/18.
Aby dodać ułamki, wyrażenie należy sprowadzić do wspólnego mianownika, co sprowadza się do problemu znalezienia LCM. Aby to zrobić, wybierz 5 liczb w kalkulatorze i wprowadź wartości mianowników w odpowiednich komórkach. Program obliczy LCM (8, 9, 12, 15, 18) = 360. Teraz dla każdego ułamka należy obliczyć dodatkowe współczynniki, które definiuje się jako stosunek LCM do mianownika. Zatem dodatkowe mnożniki będą wyglądać następująco:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
Następnie mnożymy wszystkie ułamki przez odpowiedni dodatkowy współczynnik i otrzymujemy:
45/360 + 40/360 + 30/360 + 24/360 + 20/360.
Możemy łatwo zsumować takie ułamki i otrzymać wynik 159/360. Zmniejszamy ułamek o 3 i widzimy ostateczną odpowiedź - 53/120.
Rozwiązywanie liniowych równań diofantyny
Liniowe równania diofantyny są wyrażeniami w postaci ax + by = d. Jeśli stosunek d / gcd(a, b) jest liczbą całkowitą, wówczas równanie można rozwiązać w liczbach całkowitych. Sprawdźmy kilka równań, aby zobaczyć, czy mają rozwiązanie w postaci liczb całkowitych. Najpierw sprawdźmy równanie 150x + 8y = 37. Używając kalkulatora, znajdujemy GCD (150,8) = 2. Podziel 37/2 = 18,5. Liczba nie jest liczbą całkowitą, dlatego równanie nie ma pierwiastków całkowitych.
Sprawdźmy równanie 1320x + 1760y = 10120. Użyj kalkulatora, aby znaleźć NWD(1320, 1760) = 440. Podziel 10120/440 = 23. W rezultacie otrzymamy liczbę całkowitą, zatem równanie diofantyny można rozwiązać przy użyciu współczynników całkowitych .
Wniosek
GCD i LCM odgrywają dużą rolę w teorii liczb, a same pojęcia są szeroko stosowane w wielu różnych obszarach matematyki. Skorzystaj z naszego kalkulatora, aby obliczyć największe dzielniki i najmniejsze wielokrotności dowolnej liczby liczb.