Didžiausias bendras daliklis. Vartiklis

Didžiausias bendras daliklis
Didžiausias bendras daliklis (DBD) – didžiausias iš bendrų daliklių sveikiems skaičiams a₁, a₁, ... a_n. Jei jis lygus 1, tada tie skaičiai vadinami tarpusavyje pirminiais. Kartais jis žymimas santrumpa gcd (iš angl. greatest common divisor).
Pavyzdžiui: a) Skaičių 70 ir 105 DBD yra 35; b) skaičiai 7, 8 ir 15 yra tarpusavyje pirminiai.
DBD yra naudingas supaprastinant trupmenas. Pvz.,
 70     2*35    2
---- = ----- = ---
 105    3*35    3
Dviejų skaičių m ir n didžiausias bendras daliklis egzistuoja ir yra vienareikšmiškai apibrėžtas, jei bent vienas iš m ir n nelygus 0.
Didžiausio bendro daliklio suradimas
Efektyvus DBD suradimas yra Euklido algoritmas (žr. >>>>) bei binarinis algoritmas.
Panaudojant skaičių faktorizacijas
Tačiau nesunku paskaičiuoti DBD, jei žinomi skaičių išskaidymai į pirminius daugiklius (faktorizacijos).
Pavyzdžiui, paimkime skaičius 18 ir 84. Jie išskaidomi taip: 18=2*3²; 84=2²*3*7. Tada pastebime, kad abiem skaičiams „persidengia“ daugikliai 2 ir 3, todėl 18 ir 84 DBD bus 2*3 = 6/CODE>
Pastaba: Praktiškai šis metodas taikytinas tik gana mažiems skaičiams, nes didelių skaičių faktorizacija reikalauja daug paskaičiavimų.
Griežtai matematiškai šį metodą galime apibrėžti taip. Tegu čia p₁, ..., p_k - įvairūs pirminiai skaičiai, o d₁, ..., d_k ir e₁, ..., e_k neneigiami skaičiai (jie gali būti lygūs nuliams, jei atitinkamo pirminio skaičiaus nėra išdėstyme). Tada DBD paskaičiuojamas taip:
Jei skaičių yra daugiau nei du, tai a₁, ..., a_n DBD paskaičiuojamas taip: d₂ = gcd(a₁, a₂); d₃ = gcd(d₂, a₃); ... d_n = gcd(d_n-1, a_n) – tai ir yra ieškomas DBD.
Euklido algoritmas
Šis algoritmas yra spartesnis ir panaudoja tą faktą, kad dviejų skaičių DBD dalija ir jų skirtumą.
Algoritmą skaičiams a ir b galime užrašyti taip: gcd(a,0) = a gcd(a,b) = gcd(b, a mod b)
Pavyzdžiui, imkime skaičius 18 ir 84. 84 padaliję iš 18, gausime 4 ir liekaną 12. Tada 18 dalijame iš 12 ir gauname 1 bei liekaną 6. Tada dalijame 12 iš 6 ir gauname 2 ir liekaną 0, - o tai reiškia, kad 6 yra mūsų ieškomas DBD.
Kiti suradimo metodai
[ šis skyrelis už parengtas vėliau ]
Savybės 1. gcd(a, 0)=|a|, nes bet kuris skaičius dalija 0. 2. Kiekvienas bendras a ir b daliklis dalo ir gcd(a, b); Pvz., skaičių 12 ir 18 DBD yra 6, ir jis dalosi iš visų bendrų tų dviejų skaičių daliklių: 1, 2, 3, 6. Iš čia galima padaryti išvadą: skaičių m ir n bendrų daliklių aibė sutampa su jų DBD daliklių aibe. 3. Jei n dalo m, tai jų DBD yra n. Pvz., skaičių 7 ir 21 DBD yra 7. 4. gcd(a*m,a*n)=|a|*gcd(m, n), t.y., galima iškelti bendrą daugiklį. 5. m ir n padalijus iš jų DBD gausime tarpusavyje pirminius skaičius. Pvz., skaičių 18 ir 84 DBD yra 6, tad 3 ir 14 (18/6; 84/6) yra tarpusavyje pirminiai. 6. DBD yra komutatyvus, t.y. gcd(a, b) - gcd(b, a); 7. DBD yra asociatyvus, t.y. gcd(a, gcd(b, c)) = gcd(gcd(a, b), c); 8. DBD yra multiplikatyvus, t.y., jei a ir b yra tarpusavyje pirminiai, tada gcd(a*b,c) = gcd(a,c)*gcd(b,c) Apibendrinimai DBD sąvoka išplečiama į komutatyvius žiedus, pvz., daugianarių žiedą ar Gauso sveikuosius skaičius. Tačiau, kadangi tokiuose žieduose nėra eiliškumo sąvokos, tai DBD juose apibūdinamas pagrindine DBD savybe: DBD yra tas bendras daliklis, kurį dalo visi kiti bendri dalikliai. Tačiau dviejų komutatyvaus žiedo elementų DBD nebūtinai egzistuoja, tuo tarpu Euklido žieduose jis egzistuoja visada. Dalijantys įrankiai Žinoma, kad bet kurį teigiamą skaičių galima išreikšti pirminių skaičių sandauga, pvz., 400=2⁴*5²; 1001=7*11*13; 280 981=43*67*101 Ir tokia „faktorizacija“ yra vienintelė! O iš kitos pusės, jei sandauga ab yra dali iš c, tai bent vienas iš skaičių a arba b yra dalus iš c. Tie faktai atrodo gana akivaizdūs, tačiau jų įrodymai nėra paprasti. Dalyba su liekana. Gerai žinoma procedūra, kaip padalinti skaičius, gaunant liekaną. Padalinkime 1991 iš 31: 1991 | 31 -186 64 131 -124 7 Gausime 64 ir liekaną 7, t.y. 1991=31*64+7. Tai leidžia mums suformuluoti tokį teiginį: Jei a ir b yra sveiki skaičiai ir b > 0, tada egzistuoja sveikas skaičius q toks, kad a=bq+r, kur „liekana“ r yra sveikas skaičius, tenkinantis 0<=r Pratybos Uždavinys nr. 1. Prie upės stovi 8 aukštų namas, kuriame yra kelios laiptinės. Visose laiptinėse kiekviename aukšte yra vienodas butų skaičius. Kažkuriame vienos laiptinės aukšte butai sunumeruoti nuo 97 iki 102. Kuriame aukšte yra 211 butas? Uždavinys nr. 2. Dviejų skaičių sandauga yra lygi 600. Kokią didžiausią bendrą daliklį gali turėti tie du skaičiai? Uždavinys nr. 3. Kokį didžiausią vienodų puokščių galime sudaryti iš 264 baltų ir 192 raudonų tulpių? (negalima palikti nepanaudotų gėlių! ) Pirminiai dvyniai Nulio istorija Pirminiai skaičiai Dalyba iš nulio Kvadratinė lygtis Aritmetikos pagrindai Kokiu greičiu skriejame? Skaičiai – apžvalga/ pradmenys Parabolės lenktas likimas Nepaprasti Visatos skaičiai: 8 Gauso skaičių teorijos kursas Matematika Egipte ir Finikijoje Da Vinči matematinė klaidelė Pagrindinė aritmetikos teorema Aukso gysla Ramanadžano lygtims Naujas pirminių skaičių dėsningumas Matematika Egipte: Rindo papirusas ir kt. Alef paslaptis: begalybės paieškos A. Puankarė. Mokslas ir hipotezė Nauja pirminių skaičių klasė Hipokratas iš Chijo salos Ar įrodytas abc teiginys? Pirmasis Einšteino įrodymas Euklidas iš Aleksandrijos Harmoninės eilutės Pitagoro teorema Ar viskas čia taip? Beal'o hipotezė Ferma teorema Topologija