Co znamená nejmenší společný násobek? Nod a nok čísel - největší společný dělitel a nejmenší společný násobek několika čísel

Druhé číslo: b=

Oddělovač tisíců Bez oddělovače mezer "".

Výsledek:

Největší společný dělitel gcd( A,b)=6

Nejmenší společný násobek LCM( A,b)=468

Říká se největší přirozené číslo, které lze beze zbytku dělit čísly a a b největší společný dělitel(GCD) těchto čísel. Označuje se gcd(a,b), (a,b), gcd(a,b) nebo hcf(a,b).

Nejmenší společný násobek LCM dvou celých čísel aab je nejmenší přirozené číslo, které je dělitelné aab beze zbytku. Označuje se LCM(a,b) nebo lcm(a,b).

Nazývají se celá čísla a a b vzájemně prvočíslo, pokud nemají žádné jiné společné dělitele než +1 a −1.

Největší společný dělitel

Nechť jsou dána dvě kladná čísla A 1 a A 21). Je potřeba najít společného dělitele těchto čísel, tzn. najít takové číslo λ , který rozděluje čísla A 1 a A 2 ve stejnou dobu. Pojďme si popsat algoritmus.

1) V tomto článku bude slovo číslo chápáno jako celé číslo.

Nechat A 1 ≥ A 2 a nechat

Kde m 1 , A 3 jsou nějaká celá čísla, A 3 <A 2 (zbytek divize A 1 za A 2 by mělo být méně A 2).

Předpokládejme to λ rozděluje A 1 a A 2 pak λ rozděluje m 1 A 2 a λ rozděluje A 1 −m 1 A 2 =A 3 (Výrok 2 článku „Dělitelnost čísel. Test dělitelnosti“). Z toho vyplývá, že každý společný dělitel A 1 a A 2 je společný dělitel A 2 a A 3. Opak je také pravdou, jestliže λ společný dělitel A 2 a A 3 pak m 1 A 2 a A 1 =m 1 A 2 +A 3 je také dělitelné λ . Proto společný dělitel A 2 a A 3 je také společný dělitel A 1 a A 2. Protože A 3 <A 2 ≤A 1, pak můžeme říci, že řešení problému hledání společného dělitele čísel A 1 a A 2 zredukován na jednodušší problém nalezení společného dělitele čísel A 2 a A 3 .

Li A 3 ≠0, pak můžeme dělit A 2 na A 3. Pak

Kde m 1 a A 4 jsou nějaká celá čísla, ( A 4 zbytek z divize A 2 na A 3 (A 4 <A 3)). Podobnou úvahou dojdeme k závěru, že společné dělitele čísel A 3 a A 4 se shoduje se společnými děliteli čísel A 2 a A 3, a také se společnými děliteli A 1 a A 2. Protože A 1 , A 2 , A 3 , A 4, ... jsou čísla, která neustále klesají, a protože mezi nimi je konečný počet celých čísel A 2 a 0, pak v určitém kroku n, zbytek divize A n na A n+1 se bude rovnat nule ( A n+2 = 0).

Každý společný dělitel λ čísla A 1 a A 2 je také dělitel čísel A 2 a A 3 , A 3 a A 4 , .... A n a A n+1. Platí to i obráceně, společné dělitele čísel A n a A n+1 jsou také dělitelé čísel A n−1 a A n , .... , A 2 a A 3 , A 1 a A 2. Ale společný dělitel čísel A n a A n+1 je číslo A n+1, protože A n a A n+1 jsou dělitelné A n+1 (pamatujte si to A n+2 = 0). Proto A n+1 je také dělitel čísel A 1 a A 2 .

Všimněte si, že číslo A n+1 je největší dělitel čísel A n a A n+1 , protože největší dělitel A n+1 je samo sebou A n+1. Li A n+1 lze reprezentovat jako součin celých čísel, pak jsou tato čísla také společnými děliteli čísel A 1 a A 2. Číslo A je voláno n+1 největší společný dělitelčísla A 1 a A 2 .

Čísla A 1 a A 2 mohou být kladná nebo záporná čísla. Pokud je jedno z čísel rovno nule, pak se největší společný dělitel těchto čísel bude rovnat absolutní hodnotě druhého čísla. Největší společný dělitel nulových čísel není definován.

Výše uvedený algoritmus se nazývá Euklidovský algoritmus najít největšího společného dělitele dvou celých čísel.

Příklad hledání největšího společného dělitele dvou čísel

Najděte největšího společného dělitele dvou čísel 630 a 434.

Krok 1. Vydělte číslo 630 číslem 434. Zbytek je 196.
Krok 2. Vydělte číslo 434 číslem 196. Zbytek je 42.
Krok 3. Vydělte číslo 196 42. Zbytek je 28.
Krok 4. Vydělte číslo 42 28. Zbytek je 14.
Krok 5. Vydělte číslo 28 14. Zbytek je 0.

V kroku 5 je zbytek dělení 0. Proto je největší společný dělitel čísel 630 a 434 14. Všimněte si, že čísla 2 a 7 jsou také děliteli čísel 630 a 434.

Coprime čísla

Definice 1. Nechť největší společný dělitel čísel A 1 a A 2 se rovná jedné. Poté se volají tato čísla koprime čísla, které nemají společného dělitele.

Teorém 1. Li A 1 a A 2 hlavní čísla a λ nějaké číslo, pak libovolný společný dělitel čísel λa 1 a A 2 je také společný dělitel čísel λ A A 2 .

Důkaz. Zvažte euklidovský algoritmus pro nalezení největšího společného dělitele čísel A 1 a A 2 (viz výše).

Z podmínek věty vyplývá, že největší společný dělitel čísel A 1 a A 2 a proto A n a A n+1 je 1. To znamená A n+1 = 1.

Vynásobme všechny tyto rovnosti λ , Pak

Nechť společný dělitel A 1 λ A A 2 ano δ . Pak δ je zahrnut jako násobitel v A 1 λ , m 1 A 2 λ a dovnitř A 1 λ -m 1 A 2 λ =A 3 λ (viz "Dělitelnost čísel", Příkaz 2). Další δ je zahrnut jako násobitel v A 2 λ A m 2 A 3 λ , a proto je zahrnut jako faktor v A 2 λ -m 2 A 3 λ =A 4 λ .

Tímto způsobem jsme o tom přesvědčeni δ je zahrnut jako násobitel v A n−1 λ A m n−1 A n λ , a proto v A n−1 λ −m n−1 A n λ =A n+1 λ . Protože A n+1 = 1, tedy δ je zahrnut jako násobitel v λ . Proto číslo δ je společný dělitel čísel λ A A 2 .

Podívejme se na speciální případy věty 1.

Následek 1. Nechat A A C Prvočísla jsou relativní b. Pak jejich produkt ac je prvočíslo vzhledem k b.

Opravdu. Z věty 1 ac A b mají stejné společné dělitele jako C A b. Ale ta čísla C A b poměrně jednoduché, tzn. mít jediného společného dělitele 1. Pak ac A b mají také jediného společného dělitele 1. Proto ac A b vzájemně jednoduché.

Následek 2. Nechat A A b koprime čísla a nech b rozděluje ak. Pak b rozděluje a k.

Opravdu. Z kolaudační podmínky ak A b mají společného dělitele b. Na základě věty 1, b musí být společný dělitel b A k. Proto b rozděluje k.

Důsledek 1 lze zobecnit.

Následek 3. 1. Nechte čísla A 1 , A 2 , A 3 , ..., A m jsou prvočísla vzhledem k číslu b. Pak A 1 A 2 , A 1 A 2 · A 3 , ..., A 1 A 2 A 3 ··· A m, součin těchto čísel je prvočíslo vzhledem k číslu b.

2. Mějme dvě řady čísel

takové, že každé číslo v první řadě je prvočíslo v poměru všech čísel ve druhé řadě. Poté produkt

Musíte najít čísla, která jsou dělitelná každým z těchto čísel.

Pokud je číslo dělitelné A 1, pak má tvar sa 1 kde s nějaké číslo. Li q je největší společný dělitel čísel A 1 a A 2, tedy

Kde s 1 je nějaké celé číslo. Pak

je nejmenší společné násobky čísel A 1 a A 2 .

A 1 a A 2 jsou relativně prvočísla, pak nejmenší společný násobek čísel A 1 a A 2:

Musíme najít nejmenší společný násobek těchto čísel.

Z výše uvedeného vyplývá, že libovolný násobek čísel A 1 , A 2 , A 3 musí být násobkem čísel ε A A 3 a zpět. Nechť nejmenší společný násobek čísel ε A A 3 ano ε 1. Dále násobky čísel A 1 , A 2 , A 3 , A 4 musí být násobkem čísel ε 1 a A 4. Nechť nejmenší společný násobek čísel ε 1 a A 4 ano ε 2. Zjistili jsme tedy, že všechny násobky čísel A 1 , A 2 , A 3 ,...,A m se shodují s násobky určitého čísla ε n, které se nazývá nejmenší společný násobek daných čísel.

Ve zvláštním případě, kdy čísla A 1 , A 2 , A 3 ,...,A m jsou relativně prvočísla, pak nejmenší společný násobek čísel A 1 , A 2, jak je znázorněno výše, má tvar (3). Další, od A 3 prvočíslo ve vztahu k číslům A 1 , A 2 pak A 3 prvočíslo A 1 · A 2 (důsledek 1). Znamená nejmenší společný násobek čísel A 1 ,A 2 ,A 3 je číslo A 1 · A 2 · A 3. Uvažováním podobným způsobem dospíváme k následujícím tvrzením.

Prohlášení 1. Nejmenší společný násobek prvočísel A 1 , A 2 , A 3 ,...,A m se rovná jejich součinu A 1 · A 2 · A 3 ··· A m

Prohlášení 2. Jakékoli číslo, které je dělitelné každým z prvočísel A 1 , A 2 , A 3 ,...,A m je také dělitelné jejich součinem A 1 · A 2 · A 3 ··· A m

Ale mnoho přirozených čísel je dělitelných i jinými přirozenými čísly.

Například:

Číslo 12 je dělitelné 1, 2, 3, 4, 6, 12;

Číslo 36 je dělitelné 1, 2, 3, 4, 6, 12, 18, 36.

Čísla, kterými je číslo dělitelné celkem (pro 12 jsou to 1, 2, 3, 4, 6 a 12), se nazývají dělitelé čísel. Dělitel přirozeného čísla A- je přirozené číslo, které dělí dané číslo A beze stopy. Volá se přirozené číslo, které má více než dva dělitele kompozitní.

Vezměte prosím na vědomí, že čísla 12 a 36 mají společné faktory. Tato čísla jsou: 1, 2, 3, 4, 6, 12. Největší dělitel těchto čísel je 12. Společný dělitel těchto dvou čísel A A b- je to číslo, kterým se obě daná čísla beze zbytku dělí A A b.

Společné násobky několik čísel je číslo, které je dělitelné každým z těchto čísel. Například, čísla 9, 18 a 45 mají společný násobek 180. Ale 90 a 360 jsou také jejich společné násobky. Mezi všemi společnými násobky je vždy jeden nejmenší, in v tomto případě toto je 90. Toto číslo se volá nejmenšíspolečný násobek (CMM).

LCM je vždy přirozené číslo, které musí být větší než největší z čísel, pro které je definováno.

Nejmenší společný násobek (LCM). Vlastnosti.

Komutativnost:

Asociativita:

Zejména pokud a - koprime čísla, To:

Nejmenší společný násobek dvou celá čísla m A n je dělitelem všech ostatních společných násobků m A n. Navíc množina společných násobků m, n se shoduje se sadou násobků pro LCM( m, n).

Asymptotiku for lze vyjádřit pomocí některých číselně-teoretických funkcí.

Tak, Čebyševova funkce. A také:

Vyplývá to z definice a vlastností Landauovy funkce g(n).

Co vyplývá ze zákona rozdělení prvočísel.

Hledání nejmenšího společného násobku (LCM).

NOC( a, b) lze vypočítat několika způsoby:

1. Je-li známo největší společný dělitel, můžete použít jeho spojení s LOC:

2. Nechť je znám kanonický rozklad obou čísel na prvočinitele:

Kde p 1,...,p k- různá prvočísla a d 1,..., d k A e 1,...,ek— nezáporná celá čísla (mohou to být nuly, pokud odpovídající prvočíslo není v rozšíření).

Poté NOC ( A,b) se vypočítá podle vzorce:

Jinými slovy, rozklad LCM obsahuje všechna prvočísla multiplikátory, zahrnutý alespoň v jednom z rozšíření čísel a, b a vezme se největší ze dvou exponentů tohoto multiplikátoru.

Příklad:

Výpočet nejmenšího společného násobku několika čísel lze zredukovat na několik po sobě jdoucích výpočtů LCM dvou čísel:

Pravidlo. Chcete-li najít LCM řady čísel, potřebujete:

- rozložit čísla na prvočinitele;

- převést největší rozklad (součin faktorů největšího počtu z daných) na faktory požadovaného součinu a poté přidat faktory z rozkladu dalších čísel, která se v prvním čísle nevyskytují nebo se v něm vyskytují méněkrát;

— výsledným součinem prvočinitelů bude LCM daných čísel.

Libovolná dvě nebo více přirozených čísel mají svůj vlastní LCM. Pokud čísla nejsou navzájem násobky nebo nemají stejné faktory v rozšíření, pak se jejich LCM rovná práce tato čísla.

Prvočísla čísla 28 (2, 2, 7) doplníme činitelem 3 (číslo 21), výsledný součin (84) bude nejmenší číslo, které je dělitelné 21 a 28.

Prvočísla největšího čísla 30 jsou doplněna činitelem 5 čísla 25, výsledný součin 150 je větší než největší číslo 30 a je dělitelný všemi danými čísly beze zbytku. Jedná se o nejmenší možný součin (150, 250, 300...), který je násobkem všech zadaných čísel.

Čísla 2,3,11,37 jsou prvočísla, jejich LCM se tedy rovná součinu daných čísel.

Pravidlo. Chcete-li vypočítat LCM prvočísel, musíte všechna tato čísla vynásobit dohromady.

Další možnost:

K nalezení nejmenšího společného násobku (LCM) několika čísel potřebujete:

1) reprezentovat každé číslo jako součin jeho prvočinitelů, například:

504 = 2 2 2 3 3 7,

2) zapište mocniny všech prvočinitelů:

504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,

3) zapište všechny prvočíselné dělitele (násobiče) každého z těchto čísel;

4) vyberte největší stupeň každého z nich, který se nachází ve všech rozšířeních těchto čísel;

5) vynásobte tyto síly.

Příklad. Najděte LCM čísel: 168, 180 a 3024.

Řešení. 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.

Zapíšeme největší mocniny všech prvočíselných dělitelů a vynásobíme je:

NOC = 2 4 3 3 5 1 7 1 = 15120.

Společné násobky

Jednoduše řečeno, každé celé číslo, které je dělitelné každým z daných čísel, je společný násobek daná celá čísla.

Můžete najít společný násobek dvou nebo více celých čísel.

Příklad 1

Vypočítejte společný násobek dvou čísel: $2$ a $5$.

Řešení.

Podle definice je společný násobek $2$ a $5$ $10, protože je to násobek čísla $2$ a čísla $5$:

Společné násobky čísel $2$ a $5$ budou také čísla $–10, 20, –20, 30, –30 $ atd., protože všechny jsou rozděleny do čísel $2$ a $5$.

Poznámka 1

Nula je společný násobek libovolného počtu nenulových celých čísel.

Podle vlastností dělitelnosti, je-li určité číslo společným násobkem více čísel, pak číslo opačné ve znaménku bude také společným násobkem daných čísel. To lze vidět z uvažovaného příkladu.

U daných celých čísel můžete vždy najít jejich společný násobek.

Příklad 2

Vypočítejte společný násobek 111 $ a 55 $.

Řešení.

Vynásobme daná čísla: $111\div 55=6105$. Je snadné ověřit, že číslo $6105$ je dělitelné číslem $111$ a číslem $55$:

$6105\div 111=$55;

6105 $\div 55=111 $.

6105 $ je tedy společný násobek 111 $ a 55 $.

Odpověď: Společný násobek 111 $ a 55 $ je 6 105 $.

Ale jak jsme již viděli z předchozího příkladu, tento společný násobek není jedna. Další společné násobky by byly $ –6105, 12210, –12210, 61050, –61050 $ atd. Došli jsme tedy k následujícímu závěru:

Poznámka 2

Libovolná množina celých čísel má nekonečný počet společných násobků.

V praxi se omezují na hledání společných násobků pouze kladných celých (přirozených) čísel, protože množiny násobků daného čísla a jeho opaku se shodují.

Určení nejmenšího společného násobku

Ze všech násobků daných čísel se nejčastěji používá nejmenší společný násobek (LCM).

Definice 2

Nejmenší kladný společný násobek daných celých čísel je nejmenší společný násobek tato čísla.

Příklad 3

Vypočítejte LCM čísel $4$ a $7$.

Řešení.

Protože tato čísla nemají žádné společné dělitele, pak $LCM(4,7)=28$.

Odpověď: $NOK (4,7)=28 $.

Hledání NOC přes GCD

Protože existuje spojení mezi LCM a GCD, s jeho pomocí můžete vypočítat LCM dvou kladných celých čísel:

Poznámka 3

Příklad 4

Vypočítejte LCM čísel $232$ a $84$.

Řešení.

Použijme vzorec k nalezení LCM prostřednictvím GCD:

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

Pojďme najít GCD čísel $ 232 $ a $ 84 $ pomocí euklidovského algoritmu:

232 $=84\cdot 2+64$,

$84=64\cdot 1+20 $,

$64=20\cdot 3+4$,

Tito. $GCD(232, 84)=4$.

Pojďme najít $LCC (232, 84)$:

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

Odpověď: $ NOK (232,84) = $ 4872.

Příklad 5

Vypočítejte $LCD(23, 46)$.

Řešení.

Protože $46$ je dělitelné $23$, pak $gcd (23, 46)=23$. Pojďme najít LOC:

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

Odpověď: $ NOK (23,46) = $ 46.

Tak lze formulovat pravidlo:

Poznámka 4

Největší společný dělitel a nejmenší společný násobek jsou klíčové aritmetické pojmy, díky kterým je práce se zlomky snadná. LCM a se nejčastěji používají k nalezení společného jmenovatele několika zlomků.

Základní pojmy

Dělitel celého čísla X je další celé číslo Y, kterým je X děleno beze zbytku. Například dělitel 4 je 2 a 36 je 4, 6, 9. Násobkem celého čísla X je číslo Y, které je dělitelné X beze zbytku. Například 3 je násobek 15 a 6 je násobek 12.

Pro libovolnou dvojici čísel najdeme jejich společné dělitele a násobky. Například pro 6 a 9 je společný násobek 18 a společný dělitel je 3. Je zřejmé, že páry mohou mít několik dělitelů a násobků, takže výpočty používají největšího dělitele GCD a nejmenšího násobku LCM.

Nejmenší dělitel nemá smysl, protože pro libovolné číslo je vždy jedna. Největší násobek je také bezvýznamný, protože posloupnost násobků jde do nekonečna.

Hledání gcd

Existuje mnoho metod pro nalezení největšího společného dělitele, z nichž nejznámější jsou:

sekvenční vyhledávání dělitelů, výběr společných pro dvojici a hledání největšího z nich;
rozklad čísel na nedělitelné činitele;
Euklidovský algoritmus;
binární algoritmus.

Dnes jsou ve vzdělávacích institucích nejoblíbenějšími metodami rozklad na prvočinitele a euklidovský algoritmus. Ten se zase používá při řešení diofantických rovnic: hledání GCD je nutné pro kontrolu rovnice pro možnost rozlišení v celých číslech.

Hledání NOC

Nejmenší společný násobek je také určen sekvenčním hledáním nebo rozkladem na nedělitelné faktory. Kromě toho je snadné najít LCM, pokud již byl určen největší dělitel. Pro čísla X a Y jsou LCM a GCD spojeny následujícím vztahem:

LCD(X,Y) = X × Y / GCD(X,Y).

Pokud například GCM(15,18) = 3, pak LCM(15,18) = 15 × 18 / 3 = 90. Nejviditelnějším příkladem použití LCM je nalezení společného jmenovatele, což je nejmenší společný násobek dané zlomky.

Coprime čísla

Pokud dvojice čísel nemá žádné společné dělitele, pak se taková dvojice nazývá koprimá. Gcd pro takové páry se vždy rovná jedné a na základě spojení mezi děliteli a násobky je gcd pro páry v koprime rovno jejich součinu. Například čísla 25 a 28 jsou relativně prvočísla, protože nemají žádné společné dělitele, a LCM(25, 28) = 700, což odpovídá jejich součinu. Jakákoli dvě nedělitelná čísla budou vždy relativně prvočísla.

Společný dělitel a vícenásobná kalkulačka

Pomocí naší kalkulačky můžete vypočítat GCD a LCM pro libovolný počet čísel, ze kterých si můžete vybrat. Úkoly týkající se počítání společných dělitelů a násobků se nacházejí v aritmetice 5. a 6. ročníku, ale GCD a LCM jsou klíčové pojmy v matematice a používají se v teorii čísel, planimetrii a komunikativní algebře.

Příklady ze života

Společný jmenovatel zlomků

Nejmenší společný násobek se používá při hledání společného jmenovatele násobných zlomků. Řekněme, že v aritmetickém problému potřebujete sečíst 5 zlomků:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Chcete-li přidat zlomky, výraz musí být redukován na společného jmenovatele, což redukuje na problém nalezení LCM. Chcete-li to provést, vyberte 5 čísel v kalkulačce a zadejte hodnoty jmenovatelů do příslušných buněk. Program vypočítá LCM (8, 9, 12, 15, 18) = 360. Nyní musíte pro každý zlomek vypočítat další faktory, které jsou definovány jako poměr LCM ke jmenovateli. Dodatečné násobiče by tedy vypadaly takto:

360/8 = 45
360/9 = 40
360/12 = 30
360/15 = 24
360/18 = 20.

Poté vynásobíme všechny zlomky odpovídajícím dalším faktorem a dostaneme:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Takové zlomky snadno sečteme a dostaneme výsledek 159/360. Snížíme zlomek o 3 a vidíme konečnou odpověď - 53/120.

Řešení lineárních diofantických rovnic

Lineární diofantické rovnice jsou vyjádřením tvaru ax + by = d. Pokud je poměr d / gcd(a, b) celé číslo, pak je rovnice řešitelná v celých číslech. Pojďme zkontrolovat pár rovnic, abychom zjistili, zda mají celočíselné řešení. Nejprve zkontrolujme rovnici 150x + 8y = 37. Pomocí kalkulačky zjistíme GCD (150,8) = 2. Dělíme 37/2 = 18,5. Číslo není celé, proto rovnice nemá celočíselné kořeny.

Zkontrolujeme rovnici 1320x + 1760y = 10120. Pomocí kalkulačky najděte GCD(1320, 1760) = 440. Vydělte 10120/440 = 23. Výsledkem je celé číslo, proto je diofantická rovnice řešitelná v .

Závěr

GCD a LCM hrají velkou roli v teorii čísel a samotné pojmy jsou široce používány v široké škále oblastí matematiky. Pomocí naší kalkulačky spočítejte největší dělitele a nejmenší násobky libovolného počtu čísel.