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$