Alkuluku on positiivinen kokonaisluku $p > 1$, joka on jaollinen vain itsellään ja yhdellä. Toisin sanoen, jos $p$ on alkuluku, niin sen ainoat positiiviset tekijät ovat $1$ ja $p$.

Alkuluvut – määritelmä, testaus ja sovellukset

Alkuluku on positiivinen kokonaisluku, joka on suurempi kuin 1 ja jaollinen vain itsellään ja yhdellä. Alkuluvut ovat lukuteorian perusta ja niillä on tärkeä rooli kryptografiassa ja matematiikassa. Tämä aihe kuuluu lukion pitkän matematiikan opetussuunnitelmaan (LOPS21) ja käsitellään erityisesti kurssissa MAA11: Algoritmit ja lukuteoria. Tällä sivulla opit alkulukujen määritelmän, testaamisen ja sovellukset.

Määritelmä

Alkuluku on positiivinen kokonaisluku , joka on jaollinen vain itsellään ja yhdellä. Toisin sanoen, jos on alkuluku, niin sen ainoat positiiviset tekijät ovat ja . Luku, joka ei ole alkuluku, on yhdistetty luku.

Kaavat

ja ainoat tekijät ovat ja (alkuluvun määritelmä)

on alkuluku, jos kaikilla

Eratostheneen seula poistaa luvun monikerrat välillä ja

Alkulukulause: alkulukuja on äärettömän monta

Säännöt

Alkuluvun määritelmä

Luku on alkuluku, jos sen ainoat positiiviset tekijät ovat ja

Alkuluvun testaus

Luku on alkuluku, jos se ei ole jaollinen millään luvulla välillä ja

Eratostheneen seula

Poista kaikki luvun monikerrat välillä ja . Jäljelle jäävät luvut ovat alkulukuja.

Alkulukulause

On äärettömän monta alkulukua

Esimerkit

Esimerkki 1: Yksinkertainen alkuluvun testaus

Helppo

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
ei ole jaollinen :lla ().
Jakojäännös on , joten ei ole jaollinen :lla.
Koska ei ole jaollinen millään luvulla välillä ja , niin on alkuluku.
Jos luku ei ole jaollinen millään pienemmällä luvulla, se on alkuluku.

Esimerkki 2: Yhdistetty luku

Helppo

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
on jaollinen :lla ().
Koska on jaollinen :lla, se ei ole alkuluku.
Koska on jaollinen luvulla , niin ei ole alkuluku. Se on yhdistetty luku.
Yhdistetty luku on luku, joka ei ole alkuluku ja jolla on muita tekijöitä kuin ja itse luku.

Esimerkki 3: Suurempi alkuluku

Keskitaso

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti. Tarkistetaan vain alkuluvut.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
ei ole jaollinen :lla ().
Jakojäännös on , joten ei ole jaollinen :lla.
ei ole jaollinen :llä (ei päätty :aan tai :een).
Luvut, jotka päättyvät :aan tai :een, ovat jaollisia :llä.
ei ole jaollinen :llä ().
Jakojäännös on , joten ei ole jaollinen :llä.
ei ole jaollinen :llä ().
Jakojäännös on , joten ei ole jaollinen :llä.
Koska ei ole jaollinen millään luvulla välillä ja , niin on alkuluku.
Jos luku ei ole jaollinen millään pienemmällä luvulla, se on alkuluku.

Esimerkki 4: Eratostheneen seula

Vaikea

Löydä kaikki alkuluvut välillä ja Eratostheneen seulalla.

Kirjoita kaikki luvut välillä ja : .
Aloitetaan kaikista luvuista välillä ja .
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki parilliset luvut (paitsi itse).
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki :n monikerrat, jotka eivät ole vielä poistettu.
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki :n monikerrat, jotka eivät ole vielä poistettu.
Alkuluku : Tarkista , joten algoritmi päättyy.
Kun , algoritmi päättyy, koska kaikki :n monikerrat on jo poistettu.
Jäljelle jäävät luvut ovat alkulukuja: .
Kaikki jäljelle jäävät luvut ovat alkulukuja.

Esimerkki 5: Alkulukujen tekijöihin jako

Keskitaso

Jaa luku alkulukujen tuloksi.

Aloitetaan pienimmästä alkuluvusta : .
Jaa luku pienimmällä alkuluvulla, jolla se on jaollinen.
Jatketaan luvulla : , joten .
Jatketaan jakamista, kunnes luku ei ole enää jaollinen tällä alkuluvulla.
Jatketaan luvulla : , joten .
Jatketaan seuraavalla alkuluvulla.
Luku on alkuluku, joten jako on valmis.
Kun saavutetaan alkuluku, jako on valmis.
Alkulukujen tulo on: .
Luku on jaettu alkulukujen tuloksi.

Esimerkki

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Tarkista, onko jaollinen luvuilla (koska ).
ei ole jaollinen :lla (pariton).
ei ole jaollinen :lla ().
ei ole jaollinen :llä ().
Koska ei ole jaollinen millään luvulla välillä ja , niin on alkuluku.

Sovellukset

Kryptografiassa alkuluvut ovat keskeisiä RSA-salauksessa ja muissa salausmenetelmissä. RSA-salaus perustuu siihen, että suurten alkulukujen tulo on vaikea jakaa tekijöihin.
Tietojenkäsittelytieteessä alkuluvut käytetään hajautustaulukoissa ja satunnaislukugeneraattoreissa. Alkuluvut auttavat varmistamaan, että hajautusfunktiot jakavat avaimet tasaisesti.
Matematiikassa alkuluvut ovat perusta lukuteorialle. Alkulukulause sanoo, että on äärettömän monta alkulukua, mikä on yksi matematiikan perustuloksista.
Algoritmien tehokkuusanalyysissä alkulukujen testaus on tärkeä ongelma. Erilaiset algoritmit, kuten Miller-Rabin-testi, ovat tehokkaampia kuin perusjakotesti suurille luvuille.

Yleisiä virheitä

Luvun 1 käsittely

Monet unohtavat, että luku ei ole alkuluku eikä yhdistetty luku. Alkuluvun tulee olla suurempi kuin .

Oikein: Muista: Luku ei ole alkuluku eikä yhdistetty luku. Alkuluvun tulee olla suurempi kuin ja jaollinen vain itsellään ja yhdellä.

Jakajien tarkistaminen liian pitkälle

Monet tarkistavat jakajat liian pitkälle. Riittää tarkistaa jakajat aina luvun neliöjuureen asti, ei itse lukuun asti.

Oikein: Riittää tarkistaa jakajat aina luvun neliöjuureen asti. Jos luku ei ole jaollinen millään luvulla välillä ja , se on alkuluku.

Parillisten lukujen käsittely

Monet unohtavat, että kaikki parilliset luvut (paitsi ) ovat yhdistettyjä lukuja. Ainoa parillinen alkuluku on .

Oikein: Muista: Ainoa parillinen alkuluku on . Kaikki muut parilliset luvut ovat yhdistettyjä lukuja, koska ne ovat jaollisia :lla.

Eratostheneen seulan väärä toteutus

Monet unohtavat, että Eratostheneen seulassa poistetaan luvun monikerrat alkaen luvusta , ei luvusta itse.

Oikein: Muista: Eratostheneen seulassa poistetaan luvun monikerrat alkaen luvusta , koska pienemmät monikerrat on jo poistettu aiemmin.

Usein kysyttyä

Mikä on alkuluku?: Alkuluku on positiivinen kokonaisluku , joka on jaollinen vain itsellään ja yhdellä. Toisin sanoen, jos on alkuluku, niin sen ainoat positiiviset tekijät ovat ja .
Miksi luku 1 ei ole alkuluku?: Luku ei ole alkuluku, koska alkuluvun määritelmä vaatii, että luku on suurempi kuin ja jaollinen vain itsellään ja yhdellä. Luku on erikoistapaus, joka ei ole alkuluku eikä yhdistetty luku.
Miten tarkistan, onko luku alkuluku?: Tarkista, onko luku jaollinen millään luvulla välillä ja . Jos luku ei ole jaollinen millään näistä luvuista, se on alkuluku. Tämä on tehokkain menetelmä pienille luvuille.
Mikä on Eratostheneen seula?: Eratostheneen seula on algoritmi kaikkien alkulukujen löytämiseksi välillä ja . Algoritmi poistaa kaikki luvun monikerrat alkaen luvusta . Jäljelle jäävät luvut ovat alkulukuja.
Onko äärettömän monta alkulukua?: Kyllä. Alkulukulause sanoo, että on äärettömän monta alkulukua. Tämä voidaan todistaa vastaoletuksella: jos olisi vain äärellinen määrä alkulukuja, niin niiden tulo plus olisi uusi alkuluku, mikä on ristiriita.
Mikä on suurin tunnettu alkuluku?: Suurin tunnettu alkuluku muuttuu jatkuvasti, kun uusia alkulukuja löydetään. Suurimmat tunnettavat alkuluvut ovat Mersennen alkulukuja, jotka ovat muotoa , missä on alkuluku.
Miten jaan luvun alkulukujen tuloksi?: Jaa luku pienimmällä alkuluvulla, jolla se on jaollinen. Jatka jakamista, kunnes saavutat alkuluvun. Esimerkiksi: .
Mitä eroa on alkuluvulla ja yhdistetyllä luvulla?: Alkuluku on luku, joka on jaollinen vain itsellään ja yhdellä. Yhdistetty luku on luku, joka ei ole alkuluku ja jolla on muita tekijöitä kuin ja itse luku. Esimerkiksi on alkuluku, mutta on yhdistetty luku (koska ).
Miksi alkuluvut ovat tärkeitä kryptografiassa?: Alkuluvut ovat tärkeitä kryptografiassa, koska suurten alkulukujen tulo on vaikea jakaa tekijöihin. RSA-salaus perustuu siihen, että suurten alkulukujen tulon tekijöihin jako on laskennallisesti vaikea ongelma.
Mikä on alkulukujen jakautuminen?: Alkulukujen jakautuminen on epätasainen: alkulukuja on enemmän pienemmillä luvuilla kuin suuremmilla luvuilla. Alkulukulause sanoo, että alkulukujen tiheys pienenee, kun luvut kasvavat.

Lähteet ja lisämateriaali

LOPS21: MAA11 Algoritmit ja lukuteoria
Lukion pitkän matematiikan kurssi (LOPS21), joka käsittelee alkulukuja ja niiden testaamista. Tämä kurssi on osa lukion opetussuunnitelmaa.
Ylioppilaskokeiden tehtävät
Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut alkuluvuista.
TIM - Pitkän matematiikan kertauskurssi
Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa alkuluvuista.

Alkuluvut – määritelmä, testaus ja sovellukset

Säännöt

Alkuluvun määritelmä

Luku on alkuluku, jos sen ainoat positiiviset tekijät ovat ja

Alkuluvun testaus

Luku on alkuluku, jos se ei ole jaollinen millään luvulla välillä ja

Eratostheneen seula

Poista kaikki luvun monikerrat välillä ja . Jäljelle jäävät luvut ovat alkulukuja.

Alkulukulause

On äärettömän monta alkulukua

Esimerkit

Esimerkki 1: Yksinkertainen alkuluvun testaus

Helppo

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
ei ole jaollinen :lla ().
Jakojäännös on , joten ei ole jaollinen :lla.
Koska ei ole jaollinen millään luvulla välillä ja , niin on alkuluku.
Jos luku ei ole jaollinen millään pienemmällä luvulla, se on alkuluku.

Esimerkki 2: Yhdistetty luku

Helppo

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
on jaollinen :lla ().
Koska on jaollinen :lla, se ei ole alkuluku.
Koska on jaollinen luvulla , niin ei ole alkuluku. Se on yhdistetty luku.
Yhdistetty luku on luku, joka ei ole alkuluku ja jolla on muita tekijöitä kuin ja itse luku.

Esimerkki 3: Suurempi alkuluku

Keskitaso

Tarkista, onko luku alkuluku.

Luku , joten se voi olla alkuluku.
Alkuluvun tulee olla suurempi kuin .
Tarkista, onko jaollinen luvuilla (koska ).
Riittää tarkistaa jakajat aina luvun neliöjuureen asti. Tarkistetaan vain alkuluvut.
ei ole jaollinen :lla (pariton).
Parittomat luvut eivät ole jaollisia :lla.
ei ole jaollinen :lla ().
Jakojäännös on , joten ei ole jaollinen :lla.
ei ole jaollinen :llä (ei päätty :aan tai :een).
Luvut, jotka päättyvät :aan tai :een, ovat jaollisia :llä.
ei ole jaollinen :llä ().
Jakojäännös on , joten ei ole jaollinen :llä.
ei ole jaollinen :llä ().
Jakojäännös on , joten ei ole jaollinen :llä.
Koska ei ole jaollinen millään luvulla välillä ja , niin on alkuluku.
Jos luku ei ole jaollinen millään pienemmällä luvulla, se on alkuluku.

Esimerkki 4: Eratostheneen seula

Vaikea

Löydä kaikki alkuluvut välillä ja Eratostheneen seulalla.

Kirjoita kaikki luvut välillä ja : .
Aloitetaan kaikista luvuista välillä ja .
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki parilliset luvut (paitsi itse).
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki :n monikerrat, jotka eivät ole vielä poistettu.
Alkuluku : Poista kaikki :n monikerrat: .
Poistetaan kaikki :n monikerrat, jotka eivät ole vielä poistettu.
Alkuluku : Tarkista , joten algoritmi päättyy.
Kun , algoritmi päättyy, koska kaikki :n monikerrat on jo poistettu.
Jäljelle jäävät luvut ovat alkulukuja: .
Kaikki jäljelle jäävät luvut ovat alkulukuja.

Esimerkki 5: Alkulukujen tekijöihin jako

Keskitaso

Jaa luku alkulukujen tuloksi.

Aloitetaan pienimmästä alkuluvusta : .
Jaa luku pienimmällä alkuluvulla, jolla se on jaollinen.
Jatketaan luvulla : , joten .
Jatketaan jakamista, kunnes luku ei ole enää jaollinen tällä alkuluvulla.
Jatketaan luvulla : , joten .
Jatketaan seuraavalla alkuluvulla.
Luku on alkuluku, joten jako on valmis.
Kun saavutetaan alkuluku, jako on valmis.
Alkulukujen tulo on: .
Luku on jaettu alkulukujen tuloksi.

Sovellukset

Kryptografiassa alkuluvut ovat keskeisiä RSA-salauksessa ja muissa salausmenetelmissä. RSA-salaus perustuu siihen, että suurten alkulukujen tulo on vaikea jakaa tekijöihin.

Tietojenkäsittelytieteessä alkuluvut käytetään hajautustaulukoissa ja satunnaislukugeneraattoreissa. Alkuluvut auttavat varmistamaan, että hajautusfunktiot jakavat avaimet tasaisesti.

Matematiikassa alkuluvut ovat perusta lukuteorialle. Alkulukulause sanoo, että on äärettömän monta alkulukua, mikä on yksi matematiikan perustuloksista.

Algoritmien tehokkuusanalyysissä alkulukujen testaus on tärkeä ongelma. Erilaiset algoritmit, kuten Miller-Rabin-testi, ovat tehokkaampia kuin perusjakotesti suurille luvuille.

Yleisiä virheitä

Luvun 1 käsittely

Monet unohtavat, että luku ei ole alkuluku eikä yhdistetty luku. Alkuluvun tulee olla suurempi kuin .

Oikein: Muista: Luku ei ole alkuluku eikä yhdistetty luku. Alkuluvun tulee olla suurempi kuin ja jaollinen vain itsellään ja yhdellä.

Jakajien tarkistaminen liian pitkälle

Monet tarkistavat jakajat liian pitkälle. Riittää tarkistaa jakajat aina luvun neliöjuureen asti, ei itse lukuun asti.

Oikein: Riittää tarkistaa jakajat aina luvun neliöjuureen asti. Jos luku ei ole jaollinen millään luvulla välillä ja , se on alkuluku.

Parillisten lukujen käsittely

Monet unohtavat, että kaikki parilliset luvut (paitsi ) ovat yhdistettyjä lukuja. Ainoa parillinen alkuluku on .

Oikein: Muista: Ainoa parillinen alkuluku on . Kaikki muut parilliset luvut ovat yhdistettyjä lukuja, koska ne ovat jaollisia :lla.

Eratostheneen seulan väärä toteutus

Monet unohtavat, että Eratostheneen seulassa poistetaan luvun monikerrat alkaen luvusta , ei luvusta itse.

Oikein: Muista: Eratostheneen seulassa poistetaan luvun monikerrat alkaen luvusta , koska pienemmät monikerrat on jo poistettu aiemmin.

Usein kysyttyä

Mikä on alkuluku?

Alkuluku on positiivinen kokonaisluku , joka on jaollinen vain itsellään ja yhdellä. Toisin sanoen, jos on alkuluku, niin sen ainoat positiiviset tekijät ovat ja .

Miksi luku 1 ei ole alkuluku?

Luku ei ole alkuluku, koska alkuluvun määritelmä vaatii, että luku on suurempi kuin ja jaollinen vain itsellään ja yhdellä. Luku on erikoistapaus, joka ei ole alkuluku eikä yhdistetty luku.

Miten tarkistan, onko luku alkuluku?

Tarkista, onko luku jaollinen millään luvulla välillä ja . Jos luku ei ole jaollinen millään näistä luvuista, se on alkuluku. Tämä on tehokkain menetelmä pienille luvuille.

Mikä on Eratostheneen seula?

Eratostheneen seula on algoritmi kaikkien alkulukujen löytämiseksi välillä ja . Algoritmi poistaa kaikki luvun monikerrat alkaen luvusta . Jäljelle jäävät luvut ovat alkulukuja.

Onko äärettömän monta alkulukua?

Kyllä. Alkulukulause sanoo, että on äärettömän monta alkulukua. Tämä voidaan todistaa vastaoletuksella: jos olisi vain äärellinen määrä alkulukuja, niin niiden tulo plus olisi uusi alkuluku, mikä on ristiriita.

Mikä on suurin tunnettu alkuluku?

Suurin tunnettu alkuluku muuttuu jatkuvasti, kun uusia alkulukuja löydetään. Suurimmat tunnettavat alkuluvut ovat Mersennen alkulukuja, jotka ovat muotoa , missä on alkuluku.

Miten jaan luvun alkulukujen tuloksi?

Jaa luku pienimmällä alkuluvulla, jolla se on jaollinen. Jatka jakamista, kunnes saavutat alkuluvun. Esimerkiksi: .

Mitä eroa on alkuluvulla ja yhdistetyllä luvulla?

Alkuluku on luku, joka on jaollinen vain itsellään ja yhdellä. Yhdistetty luku on luku, joka ei ole alkuluku ja jolla on muita tekijöitä kuin ja itse luku. Esimerkiksi on alkuluku, mutta on yhdistetty luku (koska ).

Miksi alkuluvut ovat tärkeitä kryptografiassa?

Alkuluvut ovat tärkeitä kryptografiassa, koska suurten alkulukujen tulo on vaikea jakaa tekijöihin. RSA-salaus perustuu siihen, että suurten alkulukujen tulon tekijöihin jako on laskennallisesti vaikea ongelma.

Mikä on alkulukujen jakautuminen?

Alkulukujen jakautuminen on epätasainen: alkulukuja on enemmän pienemmillä luvuilla kuin suuremmilla luvuilla. Alkulukulause sanoo, että alkulukujen tiheys pienenee, kun luvut kasvavat.

Lähteet ja lisämateriaali

LOPS21: MAA11 Algoritmit ja lukuteoria

Lukion pitkän matematiikan kurssi (LOPS21), joka käsittelee alkulukuja ja niiden testaamista. Tämä kurssi on osa lukion opetussuunnitelmaa.

Ylioppilaskokeiden tehtävät

Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut alkuluvuista.

TIM - Pitkän matematiikan kertauskurssi

Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa alkuluvuista.