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

Palauta vastaus

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$]]

Palauta vastaus

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

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$

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}$

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.

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$

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)

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

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