Lukuteoriasta viestin salaamiseen 2

Suurin yhteinen tekijä

Jos a on positiivinen kokonaisluku, niin jokaista positiivista kokonaislukua, jolla luku a on jaollinen, sanotaan luvun a tekijäksi.

Kun luvut a ja b ovat positiivisia kokonaislukuja, niin lukujen a ja b yhteisistä tekijöistä suurin on lukujen a ja b suurin yhteinen tekijä, merkitään syt(a,b) (engl. gcd(a,b)).

Jos positiivinen luku a on jaollinen kokonaisluvulla b, on syt(a,b)= b.

Jos positiivinen luku a ei ole jaollinen kokonaisluvulla b, voidaan edellisen kirjoituksen (Lukuteoriasta viestin salaamiseen 1) mukaisesti kirjoittaa jakoyhtälö

a = qb + c .

Nyt voitaisiin kohtuullisen helposti todistaa, että jos luku k on lukujen a ja b yhteinen tekijä, se on myös lukujen b ja c yhteinen tekijä. Ja myös vastakkaiseen suuntaan: jos luku k on lukujen b ja c yhteinen tekijä, se on välttämmättä myös lukujen a ja b yhteinen tekijä.

Näin lukujen a ja b suurimman yhteisen tekijän etsiminen voidaan muuttaa pienempien lukujen b ja c suurimman yhteisen tekijän etsimiseen, joka taas voidaan edelleen muuttaa jakoyhtälön avulla yhä pienempien lukujen käsittelyyn, kunnes lopulta päädytään tilanteeseen, jossa löytyy keskenään jaolliset luvut. Jakoyhtälöiden ketjussa viimeinen nollasta poikkeava jakojäännös on alkuperäisten lukujen aja b suurin yhteinen tekijä. Tätä menetelmää sanotaan Eukleideen algoritmiksi.

Esimerkki Määritä lukujen 2064 ja 1572 suurin yhteinen tekijä.

Kirjoitetaan jakoyhtälöt

2064 = 1 * 1572 + 492
1572 = 3 * 492 + 96
492 = 5 * 96 + 12
96 = 8 * 12 + 0

Siten syt(2064,492) = 12.