2. Lukuteoriaa
Eukleideen algoritmin sovelluksia
Määritä syt(306, 657) Eukleideen algoritmilla. Määritä sellaiset kokonaislukut x ja y siten, että syt(306, 657) = 306x + 657y
[[$657=2\cdot306+45$]]
[[$306=6\cdot45+36$]]
[[$45=1\cdot36+9$]]
[[$36=4\cdot9$]]
[[$\Rightarrow syt\left(306{,}\ 657\right)=9$]]
[[$Nyt\ määritetään\ kokonaisluvut\ x\ ja\ y\ siten{,}\ että\ 306x+657y=9$]]
Tässä käytetään apuna Eukleideen algoritmin jakoyhtälöitä alkaen viimeisestä jakoyhtälöstä, jossa on syt = 9 jakojäännöksenä
[[$9=45-36{,}\ tähän\ sijoitetaan\ toisen\ jakoyhtälön\ jakojäännös\ 36=306-6\cdot45$]]
[[$9=45-\left(306-6\cdot45\right)=7\cdot45-1\cdot306{,}\ tähän\ sijoitetaan\ eka\ jakoyhtälön\ jakojäännös\ 45=657-2\cdot306$]]
[[$9=7\cdot\left(657-2\cdot306\right)-1\cdot306=7\cdot657-15\cdot306$]]
[[$Nyt\ 306\cdot\left(-15\right)+657\cdot7=9\ \ \ \Rightarrow\ x=-15\ ja\ y=7$]]
Määritä syt(851, 667) ja esitä syt muodossa 851x + 667y
[[$851=1\cdot667+184$]]
[[$667=3\cdot184+115$]]
[[$184=1\cdot115+69$]]
[[$115=1\cdot69+46$]]
[[$69=1\cdot46+23$]]
[[$46=2\cdot23$]]
[[$23=69-46\ \ \left(tähän\ sijoitetaan\ jakojäännös\ 46=115-69\right)$]]
[[$23=69-\left(115-69\right)=2\cdot69-115\ \ \left(tähän\ sijoitetaan\ jakojäännös\ 69=184-115\right)$]]
[[$23=2\cdot\left(184-115\right)-115=2\cdot184-3\cdot115\ \left(tähän\ sij\ jakojäännös\ 115=667-3\cdot184\right)$]]
[[$23=2\cdot184-3\cdot\left(667-3\cdot184\right)=11\cdot184-3\cdot667\ \left(eka\ jakoyhtälön\ jakojäännös\ 184=851-667\right)$]]
[[$23=11\cdot\left(851-667\right)-3\cdot667=11\cdot851-14\cdot667$]]
Koska syt eli 23 = 851x+667y niin vertaamalla tätä yhtälöön
[[$23=11\cdot851-14\cdot667\ niin\ voidaan\ päätellä{,}\ että\ x=11\ ja\ y=-14$]]
Tässä yhtälöä
[[$851x+667y=23\ sanotaan\ Diofantoksen\ yhtälöksi{,}\ jonka\ yksi\ ratkai\sup ari$]]
[[$on\ x=11\ ja\ y=-14$]]
Kotitehtävät 269 ja 271
[[$657=2\cdot306+45$]]
[[$306=6\cdot45+36$]]
[[$45=1\cdot36+9$]]
[[$36=4\cdot9$]]
[[$\Rightarrow syt\left(306{,}\ 657\right)=9$]]
[[$Nyt\ määritetään\ kokonaisluvut\ x\ ja\ y\ siten{,}\ että\ 306x+657y=9$]]
Tässä käytetään apuna Eukleideen algoritmin jakoyhtälöitä alkaen viimeisestä jakoyhtälöstä, jossa on syt = 9 jakojäännöksenä
[[$9=45-36{,}\ tähän\ sijoitetaan\ toisen\ jakoyhtälön\ jakojäännös\ 36=306-6\cdot45$]]
[[$9=45-\left(306-6\cdot45\right)=7\cdot45-1\cdot306{,}\ tähän\ sijoitetaan\ eka\ jakoyhtälön\ jakojäännös\ 45=657-2\cdot306$]]
[[$9=7\cdot\left(657-2\cdot306\right)-1\cdot306=7\cdot657-15\cdot306$]]
[[$Nyt\ 306\cdot\left(-15\right)+657\cdot7=9\ \ \ \Rightarrow\ x=-15\ ja\ y=7$]]
Määritä syt(851, 667) ja esitä syt muodossa 851x + 667y
[[$851=1\cdot667+184$]]
[[$667=3\cdot184+115$]]
[[$184=1\cdot115+69$]]
[[$115=1\cdot69+46$]]
[[$69=1\cdot46+23$]]
[[$46=2\cdot23$]]
[[$23=69-46\ \ \left(tähän\ sijoitetaan\ jakojäännös\ 46=115-69\right)$]]
[[$23=69-\left(115-69\right)=2\cdot69-115\ \ \left(tähän\ sijoitetaan\ jakojäännös\ 69=184-115\right)$]]
[[$23=2\cdot\left(184-115\right)-115=2\cdot184-3\cdot115\ \left(tähän\ sij\ jakojäännös\ 115=667-3\cdot184\right)$]]
[[$23=2\cdot184-3\cdot\left(667-3\cdot184\right)=11\cdot184-3\cdot667\ \left(eka\ jakoyhtälön\ jakojäännös\ 184=851-667\right)$]]
[[$23=11\cdot\left(851-667\right)-3\cdot667=11\cdot851-14\cdot667$]]
Koska syt eli 23 = 851x+667y niin vertaamalla tätä yhtälöön
[[$23=11\cdot851-14\cdot667\ niin\ voidaan\ päätellä{,}\ että\ x=11\ ja\ y=-14$]]
Tässä yhtälöä
[[$851x+667y=23\ sanotaan\ Diofantoksen\ yhtälöksi{,}\ jonka\ yksi\ ratkai\sup ari$]]
[[$on\ x=11\ ja\ y=-14$]]
Kotitehtävät 269 ja 271
Sinulla ei ole tarvittavia oikeuksia lähettää mitään.
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$]]
[[$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$]]
Sinulla ei ole tarvittavia oikeuksia lähettää mitään.
Jaollisuus ja jakoyhtälö
Jaollisuus
Jakoyhtälö
esimerkkejä
Vastaavasti esim 7-järjestelmän luku ajatellaan muodostuvan seuraavasti, esim
220 = 36 * 6 + 4
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.
laskien muuttaa kymmenjärjestelmän luvuksi eli
Tehtävä, jossa apuvälineenä on laskin
Luku a on jaollinen luvulla b, jos löytyy sellainen luku c, että
Sanotaan myös, että b on a:n tekijä tai b jakaa a:n.
21 ei ole jaollinen luvulla 5, silläLukuteoriassa tämä merkitään jakoyhtälön muotoon eli ylläoleva yhtälö kerrotaan luvulla 5
Huom!
Jakoyhtälö
Kun luku a jaetaan luvulla b (luvut ovat kokonaislukuja, jossa b on jakaja ja a jaettava), saadaan
Kun tämä yhtälö kerrotaan b:llä saadaan jakoyhtälö
(r on jakojäännös)
Jos luku jaetaan luvulla 5 (=b) niin r voi saada arvot 0, 1, 2, 3 tai 4
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.
a) kun luku 37 jaetaan luvulla 5, saadaan jakoyhtälö
b) kun luku 1828 jaetaan luvulla 6, saadaan jakoyhtälö
Lukujärjestelmät
Kymmenlukujärjestelmän luku 3861 ajatellaan muodostuvan seuraavasti
Vastaavasti esim 7-järjestelmän luku ajatellaan muodostuvan seuraavasti, esim
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ö.
220 = 36 * 6 + 4
Nyt 6-järjestelmän luku muodostuu jakojäännöksistä, kun ne luetaan lopusta alkuun päin eli
"Pienet 10-järjestelmän luvut" on suhteellisen helppo muuttaa binäärijärjestelmään (2-lukujärjestelmä) päättelemällä esim
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
Teoriaa lukujärjestelmistä
luvussa ilmaisee eri kantaluvun 10 potenssin kerrointa, joista viimeinen numero on 10^0 kerroin.
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.
eli se koostuu eri kantaluvun 8 potenssien kertoimista. Tämä 8-järjestelmän luku voidaan helposti laskimella vain numeroita 0, 1, 2, 3, 4, 5, 6 tai 7.
laskien muuttaa kymmenjärjestelmän luvuksi eli
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
Eukleideen algoritmi
jne
Alkuluvut ovat lukuja, jotka ovat jaollisia luvulla itsellään ja luvulla 1. Eli alkuluvun tekijät ovat 1 ja luku itse.
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.
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
a)
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.
b)
Onko 781 jaollinen alkuluvuilla 2, 3, 5, 7, 11, 13, 17, 19, 23? Huomataan, että 781 = 11*71 eli 781 ei ole alkuluku.
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
Nyt syt(a,b) on yhteisten alkutekijöiden tulo ja pym(a,b) on kaikkien alkutekijöiden tulo eli
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ö
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ä)
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)
Määritä syt(851, 667) ja esitä syt muodossa 851x + 667y
Määritä syt(5768, 1545) ja esitä se muodossa 5768x + 1545y
a) syt(120, 84)
toinen tapa: jaetaan luvut alkutekijöihin
b) syt(306, 657)
Määritä syt(851, 667) ja esitä syt muodossa 851x + 667y
Määritä syt(5768, 1545) ja esitä se muodossa 5768x + 1545y