Lukuteoriasta viestin salaamiseen 3

Diofantoksen yhtälöistä

Olkoot a, b ja c kokonaislukuja. Kun yhtälölle

ax + by = c

pyritään löytämään kokonaislukuratkaisut x ja y, puhutaan (ensimmäisen kertaluvun) Diofantoksen yhtälöstä. Ratkaisun olemasssaolo riippuu vakioista a, b ja c siten, että yhtälöllä on ratkaisu jos luku c on jaollinen luvulla syt(a,b). Ratkaisun etsiminen perustuu edellisen kirjoituksen (01.09.2008) Eukleideen algoritmiin. Ratkaistaan esimerkkinä yhtälö

95x + 51y = 1 (1)

Ratkaisun olemassaolo:

95 = 1*51 + 44
51 = 1*44 + 7
44 = 6*7 + 2
7 = 3*2 + 1
2 = 2*1 + 0

Siten syt(95,51) = 1 ja yhtälö (1) oikeapuoli 1 on jaollinen tällä suurimmalla yhteisellä tekijällä. Näin yhtälöllä (1) on ratkaisu. Itseasiassa aina kun Diofantoksen yhtälöllä on ratkaisu, niitä on samalla ääretön määrä.

Suurimman yhteisen tekijän etsimisen jakoyhtälöketjusta ratkaistaan seuraavaksi jokaiselta riviltä jakojäännös.

95 = 1*51 + 44 => 44 = 95 - 1*51
51 = 1*44 + 7 => 7 = 51 - 1*44
44 = 6*7 + 2 => 2 = 44 - 6*7
7 = 3*2 + 1 => 1 = 7 - 3*2
2 = 2*1 + 0.

Tämän jälkeen lähdetään liikkeelle pienimmästä nollasta poikkeavasta jakojäännöksestä 1 = 7 - 3*2 ja sijoitetaan tämän lopussa esiintyvän luvun 2 paikalle edelliseltä riviltä ratkaistu jakojäännös ja näin saatuun lausekkeeseen taas edelliseltä rivilt jakojännös j.n.e aina ketjun ylimmälle riville asti.

Siis
1 = 7 - 3*2
= 7 - 3*(44 - 6*7) = 7 - 3*44 + 18*7 = -3*44 + 19*7
= -3*44 + 19*(51 - 1*44) = -3*44 + 19*51 - 19*44 = 19*51 - 22*44
= 19*51 - 22*(95 - 1*51) = 19*51 - 22*95 + 22*51 = -22*95 + 41*51.

Näin yhtälöketjun ensimmäisen ja viimeisen lausekkeen avulla saamme

-22*95 + 41*51 = 1 (2)

Kun vertaamme tätä yhtälöön (1), voimme todeta, että yhtälön yhtenä ratkaisuna on x = -22 ja y = 41.

Jos meillä olisi ollut yhtälössä (1) oikealla puolella vakion 1 tilalla luku 3, siis

95x + 51y = 3 , (3)

olisi toimittu yllä olevan mukaisesti ja lopussa saatu yhtälö (2) olisi vielä kerrottu puolittain kolmella, jolloin olisimme saaneet

-66*95 + 123*51 = 3 (4)

ja nyt yhtälöitä (3) ja (4) vertaamalla olisimme saaneet ratkaisuksi x = -66 ja y = 123.