Suurin yhteinen tekijä

Kahdella kokonaisluvulla a ja b on aina vähintään yksi yhteinen positiivinen tekijä, nimittäin 1.

Määritelmä. Olkoot a ja b kokonaislukuja, joista ainakin toinen on nollasta eroava. Lukujen a ja b suurin yhteinen tekijä, syt(a,b), on luku d, joka määritellään seuraavasti:

     (a)   d > 0,
     (b)   d | a ja d | b,
     (c)   jos c | a ja c | b, niin c | d.

Luku syt(a,b) on siis lukujen a ja b yhteisistä tekijöistä suurin.

Jos lukujen a ja b suurin yhteinen tekijä on 1 sanotaan, että luvut a ja b ovat suhteellisia alkulukuja.

Lause. Jos a ja b eivät molemmat ole nollia, niin syt(a,b) on olemassa ja se on yksikäsitteinen. Lisäksi on olemassa sellaiset kokonaisluvut u ja v, että

Todistus. Todistetaan, että syt(a,b) on joukon A = {xa + yb | x,y } pienin positiivinen luku, tämä todistaa lauseen väitteet.

Koska luvut a ja b eivät ole molemmat nollia, on joukossa A selvästi nollasta eroavia alkioita. Todetaan lisäksi, että joukossa A on positiivisia alkioita. Jos x A ja x < 0, niin x = x₀a + y₀b joillekin luvuille x₀ ja y₀. Silloin -x = (-x₀)a + (-y₀)b on joukon A positiivinen luku.

Oletetaan, että joukon A pienin positiivinen luku on d = ua + vb. Näytetään ensin, että d | a. Jakoalgoritmia käyttäen saadaan

Tästä saadaan

Näin ollen r kuuluu joukkoon A. Luvun d minimaalisuudesta johtuen on r = 0, siis d | a.

Samoin nähdään, että d|b; siis d on lukujen a ja b yhteinen tekijä. Jos myös c on näiden yhteinen tekijä, niin c | (ua + vb) eli c jakaa luvun d. Koska d > 0, niin c < d, ja siis d = syt (a, b).

Huomaa, että edellisen lauseen luvut u ja v eivät ole yksikäsitteisiä. Esimerkiksi syt(4, 6) = 2 = 2 ^. 4 - 1 ^. 6 = (-1) ^. 4 + 1 ^. 6.

Linkit:
Jaollisuus ja alkuluvut
Jakoalgoritmi
Eukleideen algoritmi