1.3 Eukleideen algoritmi ja kokonaislukuyhtälöt

172

$0{,}2x+1{,}5y=5$
$2x+15y=50$
$syt\left(2{,}15\right)$
$15=7\cdot2+1$
$syt\left(2{,}1\right)$
$2=2\cdot1$
$syt\left(15{,}2\right)=1$

koska 50 on jaollinen luvulla 1, yhtälöllä on kokonaislukuratkaisuja

ratkaistaan ensin yhtälön $2x+15y=1$
$1=15-7\cdot2$

joten yhtälön yksi kokonaislukuratkaisu on

$x=-7$
$y=1$

$x=-350+15n$
$y=50-2n$

$x\ge0$
$y\ge0$
$-350+15n\ge0$
$15n\ge350\ \parallel:15$
$n\ge23.33...$
$-2n\ge-50$
$n\le25$
$23.3...\le n\le25$
$n=24\ tai\ 25$
$kun\ n=24$
$x=-350+15\cdot24=10$
$y=50-48=2$
$kun\ n=25$
$x=25$
$y=0$

v:vähimmillään tarvitaan 12 astiallista

155

a)
$syt\left(15{,}6\right)$
$15=2\cdot6+3$
$syt\left(6{,}3\right)$
$6=2\cdot3$

$syt\left(15{,}6\right)=syt\left(6{,}3\right)=3$

$21:3=7+0$

jako menee tasan, Diofantoksen yhtälöllä on ratkaisuja
b)
$syt\left(6{,}\ 9\right)$
$9=1\cdot6+3$
$syt\left(6{,}3\right)$
$6=2\cdot3$
$syt\left(6{,}9\right)=syt\left(6{,}3\right)=3$

$11=3\cdot3+2$

jako ei mene tasan, Diofantoksen yhtälöllä ei ole ratkaisuja

166

Etsitään Diofantoksen yhtälön $6x+7y=50$ positiiviset kokonaislukuratkaisut

Määritetään ensin $syt\left(6{,}7\right)$

$7=6\cdot1+1$
$syt\left(6{,}1\right)$
$6=1\cdot6$
$syt\left(6{,}7\right)=syt\left(6{,}1\right)=1$

Ratkaistaan jakojäännös:

$1=7-1\cdot6$

Joten yhtälön $6x+7y=1$ eräs kokonaislukuratkaisu on

$x=-1$
$y=1$

jolloin $6x+7y=50$ eräs kokonaislukuratkaisu on

$x=-50$
$y=50$

tarkistus:

$-50\cdot6+50\cdot7=50$

$x=-50+\frac{7n}{1}=-50+7n$
$y=50-\frac{6n}{1}=50-6n$

haetaan sopiva kokonaisluku n, kun $x\ge0{,}\ y\ge0$

$-50+7n\ge0$
$7n\ge50\ \parallel:7$
$n\ge7{,}142...$
$50-6n\ge0$
$-6n\ge-50\ \parallel:\left(-6\right)$
$n\le8{,}333...$
$7{,}14...\le n\le8{,}3...$
$n=8$
$x=-50+7\cdot8=6$
$y=50-6\cdot8=2$