1.3 Eukleideen algoritmi ja kokonaislukuyhtälöt

Malliratkaisuja

159 (kaavamainen ratkaisutapa)

$x=3\ \text{desin}\text{ rasiat}{,}\ y\ =5\ \text{desin}$

$8{,}6=0{,}3x+0{,}5y$
$86=3x+5y$
$\text{syt}\left(3{,}5\right)=1$
$\frac{86}{1}=86\ \text{on kokonaisluku, joten on olemassa yksittäisratkaisu}$
Eukleideen algoritmi

$5=1\cdot3+2$
$3=1\cdot2+1$
$2=2\cdot1$

Etsitään yksittäisratkaisu:

$1=3-1\cdot2$

$1=3-1\cdot\left(5-1\cdot3\right)$
$1=3-1\cdot5+1\cdot3$
$1=2\cdot3-1\cdot5$ || * 86

$86=172\cdot3-86\cdot5$

$\begin{cases} x=172+n\cdot\frac{5}{1}=5n+172&\\ y=-86-n\cdot\frac{3}{1}=-3n-86& \end{cases}$

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

$x\cdot6+y\cdot10$

$x\cdot6+y\cdot10=56$

(päätellään, että y = 5 ja x = 1 (56 = viisi kymppiä ja yksi kutonen))

Tai kaavamaisesti:

syt:

$10=6\cdot1+4$
$6=4\cdot1+2$ <----
$4=2\cdot2$
$\text{syt}\left(10{,}6\right)=2$

Koska 56 / 2 = 28 on kokonaisluku, yksittäisratkaisu on olemassa. Selvitetään se:

$2=6\cdot1-4\cdot1$

$2=6\cdot1-\left(10-6\cdot1\right)\cdot1$
$2=6\cdot1-10\cdot1+6\cdot1$
$2=6\cdot2-10\cdot1$ || * 28 (jotta saadaan 56)

$56=56\cdot6-28\cdot10$

$\begin{cases} x=56+n\cdot\frac{10}{2}=56+5n&\\ y=-28-n\cdot\frac{6}{2}=-28-3n& \end{cases}$

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

$34086=14630\cdot2+4826$

$14630=4826\cdot3+152$
$4826=152\cdot31+114$
$152=114\cdot1+38$ <---
$114=38\cdot3$

$\text{syt}\left(34086{,}14630\right)=38$

$38=34086a+14630b$

38 / 38 = 1 on kokonaisluku, joten etsitään yksittäisratkaisu

$38=\left(14630-4826\cdot3\right)\cdot1-\left(4826-\left(14630-4826\cdot3\right)\cdot31\right)\cdot1$
(kirjoita geogebraan (a - b*3)*1-(b-(a-b*3)*31)*1)

$38=32\cdot14630-97\cdot4826$

161

Saadaan syt=3. 800 / 3 ei ole kokonaisluku, joten ei ratkaisua.

Eukleideen algoritmi

Jakoyhtälössä a = nq + r

syt(a, n) = syt(n, r)

joten lukujen a ja n syt saadaan, kun toistetaan jakoyhtälöä, kunnes jakojäännös on 0. Syt on viimeinen nollasta eroava jakojäännös.
Tämä on nimeltään Eukleideen algoritmi.

ESIM. Selvitä lukujen 433 ja 38 suurin yhteinen tekijä jakoyhtälön avulla.

$433:38=11{,}39...$

$433-11\cdot38=15$

joten jakoyhtälö on:

$433=11\cdot38+15$

$38=2\cdot15+8$
$15=1\cdot8+7$
$8=1\cdot7+1$ <-- viimeinen nollasta eroava jakojäännös on syt
$7=7\cdot1+0$

joten syt( 433, 38 ) = 1

ESIM 1. Mikä on lukujen 343 ja 63 suurin yhteinen tekijä?

$343=5\cdot63+28$

$63=2\cdot28+7$
$28=4\cdot7+0$

Siis syt(343, 63) = 7.

Pyj saadaan kaavasta $a\cdot b=\text{syt}\left(a{,}b\right)\cdot\text{pyj}\left(a{,}b\right)$ eli
$\text{pyj}\left(a{,}b\right)=\frac{a\cdot b}{\text{syt}\left(a{,}b\right)}$ .

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 (x₀, y₀)
jos ja vain jos
c on jaollinen syt(a, b):lla eli c on syt(a, b):n monikerta.
Tätä ratkaisua (x₀, y₀) kutsutaan yksittäisratkaisuksi ja se saadaan Eukleideen algoritmin avulla käyttämällä yhtälöä
$ax+by=\text{syt}\left(a{,}b\right)$
Diofantoksen yhtälön yleinen ratkaisu on kaikkien yksittäisratkaisujen joukko ja se saadaan kaavalla
$\begin{cases} x=&x_0+n\cdot\frac{b}{\text{syt}\left(a{,}b\right)}\\ y=&y_0-n\cdot\frac{a}{\text{syt}\left(a{,}b\right)} \end{cases}$
missä (x₀, y₀) on jokin yksittäisratkaisu ja n ∈ ℤ.

Siis: 1) onko c jaollinen sytillä, 2) etsi yksittäisratkaisu (x₀, y₀), 3) jos tarpeen, esitä yleinen ratkaisu.

ESIM 3. Ratkaise Diofantoksen yhtälöt

a) 128x + 56y = 8

(a=128, b=56, c=8)

Eukleideen algoritmilla syt
$128=56\cdot2+16$
$56=16\cdot3+8$
$16=8\cdot2+0$

Siis syt(128, 56) = 8.

$\frac{c}{syt\left(128{,}56\right)}=\frac{8}{8}\in\mathbb{Z}$ .
=> yhtälöllä on yksittäisratkaisu.

$8=56-16\cdot3$
$8=56-\left(128-56\cdot2\right)\cdot3$
$8=56-3\cdot128+6\cdot56$
$8=1\cdot56-3\cdot\left(1\cdot128-2\cdot56\right)$
$8=1\cdot56-3\cdot128+6\cdot56$
$8=-3\cdot128+7\cdot56$ ,

joten yksittäisratkaisu on $x_0=-3{,}\ \ \ y_0=\ 7$

$\begin{cases} x=x_0+n\cdot\frac{b}{\text{syt}\left(a{,}b\right)}&\\ y=y_0-n\cdot\frac{a}{\text{syt}\left(a{,}b\right)}& \end{cases}$

$\begin{cases} x=-3+n\cdot\frac{56}{8}=-3+7n&&&\\ y=7-n\cdot\frac{128}{8}=7-16n&n\in&\mathbb{Z}& \end{cases}$

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, ...