Najmanjši skupni večkratnik števil 3 in 4. Kako najti najmanjši skupni večkratnik števil

Toda veliko naravnih števil je deljivih tudi z drugimi naravnimi števili.

Na primer:

Število 12 je deljivo z 1, z 2, s 3, s 4, s 6, z 12;

Število 36 je deljivo z 1, z 2, s 3, s 4, s 6, z 12, z 18, s 36.

Števila, s katerimi je število deljivo s celoto (pri 12 so to 1, 2, 3, 4, 6 in 12), se imenujejo delitelji števil. Delitelj naravnega števila a- je naravno število, ki deli dano število a brez sledu. Naravno število, ki ima več kot dva delitelja, imenujemo sestavljeno .

Upoštevajte, da imata števili 12 in 36 skupne faktorje. Ta števila so: 1, 2, 3, 4, 6, 12. Največji delitelj teh števil je 12. Skupni delitelj teh dveh števil a in b- to je število, s katerim sta obe dani števili deljeni brez ostanka a in b.

Skupni večkratniki več števil je število, ki je deljivo z vsakim od teh števil. Na primer, imajo števila 9, 18 in 45 skupni večkratnik 180. Toda 90 in 360 sta tudi njuna skupna večkratnika. Med vsemi skupnimi mnogokratniki je vedno najmanjši, v tem primeru je to 90. To število imenujemo najmanjšiskupni večkratnik (CMM).

LCM je vedno naravno število, ki mora biti večje od največjega izmed števil, za katera je definirano.

Najmanjši skupni večkratnik (LCM). Lastnosti.

Komutativnost:

Asociativnost:

Zlasti, če sta in soprosti števili, potem:

Najmanjši skupni večkratnik dveh celih števil m in n je delitelj vseh drugih skupnih mnogokratnikov m in n. Poleg tega množica skupnih večkratnikov m, n sovpada z množico večkratnikov LCM( m, n).

Asimptotiko za je mogoče izraziti v smislu nekaterih številsko-teoretičnih funkcij.

Torej, Čebiševljeva funkcija. In tudi:

To izhaja iz definicije in lastnosti Landauove funkcije g(n).

Kaj sledi iz zakona porazdelitve praštevil.

Iskanje najmanjšega skupnega večkratnika (LCM).

NOC( a, b) se lahko izračuna na več načinov:

1. Če je največji skupni delitelj znan, lahko uporabite njegovo povezavo z LCM:

2. Naj je znana kanonična razgradnja obeh števil na prafaktorje:

kje p 1 ,...,p k- različna praštevila in d 1 ,...,d k in e 1 ,...,e k— nenegativna cela števila (lahko so ničle, če ustreznega praštevila ni v razširitvi).

Nato NOC ( a,b) se izračuna po formuli:

Z drugimi besedami, razčlenitev LCM vsebuje vse prafaktorje, vključene v vsaj eno od razčlenitev števil a, b, in vzame se največji od dveh eksponentov tega množitelja.

Primer:

Izračun najmanjšega skupnega večkratnika več števil se lahko zmanjša na več zaporednih izračunov LCM dveh števil:

Pravilo.Če želite najti LCM serije števil, potrebujete:

- razstavljajo števila na prafaktorje;

- največji razpad (zmnožek faktorjev največjega števila danih) prenesemo na faktorje želenega produkta, nato pa dodamo faktorje iz razčlenitve ostalih števil, ki se ne pojavljajo v prvem številu ali se pojavljajo v njem. manjkrat;

— dobljeni produkt prafaktorjev bo LCM danih števil.

Vsaki dve ali več naravnih števil ima svoj LCM. Če številki nista večkratnika ali nimata enakih faktorjev v razširitvi, potem je njun LCM enak produktu teh števil.

Prafaktorje števila 28 (2, 2, 7) dopolnimo s faktorjem 3 (število 21), dobljeni produkt (84) bo najmanjše število, ki je deljivo z 21 in 28.

Prafaktorje največjega števila 30 dopolnimo s faktorjem 5 števila 25, dobljeni produkt 150 je večji od največjega števila 30 in je deljiv z vsemi danimi števili brez ostanka. To je najmanjši možni produkt (150, 250, 300 ...), ki je večkratnik vseh danih števil.

Števila 2,3,11,37 so praštevila, zato je njihov LCM enak produktu danih števil.

Pravilo. Če želite izračunati LCM praštevil, morate vsa ta števila pomnožiti skupaj.

Druga možnost:

Če želite najti najmanjši skupni večkratnik (LCM) več števil, potrebujete:

1) predstavi vsako število kot produkt njegovih prafaktorjev, na primer:

504 = 2 2 2 3 3 7,

2) zapiši potence vseh prafaktorjev:

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

3) zapišite vse glavne delitelje (množitelje) vsakega od teh števil;

4) izberite največjo stopnjo vsakega od njih, ki jo najdete v vseh razširitvah teh števil;

5) pomnožite te moči.

Primer. Poiščite LCM števil: 168, 180 in 3024.

rešitev. 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.

Zapišemo največje potence vseh pradeliteljev in jih pomnožimo:

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

Da bi razumeli, kako izračunati LCM, morate najprej določiti pomen izraza "več".

Večkratnik A je naravno število, ki je deljivo z A brez ostanka. Število, ki je večkratnik števila 5, lahko štejemo za 15, 20, 25 itd.

Obstaja lahko omejeno število deliteljev določenega števila, obstaja pa neskončno število večkratnikov.

Skupni večkratnik naravnih števil je število, ki je z njimi deljivo brez ostanka.

Kako najti najmanjši skupni večkratnik števil

Najmanjši skupni večkratnik (LCM) števil (dva, tri ali več) je najmanjše naravno število, ki je deljivo z vsemi temi števili.

Če želite najti LOC, lahko uporabite več metod.

Za majhna števila je priročno zapisati vse večkratnike teh števil v črto, dokler med njimi ne najdete nekaj skupnega. Večkratnike označujemo z veliko črko K.

Na primer, večkratnike števila 4 lahko zapišemo takole:

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

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

Tako lahko vidite, da je najmanjši skupni večkratnik števil 4 in 6 število 24. Ta zapis je narejen na naslednji način:

LCM(4, 6) = 24

Če so številke velike, poiščite skupni večkratnik treh ali več števil, potem je bolje uporabiti drugo metodo izračuna LCM.

Za dokončanje naloge morate dana števila razložiti na prafaktorje.

Najprej morate na črto zapisati razgradnjo največjega števila, pod njim pa ostalo.

Razčlenitev vsakega števila lahko vsebuje različno število faktorjev.

Na primer, razložimo števili 50 in 20 na prafaktorje.

Pri razširitvi manjšega števila izpostavite faktorje, ki manjkajo pri razširitvi prvega največjega števila, in jih nato dodajte k temu. V predstavljenem primeru manjka dvojka.

Zdaj lahko izračunate najmanjši skupni večkratnik 20 in 50.

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

Tako bo zmnožek prafaktorjev večjega števila in faktorjev drugega števila, ki niso bili vključeni v razširitev večjega števila, najmanjši skupni večkratnik.

Če želite najti LCM treh ali več števil, jih morate vse razložiti na prafaktorje, kot v prejšnjem primeru.

Kot primer lahko poiščete najmanjši skupni večkratnik števil 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

Tako le dve dvojki iz razširitve šestnajstice nista bili vključeni v faktorizacijo večjega števila (ena je v razširitvi štiriindvajsetice).

Tako jih je treba razširitvi dodati večje število.

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

Obstajajo posebni primeri določanja najmanjšega skupnega večkratnika. Torej, če je mogoče eno od števil brez ostanka deliti z drugim, potem bo večje od teh števil najmanjši skupni večkratnik.

Na primer, LCM za dvanajst in štiriindvajset je štiriindvajset.

Če je treba najti najmanjši skupni večkratnik soprostih števil, ki nimajo enakih deliteljev, bo njihov LCM enak njihovemu produktu.

Na primer, LCM (10, 11) = 110.

Največji skupni delitelj

Definicija 2

Če je naravno število a deljivo z naravnim številom $b$, potem $b$ imenujemo delitelj $a$, $a$ pa večkratnik $b$.

Naj bosta $a$ in $b$ naravni števili. Število $c$ imenujemo skupni delitelj obeh $a$ in $b$.

Množica skupnih deliteljev števil $a$ in $b$ je končna, saj nobeden od teh deliteljev ne more biti večji od $a$. To pomeni, da je med temi delitelji največji, ki ga imenujemo največji skupni delitelj števil $a$ in $b$ in ga označujemo z naslednjimi zapisi:

$GCD\(a;b)\ ali \D\(a;b)$

Če želite najti največji skupni delitelj dveh števil, potrebujete:

1. Poiščite zmnožek števil iz 2. koraka. Dobljeno število bo želeni največji skupni delitelj.

Primer 1

Poiščite gcd števil $121$ in $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Izberite številke, ki so vključene v razširitev teh številk

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Poiščite zmnožek števil iz 2. koraka. Dobljeno število bo želeni največji skupni delitelj.

$GCD=2\cdot 11=22$

Primer 2

Poiščite gcd monomov $63$ in $81$.

Poiskali bomo po predstavljenem algoritmu. Če želite to narediti:

Razložimo števila na prafaktorje

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Izberemo številke, ki so vključene v razširitev teh številk

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Poiščimo zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni največji skupni delitelj.

$GCD=3\cdot 3=9$

Gcd dveh števil lahko najdete na drug način, z uporabo niza deliteljev števil.

Primer 3

Poiščite gcd števil $48$ in $60$.

rešitev:

Poiščimo množico deliteljev števila $48$: $\levo\((\rm 1,2,3.4.6,8,12,16,24,48)\desno\)$

Zdaj pa poiščimo množico deliteljev števila $60$:$\ \levo\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\desno\) $

Poiščimo presečišče teh množic: $\left\((\rm 1,2,3,4,6,12)\right\)$ - ta množica bo določala množico skupnih deliteljev števil $48$ in $60 $. Največji element v tem nizu bo številka $12$. To pomeni, da je največji skupni delitelj števil $48$ in $60$ 12$.

Opredelitev NPL

Definicija 3

Navadni mnogokratniki naravnih števil$a$ in $b$ je naravno število, ki je večkratnik tako $a$ kot $b$.

Skupni večkratniki števil so števila, ki so deljiva z izvirnimi števili brez ostanka. Na primer, za števili $25$ in $50$ bodo skupni večkratniki števila $50,100,150,200$ itd.

Najmanjši skupni večkratnik bomo imenovali najmanjši skupni večkratnik in ga označili z LCM$(a;b)$ ali K$(a;b).$

Če želite najti LCM dveh števil, morate:

1. Razčlenite števila na prafaktorje
2. Zapišite faktorje, ki so del prvega števila in jim dodajte faktorje, ki so del drugega in niso del prvega.

Primer 4

Poiščite LCM števil $99$ in $77$.

Poiskali bomo po predstavljenem algoritmu. Za to

Razčlenite števila na prafaktorje

99 $=3\cdot 3\cdot 11$

Zapišite dejavnike, vključene v prvi

dodajte jim množitelje, ki so del drugega in ne del prvega

Poiščite zmnožek števil, najdenih v koraku 2. Dobljeno število bo želeni najmanjši skupni večkratnik

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

Sestavljanje seznamov deliteljev števil je pogosto zelo delovno intenzivna naloga. Obstaja način za iskanje GCD, imenovan evklidski algoritem.

Izjave, na katerih temelji evklidski algoritem:

Če sta $a$ in $b$ naravni števili in $a\vpike b$, potem je $D(a;b)=b$

Če sta $a$ in $b$ naravni števili, tako da $b

Z uporabo $D(a;b)= D(a-b;b)$ lahko zaporedoma zmanjšujemo obravnavana števila, dokler ne dosežemo para števil, tako da je eno od njiju deljivo z drugim. Potem bo manjše od teh števil želeni največji skupni delitelj za števili $a$ in $b$.

Lastnosti GCD in LCM

1. Vsak skupni večkratnik $a$ in $b$ je deljiv s K$(a;b)$
2. Če $a\vpike b$ , potem К$(a;b)=a$

Če je K$(a;b)=k$ in je $m$ naravno število, potem je K$(am;bm)=km$

Če je $d$ skupni delitelj za $a$ in $b$, potem je K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Če $a\vdots c$ in $b\vdots c$, potem je $\frac(ab)(c)$ skupni večkratnik $a$ in $b$

Za poljubni naravni števili $a$ in $b$ velja enakost

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

Vsak skupni delitelj števil $a$ in $b$ je delitelj števila $D(a;b)$

Večkratnik je število, ki je deljivo z danim številom brez ostanka. Najmanjši skupni večkratnik (LCM) skupine števil je najmanjše število, ki je deljivo z vsakim številom v skupini brez ostanka. Če želite najti najmanjši skupni večkratnik, morate najti prafaktorje danih števil. LCM je mogoče izračunati tudi z uporabo številnih drugih metod, ki veljajo za skupine dveh ali več števil.

Koraki

Serija večkratnikov

Poglej te številke. Tukaj opisano metodo je najbolje uporabiti, če imate dve števili, od katerih je vsako manjše od 10. Če so podana večja števila, uporabite drugo metodo.

• Na primer, poiščite najmanjši skupni večkratnik 5 in 8. To so majhne številke, zato lahko uporabite to metodo.

1. Večkratnik je število, ki je deljivo z danim številom brez ostanka. Večkratnike najdete v tabeli množenja.

   • Na primer, števila, ki so večkratnika števila 5, so: 5, 10, 15, 20, 25, 30, 35, 40.

2. Zapišite niz števil, ki so večkratniki prvega števila. Naredite to pod večkratniki prvega števila, da primerjate dva niza števil.

   • Na primer, števila, ki so večkratnika števila 8, so: 8, 16, 24, 32, 40, 48, 56 in 64.

3. Poiščite najmanjše število, ki je prisotno v obeh nizih mnogokratnikov. Morda boste morali napisati dolg niz večkratnikov, da boste našli skupno število. Najmanjše število, ki je prisotno v obeh nizih večkratnikov, je najmanjši skupni večkratnik.

   • Na primer, najmanjše število, ki se pojavi v nizu večkratnikov 5 in 8, je število 40. Zato je 40 najmanjši skupni večkratnik 5 in 8.

   Prafaktorizacija

   1. Poglej te številke. Tukaj opisano metodo je najbolje uporabiti, če imate dve števili, od katerih je vsako večje od 10. Če so podane manjše številke, uporabite drugo metodo.

      • Na primer, poiščite najmanjši skupni večkratnik števil 20 in 84. Vsako število je večje od 10, zato lahko uporabite to metodo.

   2. Prvo število razčlenite na prafaktorje. To pomeni, da morate najti takšna praštevila, ki bodo pomnožena z danim številom. Ko najdete prafaktorje, jih zapišite kot enačbe.

      • na primer 2 × 10 = 20 (\displaystyle (\mathbf (2) )\krat 10=20) in 2 × 5 = 10 (\displaystyle (\mathbf (2) )\krat (\mathbf (5) )=10). Tako so prafaktorji števila 20 števila 2, 2 in 5. Zapiši jih kot izraz: .

   3. Drugo število razčlenite na prafaktorje. Naredite to na enak način, kot ste faktorizirali prvo število, torej poiščite taka praštevila, ki bodo pri množenju dala dano število.

      • na primer 2 × 42 = 84 (\displaystyle (\mathbf (2) )\krat 42=84), 7 × 6 = 42 (\displaystyle (\mathbf (7) )\krat 6=42) in 3 × 2 = 6 (\displaystyle (\mathbf (3) )\krat (\mathbf (2) )=6). Tako so prafaktorji števila 84 števila 2, 7, 3 in 2. Zapiši jih kot izraz: .

   4. Zapišite faktorje, ki so skupni obema številoma. Takšne faktorje zapišite kot operacijo množenja. Ko pišete vsak faktor, ga prečrtajte v obeh izrazih (izrazih, ki opisujejo faktorizacijo števil na prafaktorje).

      • Na primer, obe števili imata skupni faktor 2, zato zapišite 2 × (\displaystyle 2\krat ) in prečrtaj 2 v obeh izrazih.
      • Obema številoma je skupen še faktor 2, zato zapiši 2 × 2 (\displaystyle 2\krat 2) in prečrtaj drugi 2 v obeh izrazih.

   5. Operaciji množenja dodajte preostale faktorje. To so faktorji, ki v obeh izrazih niso prečrtani, torej faktorji, ki obema številoma niso skupni.

      • Na primer v izrazu 20 = 2 × 2 × 5 (\displaystyle 20=2\krat 2\krat 5) Oba dvojca (2) sta prečrtana, ker sta skupna faktorja. Faktor 5 ni prečrtan, zato operacijo množenja zapiši takole: 2 × 2 × 5 (\displaystyle 2\krat 2\krat 5)
      • V izrazu 84 = 2 × 7 × 3 × 2 (\displaystyle 84=2\krat 7\krat 3\krat 2) oba dva (2) sta tudi prečrtana. Faktorja 7 in 3 nista prečrtana, zato operacijo množenja zapiši takole: 2 × 2 × 5 × 7 × 3 (\displaystyle 2\krat 2\krat 5\krat 7\krat 3).

   6. Izračunaj najmanjši skupni večkratnik.Če želite to narediti, pomnožite števila v operaciji pisnega množenja.

      • na primer 2 × 2 × 5 × 7 × 3 = 420 (\displaystyle 2\krat 2\krat 5\krat 7\krat 3=420). Torej je najmanjši skupni večkratnik 20 in 84 420.

   Iskanje skupnih dejavnikov

   1. Narišite mrežo kot za igro tic-tac-toe. Takšna mreža je sestavljena iz dveh vzporednih črt, ki se sekata (pod pravim kotom) z drugima dvema vzporednima črtama. Tako boste dobili tri vrstice in tri stolpce (mreža je zelo podobna ikoni #). Napišite prvo številko v prvo vrstico in drugi stolpec. Drugo številko zapišite v prvo vrstico in tretji stolpec.

      • Na primer, poiščite najmanjši skupni večkratnik števil 18 in 30. V prvo vrstico in drugi stolpec zapišite število 18, v prvo vrstico in tretji stolpec pa število 30.

   2. Poišči delitelj, ki je skupen obema številoma. Zapišite v prvo vrstico in prvi stolpec. Bolje je iskati prafaktorje, vendar to ni pogoj.

      • Na primer, 18 in 30 sta sodi števili, zato je njun skupni faktor 2. Zato zapišite 2 v prvo vrstico in prvi stolpec.

   3. Vsako število delite s prvim deliteljem. Vsak količnik zapiši pod ustrezno številko. Količnik je rezultat deljenja dveh števil.

      • na primer 18 ÷ 2 = 9 (\displaystyle 18\div 2=9), torej pod 18 napišite 9.
      • 30 ÷ 2 = 15 (\displaystyle 30\div 2=15), torej zapišite 15 pod 30.

   4. Poiščite delitelj, ki je skupen obema količnikoma.Če takega delitelja ni, preskočite naslednja dva koraka. V nasprotnem primeru delitelj vpiši v drugo vrstico in prvi stolpec.

      • Na primer, 9 in 15 sta deljiva s 3, zato zapišite 3 v drugo vrstico in prvi stolpec.

   5. Vsak količnik delite z njegovim drugim deliteljem. Vsak rezultat deljenja zapišite pod pripadajoči količnik.

      • na primer 9 ÷ 3 = 3 (\displaystyle 9\div 3=3), torej pod 9 napišite 3.
      • 15 ÷ 3 = 5 (\displaystyle 15\div 3=5), torej pod 15 napišite 5.

   6. Po potrebi dodajte dodatne celice v mrežo. Ponavljaj opisane korake, dokler imata količnika skupni delitelj.

   7. Obkroži številke v prvem stolpcu in zadnji vrstici mreže. Nato izbrana števila zapiši kot operacijo množenja.

      • Na primer, števili 2 in 3 sta v prvem stolpcu, števili 3 in 5 pa v zadnji vrstici, zato operacijo množenja zapišite takole: 2 × 3 × 3 × 5 (\displaystyle 2\krat 3\krat 3\krat 5).

   8. Poiščite rezultat množenja števil. To bo izračunalo najmanjši skupni večkratnik dveh danih števil.

      • na primer 2 × 3 × 3 × 5 = 90 (\displaystyle 2\krat 3\krat 3\krat 5=90). Torej je najmanjši skupni večkratnik 18 in 30 90.

   Evklidov algoritem

   1. Zapomnite si terminologijo, povezano z operacijo deljenja. Dividenda je število, ki se deli. Delitelj je število, s katerim se deli. Količnik je rezultat deljenja dveh števil. Ostanek je število, ki ostane, ko dve števili delimo.

      • Na primer v izrazu 15 ÷ 6 = 2 (\displaystyle 15\div 6=2) ost. 3:
        15 je dividenda
        6 je delitelj
        2 je količnik
        3 je ostanek.

Druga številka: b=

Ločilo tisočic Brez ločila presledkov "´

rezultat:

Največji skupni delitelj gcd( a,b)=6

Najmanjši skupni večkratnik LCM( a,b)=468

Največje naravno število, ki ga lahko brez ostanka delimo s številoma a in b, imenujemo največji skupni delitelj(GCD) teh številk. Označeno z gcd(a,b), (a,b), gcd(a,b) ali hcf(a,b).

Najmanjši skupni večkratnik LCM dveh celih števil a in b je najmanjše naravno število, ki je deljivo z a in b brez ostanka. Označeno z LCM(a,b) ali lcm(a,b).

Celi števili a in b se imenujeta medsebojno prime, če nimata skupnih deliteljev, razen +1 in −1.

Največji skupni delitelj

Naj sta podani dve pozitivni števili a 1 in a 2 1). Najti je treba skupni delitelj teh števil, tj. najti tako številko λ , ki deli števila a 1 in a 2 hkrati. Opišimo algoritem.

1) V tem članku bomo besedo številka razumeli kot celo število.

Naj a 1 ≥ a 2 in pusti

kje m 1 , a 3 je nekaj celih števil, a 3 <a 2 (ostanek delitve a 1 na a 2 mora biti manj a 2).

Predpostavimo, da λ deli a 1 in a 2 potem λ deli m 1 a 2 in λ deli a 1 −m 1 a 2 =a 3 (2. trditev članka »Deljivost števil. Preizkus deljivosti«). Iz tega sledi, da vsak skupni delitelj a 1 in a 2 je skupni delitelj a 2 in a 3. Tudi obratno velja, če λ skupni delilnik a 2 in a 3 potem m 1 a 2 in a 1 =m 1 a 2 +a 3 je tudi deljivo s λ . Torej skupni delitelj a 2 in a 3 je tudi skupni delitelj a 1 in a 2. Ker a 3 <a 2 ≤a 1, potem lahko rečemo, da je rešitev problema iskanja skupnega delitelja števil a 1 in a 2 zmanjšana na enostavnejši problem iskanja skupnega delitelja števil a 2 in a 3 .

če a 3 ≠0, potem lahko delimo a 2 naprej a 3. Potem

,

kje m 1 in a 4 je nekaj celih števil, ( a 4 ostanek pri deljenju a 2 naprej a 3 (a 4 <a 3)). S podobnim razmišljanjem pridemo do zaključka, da so skupni delitelji števil a 3 in a 4 sovpada s skupnimi delitelji števil a 2 in a 3, pa tudi s skupnimi delilniki a 1 in a 2. Ker a 1 , a 2 , a 3 , a 4, ... so števila, ki nenehno padajo, in ker je med njimi končno število celih števil a 2 in 0, nato na nekem koraku n, ostanek deljenja a n naprej a n+1 bo enako nič ( a n+2 =0).

.

Vsak skupni delitelj λ številke a 1 in a 2 je tudi delitelj števil a 2 in a 3 , a 3 in a 4 , .... a n in a n+1 . Velja tudi obratno, skupni delitelji števil a n in a n+1 so tudi delitelji števil a n−1 in a n, ...., a 2 in a 3 , a 1 in a 2. Toda skupni delitelj števil a n in a n+1 je število a n+1, ker a n in a n+1 so deljivi s a n+1 (zapomni si to a n+2 =0). Zato a n+1 je tudi delitelj števil a 1 in a 2 .

Upoštevajte, da je številka a n+1 je največji delitelj števil a n in a n+1 , saj je največji delitelj a n+1 je sam a n+1 . če a n+1 lahko predstavimo kot zmnožek celih števil, potem so ta števila tudi običajni delitelji števil a 1 in a 2. številka a n+1 se imenuje največji skupni deliteljštevilke a 1 in a 2 .

Številke a 1 in a 2 so lahko pozitivna ali negativna števila. Če je eno od števil enako nič, potem bo največji skupni delitelj teh števil enak absolutni vrednosti drugega števila. Največji skupni delitelj števil nič je nedefiniran.

Pokliče se zgornji algoritem Evklidski algoritem najti največji skupni delitelj dveh celih števil.

Primer iskanja največjega skupnega delitelja dveh števil

Poiščite največji skupni delitelj dveh števil 630 in 434.

• Korak 1. Število 630 delite s 434. Ostanek je 196.
• Korak 2. Število 434 delite s 196. Ostanek je 42.
• Korak 3. Število 196 razdelite na 42. Ostanek je 28.
• Korak 4. Število 42 delite z 28. Ostanek je 14.
• 5. korak. Število 28 delite s 14. Ostanek je 0.

V 5. koraku je ostanek deljenja 0. Zato je največji skupni delitelj števil 630 in 434 14. Upoštevajte, da sta števili 2 in 7 tudi delitelja števil 630 in 434.

Kopraštevila

Opredelitev 1. Naj bo največji skupni delitelj števil a 1 in a 2 je enako ena. Nato se pokličejo te številke soprosta števila, ki nima skupnega delitelja.

Izrek 1. če a 1 in a 2 soprosti števili in λ neko število, nato poljuben skupni delitelj števil λa 1 in a 2 je tudi skupni delitelj števil λ in a 2 .

Dokaz. Razmislite o evklidskem algoritmu za iskanje največjega skupnega delitelja števil a 1 in a 2 (glej zgoraj).

.

Iz pogojev izreka sledi, da je največji skupni delitelj števil a 1 in a 2 in zato a n in a n+1 je 1. To je a n+1 =1.

Pomnožimo vse te enakosti z λ , Potem

.

Naj skupni delilec a 1 λ in a 2 da δ . Potem δ je vključen kot množitelj v a 1 λ , m 1 a 2 λ in v a 1 λ -m 1 a 2 λ =a 3 λ (glej "Deljivost števil", trditev 2). Naprej δ je vključen kot množitelj v a 2 λ in m 2 a 3 λ , in je zato vključen kot dejavnik v a 2 λ -m 2 a 3 λ =a 4 λ .

Če tako razmišljamo, smo prepričani, da δ je vključen kot množitelj v a n−1 λ in m n−1 a n λ , in torej v a n−1 λ −m n−1 a n λ =a n+1 λ . Ker a n+1 =1, torej δ je vključen kot množitelj v λ . Zato število δ je skupni delitelj števil λ in a 2 .

Oglejmo si posebne primere izreka 1.

Posledica 1. Naj a in c Praštevila so relativna b. Nato njihov izdelek ac je praštevilo glede na b.

res. Iz izreka 1 ac in b imajo enake skupne delitelje kot c in b. Ampak številke c in b razmeroma preprosto, tj. imajo en sam skupni delitelj 1. Potem ac in b imajo tudi en sam skupni delitelj 1. Zato ac in b medsebojno preprosta.

Posledica 2. Naj a in b soprosta števila in pustimo b deli ak. Potem b deli in k.

res. Iz pogoja odobritve ak in b imajo skupni delitelj b. Na podlagi izreka 1, b mora biti skupni delilnik b in k. Zato b deli k.

Posledico 1 lahko posplošimo.

Posledica 3. 1. Naj številke a 1 , a 2 , a 3 , ..., a m so praštevila glede na število b. Potem a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m, je produkt teh števil praštevil glede na število b.

2. Naj imamo dve vrstici številk

tako, da je vsako število v prvem nizu praštevilo v razmerju vsakega števila v drugem nizu. Nato izdelek

Poiskati morate števila, ki so deljiva z vsakim od teh števil.

Če je število deljivo z a 1, potem ima obliko sa 1 kje s neko število. če q je največji skupni delitelj števil a 1 in a 2, torej

kje s 1 je neko celo število. Potem

je najmanjši skupni večkratnik števil a 1 in a 2 .

a 1 in a 2 so relativno praštevila, potem najmanjši skupni večkratnik števil a 1 in a 2:

Najti moramo najmanjši skupni večkratnik teh števil.

Iz zgoraj navedenega sledi, da vsak večkratnik števil a 1 , a 2 , a 3 mora biti večkratnik številk ε in a 3 in nazaj. Najmanjši skupni večkratnik števil ε in a 3 da ε 1. Nato večkratniki števil a 1 , a 2 , a 3 , a 4 mora biti večkratnik številk ε 1 in a 4. Najmanjši skupni večkratnik števil ε 1 in a 4 da ε 2. Tako smo ugotovili, da so vsi večkratniki števil a 1 , a 2 , a 3 ,...,a m sovpadajo z večkratniki določenega števila ε n, ki se imenuje najmanjši skupni večkratnik danih števil.

V posebnem primeru, ko so številke a 1 , a 2 , a 3 ,...,a m relativno praštevila, potem najmanjši skupni večkratnik števil a 1 , a 2, kot je prikazano zgoraj, ima obliko (3). Naprej, saj a 3 praštevila glede na števila a 1 , a 2 potem a 3 praštevilo a 1 · a 2 (posledica 1). Pomeni najmanjši skupni večkratnik števil a 1 ,a 2 ,a 3 je številka a 1 · a 2 · a 3. Če sklepamo na podoben način, pridemo do naslednjih trditev.

Izjava 1. Najmanjši skupni večkratnik soprostih števil a 1 , a 2 , a 3 ,...,a m je enak njihovemu produktu a 1 · a 2 · a 3 ··· a m.

Izjava 2. Vsako število, ki je deljivo z vsakim od soprostih števil a 1 , a 2 , a 3 ,...,a m je tudi deljiv z njihovim produktom a 1 · a 2 · a 3 ··· a m.