A matematika , a GCD egészek eltérő nulla van, többek között a osztók közös ezeknél egész , a legnagyobb közülük. A GCD a legnagyobb közös osztót jelenti .
Például a 30 pozitív osztói sorrendben: 1, 2, 3, 5, 6, 10, 15 és 30. A 18-asok 1, 2, 3, 6, 9 és 18. és 18 értéke 1, 2, 3 és 6, a GCD értéke 6. Amit megjegyezünk: GCD (30, 18) = 6.
A több egész számra vonatkozó osztók a GCD osztói. Két nem nulla a és b egész szám GCD ismerete lehetővé teszi a törtrész egyszerűsítését nál nélb. Különböző érveléssel határozható meg, beleértve az Euclid algoritmust is .
Két egész a és b egész GCD- jét általában GCD-nek ( a , b ) vagy pgcd ( a , b ) jelöljük . Néha a rövidítés egyenértékű a PGDC-vel, de a PGCD a hivatalos verzió.
GCD ( a , b ) néha jegyezni a ∧ b . Ez a jelölés rendezett halmazokra vonatkozik: az a és b közös osztók felosztják GCD-jüket.
Az angolul beszélők ezt hívják a legnagyobb közös osztónak , a jegyzett gcd ( a , b ) -nek vagy a legmagasabb közös tényezőnek , amelyet a hcf ( a , b ) jegyez .
Bármely n egész számnak van legalább egy osztója: 1, mivel írhatunk n = n × 1 . Két a és b egész szám esetén tehát figyelembe vehetjük az összes közös osztójuk D halmazát, amely nem üres, mivel 1-et tartalmaz.
A GCD két egész szám egy és b van a legnagyobb számú tartozó set D valamennyi közös osztója a és b .
A GCD meghatározható egész természetes vagy relatív számokra . De egy egész szám bármely osztója egyben az ellentétének is . A GCD-re vonatkozó számításokat és bemutatásokat ezért általában pozitív egész számokon hajtják végre, a negatívokra való kiterjesztés azonnali.
Legyen a , b , c három nem nulla egész szám.
Figyelembe véve, hogy bármelyik egész szám nulla osztó (mert 0 × c = 0, függetlenül attól, hogy c ), akkor az következik, hogy bármely a > 0 egész szám esetén GCD ( a , 0) = GCD (0, a ) = a .
A szokásos meghatározás nem teszi lehetővé a GCD (0, 0) definiálását, mivel nincs nagyobb 0-os osztó. Megállapodás alapján állítjuk be a GCD (0, 0) = 0. Ha azonban egy másik módszert tekintünk nagyobbnak ( a jelentése nagyobb , mint b ha egy többszöröse b ), ezen egyezmény összhangban van a meghatározás. Ez az új megközelítés szerepel a GCD általános meghatározásában .
Két pozitív a és b egész szám GCD-je összefüggésben van a PPCM-mel (a közös többszöröseik közül a legkisebb), a relációval
ab = GCD ( a , b ) × PPCM ( a , b ).Három nem nulla relatív egész számra, a , b , c :
. Kiterjeszthetünk tetszőleges számú elemre.
Nyilvánvaló, hogy két szám bármelyik GCD-osztója szintén közös osztója ennek a két számnak. Ez fordítva igaz: két egész szám közös osztója pontosan a GCD osztója. Például, ha két a és b egész szám GCD értéke 6, akkor az a és b közös osztók a 6-os osztók lesznek, nevezetesen: 1, 2, 3, 6 és ellentéteik.
Demonstráció1 ° Legyen a és b a két egész szám, és J legyen a pozitív vagy nulla n egész szám halmaza , amelyre két relatív p és q egész szám van, így:
n = pa + qb
Legyen c a J legkisebb, nem nulla egész száma.
c = ra + sb
Bármilyen közös osztója a , és b , ezért osztója C és különösen a legnagyobb közös osztója a , és b , amely tehát kisebb, mint vagy egyenlő c .
2 ° Legyen n lehet bármely elemének J, és hagyja, hogy az R lehet a fennmaradó részlege N által c :
r = n - cm = (p - mr) a + (q - ms) b
Tehát r J-hez tartozik, és szigorúan kisebb, mint c : csak nulla lehet. Ebből következik, hogy J minden eleme többszöröse c-nek , különösen a és b . Tehát c egy közös osztója a és b , valamint nagyobb, vagy egyenlő, mint a GCD szerint az első rész, ez egyenlő a legnagyobb közös osztója, amely tehát osztható bármely közös osztója a és b is, aszerint, hogy a első rész része. CQFD
Ez fordítva igaz: az egyetlen pozitív D szám, amely mindkét tulajdonságot kielégíti:
D osztja a és b ; bármely egész szám, amely osztja az a-t és a b-t, osztja a D-t is ;a és b GCD-je .
Ezt a két mondatot néha a GCD definíciójának tekintik, ami lehetővé teszi az egész számoktól eltérő halmazokra való kiterjesztést is (lásd a GCD cikkét ). De ha eltávolítjuk a pozitív jelzőt , akkor egy másik egész szám kielégíti ezt a tulajdonságot: az a és b GCD ellentéte . Például két D szám igazolja
D 30. és 18. osztja; bármely egész szám, amely elosztja a 30-at és a 18-ot, szintén osztja a D-t ;a 6 és a -6.
Ez azt mutatja, hogy ha b osztója a egy , akkor a legnagyobb közös osztója a és b jelentése b .
A GCD részben kompatibilis a szorzással :
az a , b és k összes nem nulla egész számra GCD ( ka , kb ) = k GCD ( a , b ).De nem a kiegészítéssel . Például GCD (9, 12) = 3, de 2 hozzáadásával GCD (11, 14) = 1, míg 3-val szorozva GCD-t (27, 36) = 9 kapunk.
Lehetséges azonban az a vagy b két szám egyikének a + b- vel való helyettesítése a GCD megváltoztatása nélkül. Általánosságban elmondható, hogy a kettő közül az egyik összeadhatja vagy kivonhatja a másik többszörösét. Formálisabban:
Tétel - Legyen a , b , v három egész szám, majd GCD ( a , b ) = GCD ( a + bv , b ).
Ez a tulajdonság igazolja az Euclid algoritmusát , egy olyan módszert, amely lehetővé teszi két szám GCD meghatározását (lásd alább).
Másrészt az a és b bármely lineáris kombinációja (vagyis az au + bv alak száma , ahol u és v egész szám) nem feltétlenül egyenlő a GCD-vel ( a , b ), hanem többszörös . És fordítva, egy c egész számot csak akkor írhatunk au + bv ( u és v relatív egész számok ) formába, ha c a GCD többszöröse ( a , b ).
Az egész számokat akkor mondják elsődlegesnek, ha az oszthatóság szempontjából "nincs semmi közös", más szóval, GCD-jük egyenlő 1-vel.
Ha két a és b egész számnak van d száma a GCD esetében , akkor az egész számoknál néld és bd elsődlegesek egymás között.
Klasszikus hiba azt hinni, hogy ha egy c egész szám osztja az ab egész szám szorzatát , akkor elosztja a vagy b értéket . Ez nem így van, amint azt a 6 példája mutatja, amely osztja a 9 × 8 = 72 értéket, de nem osztja sem a 9, sem a 8. De ez igaz lesz, ha hozzáadjuk azt a hipotézist, miszerint c prím a két szám egyikével a vagy b . Ez az eredmény Gaussian Lemma néven ismert, és a következőképpen nyilatkozik:
Gauss-féle lemma - Legyen a , b és c három egész szám, úgy, hogy c elválassza ab-t, és c prím legyen a-val . Ezután c osztja b-t .
Bármely 2-nél nagyobb vagy egyenlő n egész számot egyedileg írunk fel a tényezők sorrendjéig és a jelig a prímszámok véges szorzataként. A hányszor, hogy az elsődleges egész p fordul elő ez az írás az úgynevezett p -adic értékelési az N , jelöljük v p ( n ). A nulla nem egész m egész szám akkor osztja el n és csak akkor, ha az összes p esetén v p ( m ) ≤ v p ( n ).
Valójában egy család ( a i ) gcd-jét adja meg:
ahol a szorzat a prímszámok halmazához kapcsolódik (a véges mennyiség kivételével a termék szinte minden tényezője megegyezik 1-vel).
A nem nulla egész számú családok bármelyikének osztója megosztja a gcd-jüket. Ez a megfigyelés azonnal a fenti írásból adódik, mint prímszámok szorzata, de Euklidesz algoritmusából vagy variánsaiból is levezethető :
Bizonyítás egymást követő kivonássalElég megmutatni, hogy a két nem nulla természetes ≤ b ≤ a természetes egész számra vonatkozó osztó elosztja GCD-jüket. Legyen c ≥ 1; feltételezve, hogy a tulajdonság igaz az összes párra ( a , b ) úgy, hogy a + b < c , még mindig igaz azokra, amelyekre a + b = c : " triviális ", ha b = 0, és ez következik az indukciós hipotézist, ha b > 0, mert az a-ra és b-re (amelyek közül a legnagyobbak) osztók megegyeznek az a - b és b osztókkal .
Bármilyen Lucas szekvenciát x n = U n ( P , Q ) társított paraméterek P , Q , amely a relatív prím erős oszthatóság , azaz : Ez a helyzet például:
A redukálhatatlan tört olyan frakció , amelyben a számláló és a nevező a lehető legközelebb áll az 1. értékhez. Ez azt jelenti, hogy azt mondjuk, hogy a számláló és a nevező elsődleges közöttük. A redukálhatatlan frakció egyenlő egy törttelnál nélb az adat az, amelynek számlálója nál néld és a nevező bdahol d = GCD ( a , b ) .
Példa:Azzal, hogy tudjuk, hogy a GCD (30, 18) = 6, akkor ezt megjegyezve és arra következtetünk, hogy ez az utolsó frakció nem olvasható.
Bizonyos Diophantine-egyenleteket (vagyis olyan egyenleteket, amelyek paraméterei és a keresett megoldások egész számok) megoldjuk egy GCD-vel történő osztással annak érdekében, hogy ekvivalens egyenletre redukálódjunk közöttük prímszámokkal.
Így az x és y ismeretlenek ax + by = c diofantin-egyenlete akkor és csak akkor engedi meg a végtelenséget, ha c az a és b GCD többszöröse . Ha c nem többszöröse a és b GCD-jének , akkor nem fogad el egész számú megoldást. Ezek az eredmények a Bachet-Bézout tétel következményei . A klasszikus módszer ennek a problémának a egy egyenlet áll, elosztjuk az egyenlet a legnagyobb közös osztója a és b , majd alapuló Gauss-tétel , megoldása az új kapott egyenlet, az űrlap a'x + b „y = c” , ahol egy ' és b' koprim.
Egy másik klasszikus Diophantine-egyenlet a Pitagorasz-hármasok keresése . A Pitagorai hármas három x , y és z egész szám adata , amelyek igazolják a Pitagorasz-kapcsolatot : x 2 + y 2 = z 2 . Ez azt jelenti, hogy megtaláljuk az összes derékszögű háromszöget, amelynek oldalhossza egész szám. Ennek az egyenletnek a vizsgálata az x , y és z prímszámok egymással való keresése következik : ha x , y és z az egyenlet megoldása, és hogy d az GCD-jük, akkor x / d , y / d és z A / d az egyenlet megoldása is.
Ez nem lehet meghatározni a priori száma osztója minden számot. Az RSA kódolási rendszer azon a nagy nehézségen alapul, hogy nagyon nagy számítógép esetén is megtalálható bizonyos számok osztói .
A GCD kiszámítása triviális (nyilvánvaló), ha az egyik szám elsőszámú (a GCD 1), vagy ha az egyik szám többszöröse a másiknak (a GCD a kettő közül a kisebb).
Ez a módszer különösen alkalmas kis számok vagy olyan számok esetében, amelyek sok kicsi osztóval rendelkeznek (például 2, 3, 5, 11). Az egész számok sorrendbe vételével mindegyikre teszteljük, hogy közös-e a és b osztó . Ez azt jelenti, hogy találunk egy k számot , amely a = ka ′ és b = kb ′ , akkor elegendő kiszámítani a ′ és b ′ GCD-jét, mert megvan:
Példa: pgcd (60,84). Látjuk, hogy 60 és 84 4-nek többszöröse
.
Aztán, mivel a 15 és 21 a 3 többszöröse, van
.
Na, szóval .
Két a és b szám GCD-je egyben az a és b - a értéke is . Ez indokolja az egymást követő kivonások módszerét.
Ez a módszer különösen nagyszámú, de viszonylag közeli. Tegyük fel, hogy a nagyobb, mint b , van:
.Valójában a b bármely d osztójára :
Határozzuk meg a 675 és a 660 GCD-jét. Ugyanígy a 660 és a 675 - 660 = 15 értékét is. Most, hogy 3- mal és 5- tel oszthatósági kritériumokat alkalmazunk , azt látjuk, hogy 15 osztja 660-at. Tehát a GCD (15, 660 ) = GCD (675, 660) = 15.
Az euklideszi algoritmus az euklideszi felosztást használja . Mivel két egész számot egy és b a b > 0, akkor az euklideszi részlege egy a b a keresést a két szám q és r oly módon, hogy:
Az r számot ennek a felosztásnak a maradékának nevezzük .
Az Euclid algoritmusa a GCD két tulajdonságán is alapul:
Ahhoz, hogy meghatározzuk a legnagyobb közös osztója a két szám a és b , az algoritmus elvégzi a euklideszi részlege egy a b (mi majd talál egy maradék R 1 ), majd, ha R 1 ≠ 0, a euklideszi részlege b által R 1 (mi jelöljük R 2 a fennmaradó talált), akkor, ha R 2 ≠ 0, hogy a r 1 által r 2 , és így tovább. Az euklideszi felosztás definíciójának 2. része biztosítja, hogy az r 1 , r 2 ,… szekvencia szigorúan csökkenjen, ezért nulla maradékkal végződik. Az a és b GCD az előző maradék.
A bináris GCD algoritmus az Euclid algoritmusának olyan változata, amely a számok bináris ábrázolását manipulálja.
Bármely 2-nél nagyobb vagy egyenlő egész számot egyedileg írunk prímszámok szorzataként . És megvan a kapcsolat bármely p prímszámhoz ,
,hol van a p-adikus értékelés .
Az első lépés ebben az eljárásban az elbontása egy és b termékekké prímszámok. Ekkor nagyon könnyű megtalálni a GCD-t.
Ha és hol minden kitevő ellenőriz , majd
Példa:
360 = 2 × 2 × 2 × 3 × 3 × 5, ami 360 = 2 3 × 3 2 × 5.
Ismerve az elsődleges tényező decompositions két egész szám egy és b , a prímfaktorizáció azok GCD áll ugyanazon tényezők, mint az a és b, figyelembe minden tényezőt a legkisebb kitevő megjelenő mind a és b : a legkisebb kitevő közös , hogy a és b .
Példa:Prímtényező bomlásokkal
360 = 2 3 × 3 2 × 5és
48 = 2 4 × 3Ne feledje, hogy a közös prímtényezők 2 és 3. A 2-es szám a 3-as és 4-es kitevővel jelenik meg, így a legkisebb közös kitevője 3, 3 esetében a legkisebb közös kitevő 1 (mivel 3 = 3 1 ). A 360 és 48 GCD értéke tehát 2 3 × 3 = 24.