Lyhyt MathCheck-ohje (uuteen välilehteen)
Tässä tehtävässä tutustumme tekijän, suurimman yhteisen tekijän ja alkuluvun käsitteisiin.
Luonnolliset luvut ovat 0, 1, 2, …. Luonnollinen luku t on luonnollisen luvun n tekijä jos ja vain jos on olemassa sellainen luonnollinen luku k, että n = tk. Tällöin myös k on n:n tekijä. Esimerkiksi 3 ja 4 ovat 12:n tekijöitä, koska 12 = 3 · 4 = 4 · 3.
Koska jokaiselle luonnolliselle luvulle n pätee n = 1n, on ykkönen jokaisen luonnollisen luvun tekijä. Koska jokaiselle luonnolliselle luvulle t pätee 0 = t ⋅ 0, on jokainen luonnollinen luku nollan tekijä.
Kirjoita kullekin seuraavista luvuista suurin tekijä, joka on lukua itseään pienempi.
Luonnollinen luku t on kokonaisluvun n tekijä jos ja vain jos t on |n|:n tekijä.
Alkuluku on ykköstä suurempi luonnollinen luku, jolla ei ole muita tekijöitä kuin 1 ja luku itse. Edellä näimme, että luvulla 18 on ja luvulla 19 ei ole muitakin tekijöitä kuin 1 ja luku itse. Siksi 19 on ja 18 ei ole alkuluku.
Luonnollisen luvun n alkutekijä on alkuluku, joka on n:n tekijä. Jokainen ykköstä suurempi luonnollinen luku voidaan esittää täsmälleen yhdellä tavalla alkutekijöiden tulona kasvavassa suuruusjärjestyksessä. Esimerkiksi 12 = 2 · 2 · 3 = 2 · 3 · 2 = 3 · 2 · 2, mutta näistä vain 2 · 2 · 3 on kasvavassa suuruusjärjestyksessä.
| n |
| t |
Sen sijaan on vaikeahkoa todistaa, että mitään ykköstä suurempaa luonnollista lukua ei voi esittää useammalla kuin yhdellä tavalla alkutekijöiden tulona kasvavassa suuruusjärjestyksessä. Teemme sen tämän tehtävän lopussa.
Tehtäviä tyyppiä ”esitä alkutekijöiden tulona” on hauskempi tehdä, jos tuntee helppoja keinoja testata, onko jokin pieni alkuluku annetun luonnollisen luvun tekijä. Tässä kohdassa opettelemme uuden sanan: n on jaollinen m:llä jos ja vain jos m on n:n tekijä.
Tämän luvun tavoitteena on saada sinut tekemään havaintoja, jotka auttavat ymmärtämään myöhemmin esitettäviä asioita.
Mitkä luvut kaiken kaikkiaan voidaan muodostaa edellä kuvatulla tavalla? Lähtökohtana ovat yhä 15 ja 39. VastausJokainen mukana oleva luku on jaollinen kolmella. Jokainen kolmella jaollinen luku on mukana.
Valitse toiset kaksi positiivista kokonaislukua lähtökohdiksi ja tutki, mitkä luvut voi muodostaa yhteen- ja vähennyslaskuilla edellä kuvatulla tavalla. Toista kolmansilla ja ehkä neljänsilläkin luvuilla. HavaintoKaikki muodostuvat luvut ovat pienimmän muodostuneen positiivisen luvun monikertoja, ja jokainen monikerta on mukana. Pienin muodostunut positiivinen luku on alkuperäisten lukujen yhteinen tekijä.
Havainnoista kenties helpoimmin todistettavissa oleva on se, että pienimmän mukana olevan positiivisen luvun jokainen monikerta on mukana. Aiemmin pienin mukana oleva positiivinen luku oli 3, ja jokainen 3:n monikerta oli mukana. Jokainen monikerta on mukana siitä yksinkertaisesta syystä, että pienintä mukana olevaa positiivista lukua saa laskea yhteen itsensä kanssa ja vähentää itsestään miten monta kertaa tahansa.
Myös on melko helppo nähdä, että muita lukuja ei ole mukana kuin pienimmän
mukana olevan positiivisen luvun monikertoja.
Yritä keksiä perustelu!
VihjeKuvittele, että mukana olisi luku,
joka ei ole pienimmän mukana olevan positiivisen luvun monikerta.
Mitä voidaan tehdä sillä ja sitä lähinnä pienemmällä mukana olevalla
luvulla?
VastausOlkoon v pienin mukana
oleva positiivinen luku.
Osoitamme, että jos mukana olisi luku x joka ei ole sen monikerta, niin
syntyisi ristiriita.
Siksi sellaista lukua ei voi olla mukana.
Luku x sijoittuisi kahden monikerran iv ja
(i + 1)v väliin.
Sitä lähinnä pienempi mukana oleva luku y olisi joko iv tai
sijoittuisi iv:n ja x:n väliin.
Siis iv ≤ y < x < (i + 1)v.
Vähennyslaskulla löydettäisiin x − y, joten senkin pitää olla
mukana.
Sille pätee 0 < x − y ≤ x − iv <
(i + 1)v − iv = v.
Niinpä v ei olisikaan pienin mukana oleva positiivinen luku, vastoin
v:n valintaa päättelyn alussa.
Ei ole ihan helppoa todistaa, että pienin muodostunut positiivinen luku on alkuperäisten lukujen yhteinen tekijä. Palaamme asiaan kehitettyämme lisää teoriaa, mutta yksi tarpeellinen tosiasia on riittävän helppo todistettavaksi jo nyt.
Mikä johtopäätös edellisestä voidaan tehdä? Vastaus Jos t on kahden luonnollisen luvun yhteinen tekijä, niin se on myös niiden summan ja erotuksen tekijä.
Luonnolliset luvut n ja m ajatellaan jo löydetyiksi, ja niistä muodostetaan lukuja yhteen- ja/tai vähennyslaskuilla kuten äsken. Miten edellinen johtopäätös laajenee tähän tilanteeseen? VastausJos t on n:n ja m:n yhteinen tekijä, niin t on myös jokaisen näin löytyvän luvun tekijä. Vaikka yhteen- tai vähennyslaskun osapuolina eivät olisikaan n ja/tai m vaan myöhemmin löydetyt luvut, nekin ovat t:llä jaollisia, joten myös niiden summa ja erotus ovat.
Olemme hoksanneet, että jos on kaksi luonnollista lukua, joista ainakin toinen ei ole 0, niin niillä on ainakin yksi yhteinen tekijä, mutta ei voi olla miten suuria yhteisiä tekijöitä tahansa. Siksi niillä on suurin yhteinen tekijä.
Kahden luonnollisen luvun suurin yhteinen tekijä voidaan löytää esittämällä luvut alkutekijöiden tuloina ja poimimalla ne alkutekijät, jotka esiintyvät molemmissa. Alkutekijä otetaan mukaan niin monta kertaa, kuin se esiintyy siinä luvussa, jossa se esiintyy vähemmän kertoja. Esimerkiksi koska 45 = 3 · 3 · 5 ja 54 = 2 · 3 · 3 · 3, niiden suurin yhteinen tekijä syt(45, 54) on 3 · 3 = 9. Koska 12 = 2 · 2 · 3 ja 66 = 2 · 3 · 11, niiden suurin yhteinen tekijä on syt(12, 66) = 2 · 3 = 6.
Tämä tapa etsiä suurin yhteinen tekijä on käytännöllinen vain pienillä luonnollisilla luvuilla, koska suurten luonnollisten lukujen jakaminen tekijöihin on työlästä. Parempi tapa löytää suurin yhteinen tekijä tunnetaan nimellä Eukleideen algoritmi. Siitä on olemassa kaksi versiota, antiikkinen (kirjaimellisesti!) ja moderni. Moderni versio on tehokas, mutta sopii huonosti käsin laskentaan. Tutustumme siihen joskus toiste. Antiikkinen versio sopii hyvin käsin laskentaan.
Antiikkinen versio toimii toistamalla seuraavaa kunnes jäljellä olevat luvut ovat yhtäsuuret tai toinen niistä on 0: vähennetään suuremmasta luvusta pienempi, heitetään suurempi luku pois ja otetaan vähennyslaskun tulos mukaan. Esimerkiksi jos luvut ovat 98 ja 70, laskelma etenee seuraavasti: 98 − 70 = 28, 70 − 28 = 42, 42 − 28 = 14, 28 − 14 = 14. Nyt jäljellä ovat 14 ja 14. Ne ovat yhtäsuuret, joten lopetetaan ja tulos on 14.
| 98 |
| 70 |
| 98 / 14 |
| 70 / 14 |
| 7 |
| 5 |
Sievennä seuraavat murtoluvut.
Johtaaksemme erään tärkeän suurinta yhteistä tekijää koskevan tuloksen, tarvitsemme jakoyhtälöä. Jakoyhtälö on muutenkin laajasti hyödyllinen luonnollisten lukujen käsittelyssä.
Jakoyhtälön muistamisessa auttaa ajatella lastenkutsuja. Oletetaan, että kutsuilla on m lasta. Heille jaetaan n ilmapalloa mahdollisimman tasan, kuitenkin rikkomatta ilmapalloja. Jako ei välttämättä mene tasan. Jakojäännöstä eli yli jäävien ilmapallojen määrää merkitään n mod m. Osamäärää eli kunkin lapsen saamaa ilmapallojen määrää merkitään n div m.
Yllä olevasta saadaan alla oleva niissä tapauksissa, kun n ja m ovat luonnollisia lukuja ja m ≠ 0. Laajennos negatiivisiin kokonaislukuihin voidaan tehdä monin tavoin. Eri ohjelmointikielissä on käytetty eri tapoja. Alla on käytetty matemaatikkojen suosimaa tapaa.
Tätä kutsutaan jakoyhtälöksi.
Tarvitsemme jatkossa seuraavaa lausetta. Se kertoo, että syt(n, m) voidaan muodostaa laskemalla sopiva n:n monikerta ja vähentämällä siitä sopiva m:n monikerta, tai laskemalla sopiva m:n monikerta ja vähentämällä siitä sopiva n:n monikerta.
Lause 1 Olkoot n ja m luonnollisia lukuja ja n ≠ 0. On olemassa sellaiset kokonaisluvut x ja y, että xn + ym = syt(n, m).
Kuvitellaan, että x ja y valitaan vuoronperään kaikilla mahdollisilla tavoilla, ja asetetaan niin saatavat luvut xn + ym jonoon suuruusjärjestykseen. Jonoon kuuluu ainakin luku −3m, koska se saadaan valitsemalla x = 0 ja y = −3. Jonoon kuuluu myös 0, koska se saadaan valitsemalla x = y = 0. (Ne voivat itse asiassa olla sama luku, koska emme ole olettaneet, että m ≠ 0.)
Todistuksemme käyttää pienintä positiivista yllä olevaan jonoon kuuluvaa lukua. On tarpeen varmistua, että sellainen luku on olemassa. Mikä varmistaa, että jonossa on yhtään positiivista lukua? VastausValinta x = 1 ja y = 0 tuottaa xn + ym = n. Koska lauseessa oletettiin, että n ≠ 0 ja n on luonnollinen luku, pätee n > 0.
| x |
| 2 |
Tässä tapauksessa kuitenkin on varmaa, että jonossa on pienin positiivinen luku. Merkitsemme sitä k:lla ja valitsemme sen tuottavat x ja y. Niinpä k = xn + ym.
Siksi m mod k = m − (xn + ym)d = −xdn + (1 − yd)m. Koska div tuottaa kokonaisluvun, ovat d, −xd ja 1 − yd kokonaislukuja. Niinpä myös −xdn + (1 − yd)m eli m mod k on jonossamme.
Miksi m mod k ei voi olla positiivinen? VastausKoska k on pienin positiviinen jonomme luku, m mod k on sitä pienempi, ja m mod k on jonossamme. Kuinka paljon m mod k on, ja miksi? VastausJakoyhtälön mukaan 0 ≤ m mod k. Juuri todettiin, että 0 < m mod k ei päde. Niinpä m mod k = 0. Toisin sanoen, m on jaollinen k:lla.
Samasta syystä n on jaollinen k:lla. Miksi ei haittaa, että oletettiin n ≠ 0, mutta ei oletettu m ≠ 0? VastausTodistuksemme, että m on jaollinen k:lla, pätee jokaiselle luvulle, jolle pätevät ne asiat, mitä oletettiin m:stä. Luvusta m oletettiin vain, että se on luonnollinen luku. Myös n on luonnollinen luku. Lisätieto, että n ≠ 0, ei kumoa sitä, että n on luonnollinen luku.
Niinpä k eli xn + ym on m:n ja n:n yhteinen tekijä.
Saamme k = xn + ym = xtj + yti = t(xj + yi). Koska k on positiivinen ja xj + yi on kokonaisluku, pätee t ≤ k. Niinpä k eli xn + ym on m:n ja n:n suurin yhteinen tekijä.
Lause 2 Olkoon p alkuluku ja olkoot n ja m luonnollisia lukuja. Jos nm on jaollinen p:llä, niin n tai m (tai molemmat) on jaollinen p:llä.
Jos syt(n, p) = p, niin n on jaollinen p:llä. Tällöin lause pätee.
Jäljellä on tapaus syt(n, p) = 1. Osoitamme, että tällöin m on jaollinen p:llä.
Lauseen 1 mukaan on olemassa sellaiset kokonaisluvut x ja y, että syt(n, p) = …xn + yp. Koska syt(n, p) = 1, pätee …xn + yp = 1. Kertomalla tämän molemmat puolet m:llä saadaan …xnm + ypm = m.
Koska nm on jaollinen p:llä, on olemassa sellainen luonnollinen luku k, että nm = pk. Siksi m = xnm + ypm = xpk + ypm = p(xk + ym).
Kokonaisluku xk + ym ei voi olla negatiivinen, koska muutoin p(xk + ym) eli m olisi negatiivinen vastoin sitä, että m on luonnollinen luku. Niinpä xk + ym on luonnollinen luku. Koska m on p:n ja sen tulo, on m jaollinen p:llä.
Aritmetiikan peruslause Jokainen ykköstä suurempi luonnollinen luku voidaan esittää täsmälleen yhdellä tavalla alkutekijöiden tulona kasvavassa suuruusjärjestyksessä.
Näimme aikaisemmin, että ainakin yhdellä tavalla voidaan esittää. Nyt osoitamme, että ei voida esittää useammalla tavalla. Olkoot p1p2⋯pi ja q1q2⋯q j kaksi esitystä samalle luvulle. Todistamme, että ne ovat sama esitys.
Siis p1p2⋯pi = q1q2⋯q j.
Jos i = j = 1, niin …p1 = p1p2⋯pi = q1q2⋯q j = q1, joten p1 = q1.
Lauseen 2 mukaan p1 on q1:n tai q2⋯q j:n tekijä. Jos p1 on q2⋯q j:n tekijä ja j > 2, niin lauseen 2 mukaan p1 on q2:n tai q3⋯q j:n tekijä. Näin jatkamalla nähdään, että p1 on jonkin luvuista q1, …, q j tekijä. Koska ne ja p1 ovat alkulukuja, tämä on mahdollista vain siten, että p1 on jokin luvuista q1, …, q j. Koska q1 ≤ … ≤ q j, saadaan p1 ≥ q1.
Samalla tavalla saadaan q1 ≥ p1. Niistä yhdessä tulee p1 = q1. Siitä seuraa p2⋯pi = q2⋯q j.
Olemme todistaneet, että p1 = q1 ja joko i = j = 1 tai i > 1, j > 1 ja p2⋯pi = q2⋯q j. Tapaus p2⋯pi = q2⋯q j on muuten sama kuin todistuksen alussa, mutta yhtä lyhyemmille esityksille. Siksi päättely voidaan toistaa sille. Niin tekemällä saadaan p2 = q2. Jatkamalla näin saadaan p3 = q3, p4 = q4 ja niin edelleen kunnes jompi kumpi esitys loppuu, jolloin toinenkin esitys loppuu.
Tämä riittäköön tällä kertaa.