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. 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
formula_1 ja
formula_2,
jossa formula_3 on "i":s alkuluku, ja jos formula_3 ei ole luvun tekijä, sitä vastaava eksponentti formula_5 tai formula_6 on nolla, saadaan suurin yhteinen tekijä kaavasta
formula_7
Suurin yhteinen tekijä voidaan löytää myös esimerkiksi Eukleideen algoritmin avulla.
Algebrallinen määritelmä.
Algebrallisessa mielessä kokonaislukujen formula_8 suurimmalla yhteisellä tekijällä tarkoitetaan näiden lukujen virittämän kokonaislukujen renkaan ideaalin virittäjää.
Jos luvut formula_8 ovat kaikki nollia, niiden virittämä ideaali koostuu pelkästään luvusta formula_10.
Kokonaislukujen rengas formula_11 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 formula_11 äärellisesti viritetty ideaali on yhden alkion virittämä, voidaan todistaa seuraavasti:
Olkoon formula_13 kaikilla formula_14 kokonaislukujen
formula_8 virittämä renkaan formula_11 ideaali. Olkoon formula_17 tämän ideaalin pienin positiivinen alkio ja formula_18.
Helposti todetaan, että jokainen formula_17:n monikerta sisältyy ideaaliin formula_20.
Olkoon toisaalta formula_21 ideaalin 
formula_20 mielivaltainen alkio ja formula_23, jossa 
formula_24.
Tällöin formula_25.
Siis formula_26 kuuluu ideaaliin formula_20.
Jos formula_26 on suurempi kuin nolla, saadaan ristiriita luvun formula_17 valinnan kanssa. Siis välttämättä jokainen ideaalin formula_20 alkio on luvun formula_17 monikerta.
Toisin sanoen lukujen formula_32 virittämä ideaali on sama, kuin ko. ideaalin pienimmän positiivisen alkion formula_17 virittämä ideaali. Tätä lukua formula_17 kutsutaan lukujen formula_8 suurimmaksi yhteiseksi tekijäksi.
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.
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))