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