Didžiausias bendras daliklis

Didžiausias bendras daliklis (DBD) – didžiausias iš bendrų daliklių sveikiems skaičiams a1, a1, ... an. 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*32; 84=22*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
greatest common divisor
čia p1, ..., pk - įvairūs pirminiai skaičiai, o d1, ..., dk ir e1, ..., ek 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:
greatest common divisor

Jei skaičių yra daugiau nei du, tai a1, ..., an DBD paskaičiuojamas taip:
d2 = gcd(a1, a2);
d3 = gcd(d2, a3);
...
dn = gcd(dn-1, an)
– 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=24*52; 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
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ė
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