II.2.  Jaollisuus

Esittäessämme murtoluvun muodossa

käytämme itse asiassa hyväksi yhtälöä . Yleisemmin, kun kaksi luonnollista lukua jaetaan tällä tavalla, saadaan ilmeisesti aina aikaan jakotuloksen kokonaisosa ja jakojäännös. Tämä ns. jakoyhtälö osoitetaan seuraavassa oikeaksi pienimmän alkion periaatteella.

Koska samat tarkastelut voidaan tehdä jatkossa usein myös negatiivisille luvuille, siirrymme tarkastelemaan kaikkien kokonaislukujen joukkoa

.

Tässä esiintyvät negatiiviset luvut voidaan matemaattisesti määritellä luonnollisten lukujen 'väärässä järjestyksessä' tehdyillä erotuksilla:

,
,
,
jne.

Todistamme tulevien tarkastelujen perustaksi heti kokonaislukuja koskevan jakoyhtälön.

Lause 2.2.1. (Jakoyhtälö)

Kahdelle kokonaisluvulle ja , joista on positiivinen, on olemassa yksikäsitteisesti määrätyt kokonaisluvut ja siten, että

ja .

Tässä yhtälössä on jaettava, on jakaja, on jakotulos (tai osamäärä) ja on jakojäännös (eli "jaettava = jakotulos . jakaja + jakojäännös").

Todistus. Havainnollistetaan väitettä ensin reaaliakselilla alla olevilla kuvioilla.

Jakoyhtälön olemassaolon todistamiseksi tarkastellaan luonnollisten lukujen osajoukkoa

.

Se ei ole tyhjä joukko, sillä ainakin on sen alkio. Pienimmän alkion periaatteen mukaan joukossa on pienin alkio, olkoon se . Joukon alkiona sillä on esitys jollekin kokonaisluvulle . Siten . Lisäksi tässä , sillä jos olisi päinvastoin , olisi luku lukua pienempi joukon alkio.

Osoitamme sitten jakoyhtälön yksikäsitteisyyden. Oletetaan, että on kaksi esitystä

Koska silloin , riittää osoittaa, että . Jos olisi , olisi ja edelleen , mikä on mahdotonta. Samasta syystä vaihtoehto ei käy. Siten on oltava . Silloin myös .

Esimerkki 2.2.2.

Luvuille ja saadaan laskimella jakotulokseksi likiarvo 32,46. Kun valitaan tämän kokonaisosa 32 jakotulokseksi , saadaan jakojäännökseksi . Annetuille luvuille ja jakoyhtälö on siten muotoa , ts. niille ja .

Jakoyhtälön erikoistapaus saadaan silloin, jos jakojäännös sattuu olemaan nolla, ts. jos jako sattuu menemään tasan. Jos kokonaisluvuille ja on jollekin kokonaisluvulle , sanotaan, että luku on jaollinen luvulla , tai että on luvun tekijä, tai että jakaa luvun , merkitään (jolloin pystyviivan voi lukea jakaa-sanana). Siis

.

Tehtävä. Määrää kaikki luvun 45 tekijät. Määrää edelleen luvun 60 kaikki positiiviset tekijät.

Opiskelutehtävä 13. (Kokonaisluvun positiiviset tekijät)

Määrää kaikki luvun 496 positiiviset tekijät ja laske ne yhteen. Mitä huomaat? Eräällä luvulla lukujen 20 ja 30 välissä on sama ominaisuus. Millä?

Vinkki tehtävään 13

Seuraavassa on tärkeimpiä jaollisuuden perusominaisuuksia.

Lause 2.2.3.

Olkoot , ja kokonaislukuja.

(a)   Jos ja , niin .

(b)   Jos ja , niin kaikilla kokonaisluvuilla ja .

(c)   Jos ja , niin .

(d)   Jos ja , niin .

Todistus. (a) Oletuksen mukaan ja joillekin kokonaisluvuille ja , joten eli .

(b) Tämän kohdan oletuksen mukaan ja , joten kaikilla kokonaisluvuilla ja on

eli .

(c) Jos luku jakaisi summan , oletuksen ja kohdan (b) mukaan se jakaisi myös luvun , mikä on vastoin oletusta. Siis .

(d) Koska oletuksen mukaan ja , on . Jos , myös . Jos taas , yhtälöstä seuraa, että ja siten joko tai . Joka tapauksessa pätee, että .

Opiskelutehtävä 14. (Jaollisuuden todistaminen induktiolla)

Osoita (induktiolla), että luonnollisille luvuille pätee: a) ja b)  .

Vinkki tehtävään 14

Kahdella eri luvulla voi olla samoja lukuja tekijöinään. Ne ovat näiden lukujen yhteisiä tekijöitä.

Tehtävä. Määrää lukujen 45 ja 60 kaikki yhteiset tekijät.

Määrittelemme edelleen, että nollasta eroavien kokonaislukujen ja suurin yhteinen tekijä on näiden yhteinen positiivinen tekijä, joka on jaollinen kaikilla muilla yhteisillä tekijöillä. Toisin sanoen luonnollinen luku on , jos se toteuttaa seuraavat kaksi ehtoa:

(a)   ja ,

(b)   jos ja , niin .

Lisäksi sovitaan, että , kun .

Tehtävä. Mikä lukujen 45 ja 60 yhteisistä tekijästä on suurin? Mitä voit jaollisuuden mielessä sanoa muitten suhteesta suurimpaan (muuta kuin, että ne ovat pienempiä)? Onko tämä yhteisten tekijöiden suurin luku myös suurin yhteinen tekijä edellä olevan määrittelyn mukaan?

On selvää, etteivät lukujen merkit vaikuta suurimpaan yhteiseen tekijään, joten

.

Voimme siis tarkasteluissa yleisesti ilman rajoituksia olettaa, että kaikki tarkasteltavat luvut ovat positiivisia. Selvää on myös, että luvun ja sen tekijän suurin yhteinen tekijä on se tekijä:

.

Isoille luvuille yhteisten tekijöiden etsiminen on työläs tehtävä. On osoitettu jopa, että ei ole olemassa mitään nopeaa ja yleisesti toimivaa algoritmia, joilla kokonaislukujen tekijät voitaisiin määrätä. Täysin yllättävää onkin, että paitsi etsimällä yhteisten tekijöiden joukosta suurinta, suurin yhteinen tekijä voidaan määrätä suoraankin, ilman muiden tekijöiden etsimistä. Tämän jo Eukleideen tunteman menettelyn johtamiseksi todetaan ensin, että suurinta yhteistä tekijää määrättäessä toista lukua voidaan muuttaa toisen monikerralla.

Lause 2.2.4.

Nollasta eroaville kokonaisluvulle ja on

kaikille kokonaisluvuille .

Todistus.

Jokainen lukujen ja yhteinen tekijä on myös luvun tekijä. Ja päinvastoin lukujen ja yhteinen tekijä on myös luvun tekijä. Tarkasteltavilla lukupareilla on siis samat yhteinen tekijät ja siten myös sama suurin yhteinen tekijä.

Kahden luvun suurinta yhteistä tekijää määrättäessä voimme siis suuremmasta luvusta vähentää pienemmän monikertoja ilman että suurin yhteinen tekijä muuttuu. Esimerkiksi luvuille 4187 ja 129 on jakoyhtälön mukaan , joten

.

Käyttämällä saatuun lukupariin uudelleen jakoyhtälöä voimme edelleen pienentää suurempaa lukua: koska , on

.

Tällä parilla ei selvästikään ole ykköstä isompia tekijöitä, joten niitä ei ole alkuperäisellä lukuparillakaan. Tällaisen päättelyn toistamiseen perustuukin ns. Eukleideen algoritmi suurimman yhteisen tekijän määräämiseksi. Esitetään seuraavassa sen yleiset vaiheet ja palataan sen jälkeen vielä äskeiseen esimerkkiin.

Lause 2.2.5. (Eukleideen algoritmi)

Olkoot ja positiivisia kokonaislukuja. Näiden suurin yhteinen tekijä saadaan seuraavalla algoritmilla:

1° Jaetaan luku luvulla jakoyhtälön mukaisesti:

Jos tässä , valitaan ja lopetetaan.

2° Jos , muodostetaan jakoyhtälö luvuille ja :

Jos tässä , valitaan ja lopetetaan.

3° Tästä eteenpäin jatketaan seuraavan periaatteen mukaisesti: Aina, jos jakojäännös on nolla, valitaan edellinen jakojäännös luvuksi . Jos taas jakojäännös ei ole nolla, muodostetaan uusi jakoyhtälö niin, että edellinen jakaja siirretään uudeksi jaettavaksi ja edellinen jakojäännös uudeksi jakajaksi.

4° Koska tällaisessa menettelyssä uusi jakojäännös on aina edellistä pienempi, ei pienimmän alkion (tai rajallisen laskeutumisen) periaatteen johdosta jakojäännös voi olla loputtomasti positiivinen, vaan jossain vaiheessa jakojäännökseksi on tultava nolla. Silloin, olkoon se vaiheessa , saadaan seuraavanlainen tilanne:

5° Valitaan , ts. valitaan viimeinen nollasta eroava jakojäännös suurimmaksi yhteiseksi tekijäksi.

Todistus. Perustellaan lyhyesti algoritmin toimivuus. Ensinnäkin, viimeisestä yhtälöstä nähdään, että . Tällöin myös eli . Näin päättelyä jatkamalla (ja tarvittaessa induktiolla todistamalla) nähdään, että luku jakaa jokaisen edeltävistä jakojäännöksistä ja lopulta myös luvut ja . Luku on siis näiden yhteinen tekijä.

Toisaalta, koska

(joillekin kokonaisluvuille ja ), voidaan ilmeisesti (ja täydellisellä induktiolla todistaen) ilmoittaa muodossa

joillekin .

Tämän yhtälön ja lauseen 2.2.3 kohdan (b) perusteella jokainen lukujen ja yhteinen tekijä on myös luvun tekijä.

Määritelmän mukaan luku on lukujen ja suurin yhteinen tekijä.

Esimerkki 2.2.6.

Määrätään :

Siten .

Tehtävä. Määrää Eukleideen algoritmilla lukujen 345 ja 45 suurin yhteinen tekijä.

Lause 2.2.7.

Nollasta eroavien kokonaislukujen ja suurin yhteinen tekijä voidaan esittää muodossa

joillekin .

Todistus. Katso Eukleideen algoritmin 2.2.5 todistuksen loppuosa.

Muotoa , missä , olevaa summaa sanomme lukujen ja monikertasummaksi. Myös lineaarialgebrallista termiä "kokonaislukukertoiminen lineaarikombinaatio" käytetään yleisesti.

Opiskelutehtävä 15. (Kahden luvun yhteiset tekijät)

Ilmoita luvuille 60 ja 84 a) niiden positiiviset tekijät, b) niiden yhteiset positiiviset tekijät, c) niiden suurin yhteinen tekijä, ja d) yritä keksiä tälle jokin esitys alkuperäisten lukujen monikertasummana.

Vinkki tehtävään 15

Esimerkki 2.2.8.

Edellisessä esimerkissä 2.2.6 saatiin lukujen ja suurimmaksi yhteiseksi tekijäksi . Esitetään se muodossa :

Luvuiksi ja kelpaavat siis esimerkiksi luvut ja .

Huomaa, että monikertasumman kertoimia ja ratkaistaessa, ns. 'paluualgoritmia' tehtäessä, laskuissa esiintyviä jakojäännöksiä ei kerrota koskaan, vaan vain näiden kertoimia yhdistellään. Se jakojäännös, joka on luvun ratkaisualgoritmissa, 'menoalgoritmissa', myöhemmin saatu, korvataan aina kahden edellisen jakojäännöksen monikertasummalla, kunnes lopulta saadaan lukujen ja monikertasumma.

Opiskelutehtävä 16. (Suurin yhteinen tekijä Euklideen algoritmilla)

Määrää Eukleideen algoritmilla lukujen 60 ja 84 suurin yhteinen tekijä ja sille esitys näiden lukujen monikertasummana.

Vinkki tehtävään 16

Suurimman yhteisen tekijän esityksessä kertoimet ja eivät ole yksikäsitteiset, koska näiden tilalle voi aina sijoittaa myös luvut ja , missä voi olla mikä tahansa kokonaisluku. Jos toisaalta jokin muu luku voidaan esittää muodossa , silloin lukujen ja suurin yhteinen tekijä jakaa luvun . Olemme siten todenneet oikeaksi seuraavan karakterisoinnin.

Lause 2.2.9.

Nollasta eroavien kokonaislukujen ja suurin yhteinen tekijä on pienin positiivinen luku , joka voidaan esittää muodossa , missä .

Jos erikoisesti , kuten esimerkissä 2.2.6, sanomme, että luvut ja ovat keskenään jaottomat tai suhteellisesti jaottomat. Puhutaan myös suhteellisista alkuluvuista. Nämä ovat vakiintuneita termejä, kuvaavampia voisivat olla 'yhteistekijättömät' tai 'keskenään supistumattomat'. Huomaa, että keskenään jaottomuus ei tarkoita sitä, että luvut eivät jaa toisiaan, vaan sitä, että niillä ei ole ykköstä isompia yhteisiä tekijöitä.

Tehtävä. Ovatko luvut 15 ja 28 keskenään jaottomat? Entä 35 ja 84?

Lause 2.2.10.

Nollasta eroavat kokonaisluvut ja ovat keskenään jaottomat täsmälleen silloin, kun joillekin .

Todistus. Kokonaisluvut ja ovat keskenään jaottomat, jos ja vain jos niiden suurin yhteinen tekijä on yksi. Lauseiden 2.2.7 ja 2.2.9 perusteella tämä on taas yhtäpitävää sen kanssa, että joillekin kokonaisluvuille ja .

Seuraavassa on eräitä tavallisimpia suurimman yhteisen tekijän ominaisuuksia. Näiden todistukset sivuutetaan tässä.

Lause 2.2.11.

Olkoot , ja nollasta eroavia kokonaislukuja. Tällöin seuraavat pätevät:

(a)   jos , niin ,

(b)   kaikilla ,

(c)   ,

(d)   jos ja , niin ,

(e)   jos sekä ja ovat molemmat luvun tekijöitä, myös tulo on luvun tekijä.

Opiskelutehtävä 17. (Tulon jakaminen)

Olkoot ja keskenään jaottomia kokonaislukuja sekä kokonaisluku sellainen, että . Osoita, että tällöin .

Vinkki tehtävään 17

Suurin yhteinen tekijä voidaan määritellä luontevasti myös useammalle kuin kahdelle luvulle: se on kaikille yhteisistä positiivisista tekijöistä suurin, tai se on yhteisistä positiivisista tekijöistä se, joka on jaollinen kaikilla muilla yhteisillä tekijöillä. Monen luvun yhteisen tekijän etsiminen voidaan aina palauttaa kahden luvun yhteisten tekijöiden määräämisiin. Esimerkiksi kolmelle luvulle , ja pätee, että

.

Nollasta eroaville kokonaisluvuille ja voidaan myös määritellä pienin yhteinen jaettava (pyj). Se on positiivinen kokonaisluku , jolle on voimassa ehdot

(a)   ja , ja

(b)   jos ja , niin .

On selvää, että aina , mutta pienin yhteinen jaettava voi olla tätä tuloa pienempikin. Esimerkiksi lukujen 12 ja 18 pienin yhteinen jaettava on 36.

Voidaan osoittaa, että pienimmälle yhteiselle jaettavalle pätee yhtälö , kun on kyseisten lukujen suurin yhteinen tekijä. Pienimmän yhteisen jaettavan laskeminen palautuukin siis kaavalla

suurimman yhteisen tekijän määräämiseen.

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]