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
Säännöt
Alkuluvun määritelmä
Alkuluvun testaus
Eratostheneen seula
Alkulukulause
Esimerkit
Esimerkki 1: Yksinkertainen alkuluvun testaus
Helppo- 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- 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- 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- 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- 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
- 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
Jakajien tarkistaminen liian pitkälle
Parillisten lukujen käsittely
Eratostheneen seulan väärä toteutus
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.