Elikkäs sellainen kysmys olisi, että ovatko kokonaisluvut u ja v yksikäsitteiset, kun au bv = syt.(a,b), missä a ja b tietysti kokonaislukuja?
Tämä on siis suora seuraus Eukleideen algoritmista ja näin ollen ylläoleva yhtälö on varmasti ratkeava, mutta onko ratkaisuja useita?
Tämä on siis suora seuraus Eukleideen algoritmista ja näin ollen ylläoleva yhtälö on varmasti ratkeava, mutta onko ratkaisuja useita?
Vastaukset 4
Vanhimmat
Valitaan a=b=1. Nyt yhtälö sievenee muotoon u v=1, jolla on äärettömän monta ratkaisua.
No tottahan toki a ja b nyt ovat sentään ERI lukuja. Eihän tässä muuten mitään tolkkua olisi koko hommassa. En sitä tuossa nyt muistanut mainita, mutta kyllähän nyt pyllysilmälläkin näkee, että jos a=b, niin ratkaisuja on ääretön määrä.
Lisäksi oletetaan, että a ja b eivät molemmat ole yhtä kuin 0.
Oletetaan yleinen kahden tuntemattoman muuttujan x,y lineaarinen Diofantoksen yhtälö ax by=c. Tällä on kokonaislukuratkaisu x=x_0, y=y_0 jos ja vain jos syt(a,b) jakaa c:n. Tämä ratkaisu saadaan Eukleideen algoritmilla. Nyt kyseisen Diofantoksen yhtälön kaikki ratkaisut ovat muotoa
x=x_0 b*t/syt(a,b)
y=y_0-a*t/syt(a,b)
Siis jos ratkaisuja on ainakin yksi kappale, niitä on äärettömän monta.
Kyllä niitä löytyy aina ääretön määrä. Otetaan ensin esimerkki, niin tilanne hahmottuu.
Olkoon a=5 ja b=3. Selvästi näiden syt on 1.
Pitäisi siis ratkaista 5u 3v = 1. Tämä on aika helppo kokeilemalla, vaikka Eukleideen algoritmihan tietenkin auttaa vaikeammissa tapauksissa.
5-6=-1, joten merkkiä vaihtamalla saadaan -5 6 = 1, ja siis:
5*(-1) 2*3=1
Nyt meillä on yhtälö voimassa. Entäpä jos sen molemmille puolille lisätään nolla? Yhtälö säilyy voimissaan. Lisättävässä voisi kummitella luku 15, koska se on hauska.
15-15=3*5-5*3=0
Lisätään tämä:
5*(-1) 3*5 2*3-5*3 = 1
joka sievenee näin
2*5 - 3*3 = 1 (10-9=1).
Miksipä lisättiin juuri 15? Sehän on 3:n ja 5:n pyj. Voisi heti arvella, että kaikki pyj:n monikerrat samalla tavalla lisättynä & vähennettynä antavat samanlaisen tuloksen - yhtälö sievenee alkuperäiseen muotoon eri kertoimilla.
Jos taas lisätään-vähennetään (heh, uudissana, anteeksi) jokin luku, joka ei ole jaollinen pyj:llä, varmaankin käy niin, että se ei jakaannu samalla tavalla tekijöiksi tuohon yhtälöön.
Tässä on siis todistuksen alku sille, mitä muotoa yleinen ratkaisu on. Tarkka todistus on vähän pidempi, joten pahoittelen, etten jaksa sitä kirjoitella. Idea varmasti on selvä.
Taulukoidaan lopuksi 3:n ja 5:n ratkaisuja:
viiden kerroin / kolmen kerroin
-1 / 2
2 / -3
5 / -8 (25-24=1)
8 / -13 (40-39=1)
jne.
Huomaamme, että viiden kerroin kasvaa kolmella kun taas kolmen kerroin pienenee viidellä. Toiseenkin suuntaan voisi mennä. Tämä tietenkin liittyy siihen pyj:hin siellä, joka lisättiin & vähennettiin :-)
Kokeilemallakin voi asian tajuta, vaikka tietenkin todistus vasta on *varma* asia.