1.3 Eukleideen algoritmi ja kokonaislukuyhtälöt
Malliratkaisuja
159 (kaavamainen ratkaisutapa)
Eukleideen algoritmi
|| * 86
<----
<---
(kirjoita geogebraan (a - b*3)*1-(b-(a-b*3)*31)*1)
161
Eukleideen algoritmi
Etsitään yksittäisratkaisu:
|| * 86
Yksi ratkaisu, jossa x ja y ovat positiivisia, on x = 27 ja y = 1, (kun n = -29)
V: 27 kolmen desin rasiaa ja 1 viiden desin rasia.
Nopea ratkaisu:
Huomataan, että 86 = 81+5 = 3*27+5*1, joten
V: 27 kolmen desin rasiaa ja 1 viiden desin rasia.
x = 6 puruluun pakkaus
y = 10 puruluun pakkaus
a)
b)
(päätellään, että y = 5 ja x = 1 (56 = viisi kymppiä ja yksi kutonen))
Tai kaavamaisesti:
syt:
<----
Koska 56 / 2 = 28 on kokonaisluku, yksittäisratkaisu on olemassa. Selvitetään se:
|| * 28 (jotta saadaan 56)
Kun n = -10, saadaan
x = 56 + 5*(-10) = 6 ja
y = -28 - 3*(-10) = 2
Kun n = -11, saadaan
x = 56 + 5*(-11) = 1 ja
y = -28 - 3*(-11) = 5
V: 6 kuuden puruluun pakkausta ja 2 kymmenen.
V: 1 kuuden puruluun pakkausta ja 5 kymmenen.
163
<---
=>
38 / 38 = 1 on kokonaisluku, joten etsitään yksittäisratkaisu
(kirjoita geogebraan (a - b*3)*1-(b-(a-b*3)*31)*1)
161
Saadaan syt=3. 800 / 3 ei ole kokonaisluku, joten ei ratkaisua.
Eukleideen algoritmi
Jakoyhtälössä a = nq + r
Tämä on nimeltään Eukleideen algoritmi.
<-- viimeinen nollasta eroava jakojäännös on syt
ESIM 1. Mikä on lukujen 343 ja 63 suurin yhteinen tekijä?
Pyj saadaan kaavasta eli
.
ESIM 2. Mikä on lukujen 14 ja 6 pienin yhteinen monikerta?
***
Tehtäviä
149, 150, 151, 156, 152, 155, 165a
- syt(a, n) = syt(n, r)
Tämä on nimeltään Eukleideen algoritmi.
ESIM. Selvitä lukujen 433 ja 38 suurin yhteinen tekijä jakoyhtälön avulla.
joten jakoyhtälö on:
<-- viimeinen nollasta eroava jakojäännös on syt
joten syt( 433, 38 ) = 1
ESIM 1. Mikä on lukujen 343 ja 63 suurin yhteinen tekijä?
Siis syt(343, 63) = 7.
Pyj saadaan kaavasta eli
.
ESIM 2. Mikä on lukujen 14 ja 6 pienin yhteinen monikerta?
***
Tehtäviä
149, 150, 151, 156, 152, 155, 165a
Diofantoksen yhtälö
Diofantoksen yhtälö on yleisnimitys yhtälöille, joiden kertoimet ovat kokonaislukuja ja joille etsitään kokonaislukuratkaisuja.
1. asteen Diofantoksen yhtälö: ax + by = c kun a, b, c ∈ ℤ
- Diofantoksen yhtälöllä ax + by = c on jokin ratkaisu (x0, y0)
jos ja vain jos
c on jaollinen syt(a, b):lla eli c on syt(a, b):n monikerta. - Tätä ratkaisua (x0, y0) kutsutaan yksittäisratkaisuksi ja se saadaan Eukleideen algoritmin avulla käyttämällä yhtälöä
- Diofantoksen yhtälön yleinen ratkaisu on kaikkien yksittäisratkaisujen joukko ja se saadaan kaavalla
missä (x0, y0) on jokin yksittäisratkaisu ja n ∈ ℤ.
ESIM 3. Ratkaise Diofantoksen yhtälöt
a) 128x + 56y = 8
(a=128, b=56, c=8)
Eukleideen algoritmilla syt
=> yhtälöllä on yksittäisratkaisu.
Eukleideen algoritmilla syt
Siis syt(128, 56) = 8.
.=> yhtälöllä on yksittäisratkaisu.
,
joten yksittäisratkaisu on
b) 128x + 56y = 40
***
c) 128x + 56y = 4
***
ESIM 4. Ratkaise Diofantoksen yhtälö 4x – 15y = 3.
***
ESIM 5. Isä osti kaupasta kahvia 40 eurolla. Toinen kahvilajike oli maksanut 2,30 e paketilta ja toinen 1,60 e paketilta. Isä osti vain näitä kahta kahvilajiketta. Kuinka monta pakkausta isä oli ostanut kumpaakin lajiketta?
***
Tehtäviä
154, 157, 158, 159, 163, 164, 165b, 168, ...