Suurin yhteinen tekijä

Matematiikassa kahden kokonaisluvun a ja b suurin yhteinen tekijä, merkitään syt(a, b) tai pelkästään (a, b), tarkoittaa suurinta sellaista lukua, joka jakaa molemmat luvut a ja b niin, että lopputulos on kokonaisluku.Rosen, s. 53 Suurin yhteinen tekijä voidaan etsiä jakamalla tarkasteltavina olevat luvut alkutekijöihin. Tällöin lukujen suurin yhteinen tekijä saadaan ottamalla ne alkuluvut, jotka esiintyvät molempien lukujen alkutekijähajotelmassa korotettuna siihen potenssiin, joka on pienempi tämän kyseisen alkuluvun eksponentti lukujen alkutekijähajotelmissa. Suurin yhteinen tekijä on tällöin saatujen lukujen tulo.
Siis jos

 ja
,

jossa  on i:s alkuluku, ja jos  ei ole luvun tekijä, sitä vastaava eksponentti  tai  on nolla, saadaan suurin yhteinen tekijä kaavasta

Suurin yhteinen tekijä voidaan löytää myös esimerkiksi Eukleideen algoritmin avulla.

Algebrallinen määritelmä

Algebrallisessa mielessä kokonaislukujen  suurimmalla yhteisellä tekijällä tarkoitetaan näiden lukujen virittämän kokonaislukujen renkaan ideaalin virittäjää.

Jos luvut  ovat kaikki nollia, niiden virittämä ideaali koostuu pelkästään luvusta .

Kokonaislukujen rengas  on kommutatiivinen eli vaihdannainen rengas. Lisäksi se on kokonaisalue, toisin sanoen siinä ei ole nollasta eroavia nollanjakajia, ja edelleen niin sanottu pääideaalialue, toisin sanoen sen jokainen ideaali on yhden alkion virittämä.

Väite, että jokainen kokonaislukujen renkaan  äärellisesti viritetty ideaali on yhden alkion virittämä, voidaan todistaa seuraavasti:

Olkoon  kaikilla  kokonaislukujen
 virittämä renkaan  ideaali. Olkoon  tämän ideaalin pienin positiivinen alkio ja .

Helposti todetaan, että jokainen :n monikerta sisältyy ideaaliin .

Olkoon toisaalta  ideaalin 
 mielivaltainen alkio ja , jossa 
.

Tällöin .

Siis  kuuluu ideaaliin .
Jos  on suurempi kuin nolla, saadaan ristiriita luvun  valinnan kanssa. Siis välttämättä jokainen ideaalin  alkio on luvun  monikerta.

Toisin sanoen lukujen  virittämä ideaali on sama, kuin ko. ideaalin pienimmän positiivisen alkion  virittämä ideaali. Tätä lukua  kutsutaan lukujen  suurimmaksi yhteiseksi tekijäksi.

Esimerkkejä
 Lukujen 12 ja 15 suurin yhteinen tekijä on 3. Tämä nähdään jakamalla luvut tekijöihin: 12 = 22 · 3 ja 15 = 3 · 5.
 Lukujen 132 ja 222 suurin yhteinen tekijä syt(132,222) = 6, koska 132 = 22 · 3 · 11 ja 222 = 2 · 3 · 37.

Yksinkertainen käytännön esimerkki

Olkoon tehtävänä peittää suorakaiteen muotoisen huoneen, jonka leveys a ja pituus b ovat kokonaislukuja, lattia mahdollisimman suurilla keskenään samankokoisilla neliön muotoisilla laatoilla. Miten laatan sivun pituus c on valittava?

Ratkaisun antaa lukujen a ja b suurin yhteinen tekijä suoraan. Siis valitaan c=syt(a,b).

Ominaisuuksia
 Jos syt(a, b) = 1, a ja b ovat keskenään jaottomia.
 syt(a, b) = syt(b, a) = syt(|a|, |b|)Rosen, s. 54
 syt(a, a) = a
 syt(0, a) = a
 syt(m·a, m·b) = m·syt(a, b)
 syt(a, b) = syt(a - kb, b), jossa k on kokonaisluku
 Eukleideen algoritmi: syt(a, b) = syt(b, a modulo b)

Käytännössä nopein tapa määrittää kahden luvun suurin yhteinen tekijä on käyttää Josef Steinin vuonna 1961 julkaisemaa binääristä algoritmia, mikäli lukujen alkutekijähajotelmaa ei tunneta.

 Ohjelmallinen toteutus 
Suurin yhteinen tekijä kahdelle epänegatiiviselle kokonaisluvulle on laskettavissa Pythonilla rekursiolla seuraavalla funktiolla:

def syt(a, b):
  if b == 0:
    return a
  else:
    return syt(b, (a % b))

Katso myös
 Pienin yhteinen jaettava
 Aito jakaja
 Yhteinen tekijä

 Lähteet 


 Viitteet 

 Aiheesta muualla 

Luokka:Algebra
Luokka:Lukuteoria