2. Lukuteoriaa

Jaollisuus ja jakoyhtälö

Jaollisuus

Luku a on jaollinen luvulla b, jos löytyy sellainen luku c, että

$a=c\cdot b\ \ \left(\frac{a}{b}=c\right){,}\ tässä\ a{,}\ b\ ja\ c\ ovat\ kokonaislukuja\ \left(merkitään\ a{,}b{,}c\in\mathbb{Z}\right)$

Sanotaan myös, että b on a:n tekijä tai b jakaa a:n.

$esim\ \ \ 21=3\cdot7\ \ \left(\frac{21}{7}=3\right){,}\ mutta\$

21 ei ole jaollinen luvulla 5, sillä
$\frac{21}{5}=4+\frac{1}{5}\ \left(=4\frac{1}{5}\right)$

Lukuteoriassa tämä merkitään jakoyhtälön muotoon eli ylläoleva yhtälö kerrotaan luvulla 5

$21=4\cdot5+1$

Huom!

$Parillisia\ lukuja\ merkitään\ yleisesti\ 2n\ ja\ parittomia\ 2n+1\ \left(2n-1\right){,}\ n\in\mathbb{Z}$

Jakoyhtälö

Kun luku a jaetaan luvulla b (luvut ovat kokonaislukuja, jossa b on jakaja ja a jaettava), saadaan

$\frac{a}{b}=q+\frac{r}{b}{,}\ jossa\ myös\ q\ \ ja\ \ r\in\mathbb{Z}$

Kun tämä yhtälö kerrotaan b:llä saadaan jakoyhtälö

$a=q\cdot b+r{,}\ \ 0\le r\le b-1$ (r on jakojäännös)

Jos luku jaetaan luvulla 5 (=b) niin r voi saada arvot 0, 1, 2, 3 tai 4

Lukuteoriassa käytetään usein jakoyhtälöä tälläkin kurssilla.

$jos\ r=0\ niin\ a=q\cdot b\ \ eli\ a\ on\ jaollinen\ b:llä$

esimerkkejä

a) kun luku 37 jaetaan luvulla 5, saadaan jakoyhtälö

$37=7\cdot5+2$

b) kun luku 1828 jaetaan luvulla 6, saadaan jakoyhtälö

$1828=304\cdot6+4$

Kotitehtävät: 109, 204, 205 ja 206

Lukujärjestelmät

Kymmenlukujärjestelmän luku 3861 ajatellaan muodostuvan seuraavasti

$3861\ =\ 3\cdot10^3+8\cdot10^2+6\cdot10^1+1\cdot10^0$

Vastaavasti esim 7-järjestelmän luku ajatellaan muodostuvan seuraavasti, esim

$6532_7=6\cdot7^3+5\cdot7^2+3\cdot7^1+2\cdot7^0=2326_{10}$

Kymmenjärjestelmän luvun muuttaminen johonkin toiseen lukujärjestelmään onnistuu helposti jakoyhtälön avulla

esim. Muutetaan 10-järjestelmän luku 7943 6-järjestelmän luvuksi: Jaetaan 10 järjestelmän luku 6:lla, josta kirjoitetaan jakoyhtälö.

$7943=1323\cdot6+5{,}\ \ nyt\ edelleen\ 1323\ jaetaan\ 6:lla$

$1323=220\cdot6+3{,}\ \ nyt\ 220\ jaetaan\ 6:lla$
220 = 36 * 6 + 4
$36=6\cdot6+0$
$6=1\cdot6+0$
$1=0\cdot6+1$

Nyt 6-järjestelmän luku muodostuu jakojäännöksistä, kun ne luetaan lopusta alkuun päin eli

$7943_{10}=100435_6=1\cdot6^5+0\cdot6^4+0\cdot6^3+4\cdot6^2+3\cdot6+5\left(\cdot6^0\right)$

"Pienet 10-järjestelmän luvut" on suhteellisen helppo muuttaa binäärijärjestelmään (2-lukujärjestelmä) päättelemällä esim

$87_{10}=1\cdot2^{^6}+0\cdot2^5+1\cdot2^4+0\cdot2^3+1\cdot2^2+1\cdot2^1+1\cdot2^0=1010111_2$

16-lukujärjestelmän luvuissa voivat esiintyä jakojäännökset 10 - 15, joita merkitään aakkosten alkupään kirjaimilla eli

10 =A, 11 = B, 12 = C, 13 = D, 14 = E ja 15 = F

$16-järjestelmän\ luku\ voi\ olla\ esim\ ABBA$

$ABBA_{16}=10\cdot16^3+11\cdot16^2+11\cdot16+10\cdot16^0=43962_{10}$

Kotitehtävät: 215, 217 ja 222

Teoriaa lukujärjestelmistä

Kymmen- eli desimaalijärjestelmässä kaikki luvut esitetään numeroita 0, 1, 2, ... , 8, 9 käytäen. Numeron paikka
luvussa ilmaisee eri kantaluvun 10 potenssin kerrointa, joista viimeinen numero on 10^0 kerroin.

$Esimerkiksi\ luku\ 2508=2\cdot10^3+5\cdot10^2+0\cdot10^1+8\cdot10^0$

Lukuja voidaan esittää myös muissa lukujärjestelmässä esimerkiksi oktaali- eli 8-lukujärjestelmässä, jossa esiintyy
vain numeroita 0, 1, 2, 3, 4, 5, 6 tai 7.

$Esimerkiksi\ 8-järjestelmän\ luku\ 1234\ =1\cdot8^3+2\cdot8^2+3\cdot8^1+4\cdot8^0\$

eli se koostuu eri kantaluvun 8 potenssien kertoimista. Tämä 8-järjestelmän luku voidaan helposti laskimella
laskien muuttaa kymmenjärjestelmän luvuksi eli

$1234_8=1\cdot8^3+2\cdot8^2+3\cdot8^1+4\cdot8^0=668_{10}\ \left(alaindeksi\ kuvaa\ kantalukua\right)$

Tehtävä, jossa apuvälineenä on laskin

Muuta 6-järjestelmän luku 12433 kymmenjärjestelmän luvuksi.
Tämä luku on lukon koodi, jolla pääsette luokasta pois.

Alkuluvut ja Eukleideen algoritmi

Alkuluvut

Alkuluvut ovat lukuja, jotka ovat jaollisia luvulla itsellään ja luvulla 1. Eli alkuluvun tekijät ovat 1 ja luku itse.

$Alkulukujen\ joukko\ P\ =\ \left\{2{,}\ 3{,}\ 5{,}\ 7{,}\ 11{,}\ 13{,}\ 17{,}\ 19{,}\ 23{,}\ ...\right\}$

Alkulukuja kutsutaan myös jaottomiksi luvuiksi.

Yhdistettyjä lukuja ovat kaikki ne luvut, jotka eivät ole alkulukuja.

Yhdistetty luku voidaan esittää alkulukujen tulona eli hajoittaa alkutekijöihin vain yhdellä tavalla.

$Esim.\ 680=2\cdot34\cdot10=2\cdot2\cdot17\cdot2\cdot5=2^3\cdot5\cdot17$

Yksinkertainen alkulukutesti:

Selvitetään onko annettu luku n jaollinen niillä alkuluvuilla, jotka ovat pienempiä kuin luvun n neliöjuuri.

esim. Onko luku a) 163, b) 781 alkuluku

$\sqrt{163}\approx12{,}8$

Tutkitaan, onko luku 163 jaollinen luvuilla 11, 7, 5, 3 tai 2? Huomataan, ettei se ole jaollinen yhdelläkään näistä, joten 163 on alkuluku.

$\sqrt{781}\approx27{,}9$

Onko 781 jaollinen alkuluvuilla 2, 3, 5, 7, 11, 13, 17, 19, 23? Huomataan, että 781 = 11*71 eli 781 ei ole alkuluku.

Muuta 10-järjestelmän luku 4589 oktaali eli 8-järjestelmän luvuksi.

$\left(4589_{10}=?_8\right)$

Käytetään jakoyhtälöä apuna eli lähdetään 4589 jakamaan luvulla 8. Edelleen jakoyhtälön 8:n monikerta jaetaan luvulla 8

$4589=573\cdot8+5$
$573=71\cdot8+5$
$71=8\cdot8+7$
$8=1\cdot8+0$
$1=0\cdot1+1$
$8-järjestelmän\ luku\ koostuu\ jakojäännöksistä\ lopusta\ alkuunpäin$
$10755_8=4589_{10}\left(=1\cdot8^4+0\cdot8^3+7\cdot8^2+5\cdot8^1+5\cdot8^0\right)$

219, 221, 224

224

$a\ on\ jaollinen\ n:llä\ \ \Rightarrow\ a=c\cdot n\ \ ja\ b\ on\ jaollinen\ n:llä\ \ \ \Rightarrow\ b=d\cdot n\ \ \left(c\ ja\ d\ \in\mathbb{Z}\right)$
$summa\ a+b=c\cdot n+d\cdot n=\left(c+d\right)n=e\cdot n{,}\ c+d=e\in\mathbb{Z}$

$koska\ a+b=e\cdot n\ \ niin\ a+b\ on\ jaollinen\ n:llä$

Kotona: 230, 231, 232, 237

Lukujen suurin yhteinen tekijä ja pienin yhteinen monikerta (jaettava)

Lukujen a ja b

suurin yhteinen tekijä, syt(a,b) on suurin luku, joka jakaa molemmat luvut eli jolla molemmat luvut ovat jaollisia
pienin yhteinen monikerta (tai jaettava), pym(a,b) (pyj(a,b)) on pienin kokonaisluku, joka on jaollinen molemmilla luvuilla.

syt(a,b) ja pym(a,b) löydetään helposti jakamalla luvut a ja b alkutekijöihin.

esimerkki

Määritä syt(a,b) ja pym(a,b), kun a = 72 ja b = 240

Jaetaan luvut alkutekijäihin

$72=8\cdot9=2^3\cdot3^2$
$240=3\cdot8\cdot10=3\cdot2^3\cdot2\cdot5=2^4\cdot3\cdot5$

Nyt syt(a,b) on yhteisten alkutekijöiden tulo ja pym(a,b) on kaikkien alkutekijöiden tulo eli

$syt\left(72{,}240\right)=2^3\cdot3=24\ \ ja\ \ pym\left(72{,}240\right)=2^4\cdot3^2\cdot5=720$

Tehtäviä 235, 238 eteenpäin

Eukleideen algoritmi

Eukleideen algoritmin avulla voidaan määrittää kahden kokonaisluvun a ja b suurin yhteinen tekijä, syt(a, b).

Sen käyttäminen on järkevää erityisesti silloin, kun lukujen a ja b jakaminen alkutekijöihin on työlästä: usein silloin, kun a ja b ovat suuria lukuja.

Eukleideen algoritmissa käytetään jakoyhtälöä toistuvasti; niin kauan kunnes jako menee tasan.

Algoritmissa edetään seuraavasti: luvuista a ja b suurempi jaetaan pienemmällä. Oletetaan, että a > b eli saadaan jakoyhtälö

$a=q_1b+r_1{,}\ \ jos\ r_1\ne0\ niin\ \frac{b}{r_1}$

$b=q_2r_1+r_2{,}\ jos\ r_2\ne0\ niin\ \frac{r_1}{r_2}$
$r_1=q_3r_2+r_3$ jne

Tätä jatketaan kunnes jako menee tasan. Viimeinen jakaja on syt(a, b).

Syt(a, b) voidaan esittää muodossa (eli löytyy sellaiset kokonaisluvut x ja y, että)

$syt\left(a{,}b\right)=ax+by{,}\ jossa\ x\ ja\ y\in\mathbb{Z}$

Tässä käytetään Eukleideen algoritmin jakoyhtälöitä apuna alkaen toiseksi viimeisestä jakoyhtälöstä, jonka jakojäännös on syt.

Esim. Määritä a) syt(120, 84), b) syt(306, 657)

a) syt(120, 84)

$\left(\frac{120}{84}\Rightarrow\right):\ \ 120=1\cdot84+36\ \ \left(kirjassa\ syt\left(120{,}84\right)=syt\ \left(84{,}36\right)\right)$

$\left(\frac{84}{36}\Rightarrow\right):\ \ 84=2\cdot36+12\ \ \ \left(kirja:\ syt\left(84{,}36\right)=syt\left(36{,}12\right)=12\right)$
$\left(\frac{36}{12}\Rightarrow\right)\ :\ \ 36=3\cdot12\ \ eli\ syt\ \left(120{,}\ 84\right)=12$

toinen tapa: jaetaan luvut alkutekijöihin

$120=4\cdot3\cdot10=2^2\cdot3\cdot2\cdot5=2^3\cdot3\cdot5$
$84=4\cdot21=2^2\cdot3\cdot7\$
$eli\ syt\left(120{,}84\right)=2^2\cdot3=12$

b) syt(306, 657)

syt (306, 657) määrittäminen Eukleideen algoritmilla

$657=2\cdot306+45$
$306=6\cdot45+36$
$45=1\cdot36+9$
$36=4\cdot9$
$\Rightarrow\ syt\left(306{,}\ 657\right)=9$

Kotitehtävät: 263, 246 ja (258)

Määritä syt(851, 667) ja esitä syt muodossa 851x + 667y

syt(851, 667)

$851=1\cdot667+184$
$667=3\cdot184+115$
$184=1\cdot115+69$
$115=1\cdot69+46$
$69=1\cdot46+23$
$46=2\cdot23$
$koska\ jako\ meni\ tasan\ niin\ viimeinen\ jakaja\ 23\ on\ syt\left(851{,}\ 667\right)$
$nyt\ etsitään\ kokonaisluvut\ x\ ja\ y\ siten{,}\ että\ 23=851x+667y$
$tässä\ käytetään\ apuna\ Eukleideen\ a\lg orit\min\ jakoyhtälöitä$
$5.\ jakoyhtälöstä\ ratkaistaan\ jakojäännös:\ 23=69-1\cdot46$
$4.\ jakoyhtälöstä\ ratkaistaan\ jakojäännös\ 46=115-1\cdot69{,}\ joka\ sijoitetaan\ edelliseen\ yhtälöön$
$nyt\ 23=69-1\cdot\left(115-1\cdot69\right)=69-1\cdot115+69=2\cdot69-1\cdot115$
$eli\ 23=2\cdot69-1\cdot115$
$3.\ jakoyhtälön\ jakojäännös\ 69=184-1\cdot115{,}\ joka\ sijoitetaan\ yhtälöön\ 23=2\cdot69-1\cdot115$
$23=2\cdot\left(184-1\cdot115\right)-1\cdot115=2\cdot184-3\cdot115$
$2.\ jakoyhtälön\ mukaan\ 115=667-3\cdot184$
$nyt\ 23=2\cdot184-3\cdot\left(667-3\cdot184\right)=11\cdot184-3\cdot667$
$1.\ jakoyhtälön\ mukaan\ 184=851-1\cdot667$
$nyt\ 23=11\cdot\left(851-1\cdot667\right)-3\cdot667=11\cdot851-14\cdot667$
$eli\ 23=851\cdot11+667\cdot\left(-14\right)\ eli\ x=11\ ja\ y=-14$

264, 265, 268

Kotona 266, 268c, 270

Määritä syt(5768, 1545) ja esitä se muodossa 5768x + 1545y

Oppilaskunnalla oli rahaa keväällä 542 €. Hallitus halusi käyttää koko rahan vapputapahtumaan ostamalla munkkeja; tavallisia hintaan 1,1 €/kpl ja hillomunkkeja hintaan 1,5 €/kpl. Kuinka monta tavallista ja hillomunkkia hallituksella oli mahdollista ostaa 542 €:lla?

$tästä\ saadaan\ \ yhtälö\ 1{,}1x+1{,}5y=542$
$\ker tomalla\ tämä\ luvulla\ 10\ saadaan\ Diofantoksen\ yhtälö\ 11x+15y=5420$
$15=1\cdot11+4\ \ \Rightarrow\ \ 4=15-11$
$11=2\cdot4+3\ \ \Rightarrow\ \ 3=11-2\cdot4$
$4=1\cdot3+1\ \ \Rightarrow1=4-3$
$3=3\cdot1$
$syt\ on\ 1=4-3=4-\left(11-2\cdot4\right)=3\cdot4-11$
$1=3\cdot\left(15-11\right)-11=3\cdot15-4\cdot11$
$\left(5420=11x+15y\right)$
$nyt\ yhtälö\ 1=3\cdot15-4\cdot11\ \ker rotaan\ luvulla\ 5420$
$5420=3\cdot5420\cdot15-4\cdot5420\cdot11\ eli\ y_0=3\cdot5420\ \ ja\ x_0=-4\cdot5420$
$yleinen\ ratkaisu$
$\begin{cases} x=-21680+15n&\\ y=16260-11n& \end{cases}$
$lukumäärät\ x\ ja\ y\ on\ oltava\ positiivisia$
$\Rightarrow-21680+15n>0\ \ ja\ 16260-11n>0$
$n>1445{,}3\ \ ja\ n<1478{,}2\ eli\ kokonaisluku\ n\ on\ välillä\ 1446\le n<1478$

$n\ voi\ olla\ 1446{,}\ 1447{,}\ ...\ {,}\ 1478$
$kun\ n=1446:\ x=10\ ja\ y=354$
$toinen\ ääripää\ eli\ n=1478:\ x=490\ ja\ y=2$

Diofantoksen yhtälö

Diofantoksen yhtälö on muotoa

[[$ax+by=c\ \ \left(ax+by+c=0\right){,}\ missä\ a{,}\ b\ ja\ c\ sekä\ yhtälön\ ratkaisut\ x\ ja\ y\ ovat\ kokonaislukuja$]]

Ratkaiseminen, jos ratkaisuja ei helposti löydä kokeilemalla

1. Määritetään syt (a, b) Eukleideen algoritmilla

2. Esitetään syt (a, b) muodossa
[[$syt\left(a{,}b\right)=ax_1+by_1\ \left(yhtälö\ 1\right)$]]

3. tätä verrataan alkuperäiseen yhtälöön [[$ax+by=c$]]
Jos syt(a, b) = c niin yksi yksittäisratkaisupari on
[[$x_1=x_0\ \ ja\ y_1=y_0$]]

Jos syt(a, b) ≠ c niin yhtälö 1 joudutaan kertomaan jollakin kokonaisluvulla t siten, että [[$c=t\cdot syt\left(a{,}b\right)$]]
nyt yksityisratkaisupari on

[[$\ \ \ \ x_0=tx_1\ \ ja\ y_0=ty_1$]]

4. Esitetään Diofantoksen yhtälön [[$ax+by=c$]] yleinen ratkaisu

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

Huom! Diofantoksen yhtälöllä on ratkaisuja, jos c on jaollinen syt(a, b) eli [[$c=t\cdot syt\left(a{,}b\right)$]]

Ratkaise yhtälö
[[$a.\ \ \ \ 28x+36y=8\ $]]

[[$b.\ \ \ \ 2520x+936y=144$]]

Oppilaskunnalla oli rahaa keväällä 542 €. Hallitus halusi käyttää koko rahan vapputapahtumaan ostamalla munkkeja; tavallisia hintaan 1,1 €/kpl ja hillomunkkeja hintaan 1,5 €/kpl. Kuinka monta tavallista ja hillomunkkia hallituksella oli mahdollista ostaa 542 €:lla?

Palauta vastaus

Sinulla ei ole tarvittavia oikeuksia lähettää mitään.