Lukuteoria
Lukujonolaskin
Tutki lukuja: laske Fibonacci-luvut, tarkista alkuluvut, etsi alkutekijät, suurin yhteinen tekijä (SYT) ja pienin yhteinen jaettava (PYJ).
Fibonacci-lukujono
Fibonacci-luvut on yksi kuuluisimmista lukujonoista. Jokainen luku on kahden edellisen summa:
F(n) = F(n−1) + F(n−2), F(0) = 0, F(1) = 1
Ensimmäiset Fibonacci-luvut: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Lukujen suhde F(n+1)/F(n) lähestyy kultaista leikkausta φ ≈ 1,618.
Alkuluvut ja alkutekijät
Alkuluku on jaollinen vain 1:llä ja itsellään. Ensimmäiset alkuluvut: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Luku 2 on ainoa parillinen alkuluku — kaikki muut parilliset luvut ovat jaollisia kahdella, joten niillä on enemmän kuin kaksi tekijää.
Aritmetiikan peruslause: jokainen kokonaisluku ≥ 2 voidaan ilmaista yksikäsitteisesti alkulukujen tulona. Esim. 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5.
SYT ja PYJ — Eukleideen algoritmi
Suurin yhteinen tekijä lasketaan Eukleideen algoritmilla (~300 eaa.):
SYT(a, b) = SYT(b, a mod b), SYT(a, 0) = a
Esimerkki: SYT(48, 36) = SYT(36, 12) = SYT(12, 0) = 12.
PYJ (pienin yhteinen jaettava) lasketaan SYT:n avulla:
PYJ(a, b) = (a × b) / SYT(a, b)
Käyttökohteita
- Murtolukujen sieventäminen — jaa osoittaja ja nimittäjä SYT:llä
- Yhteinen nimittäjä — PYJ on tehokkain
- RSA-salaus — perustuu suurten alkulukujen jakelun vaikeuteen
- Algoritmit — Fibonacci on klassinen rekursio-esimerkki
Usein kysyttyä
Mikä on Fibonacci-lukujono?+
Lukujono, jossa jokainen luku on kahden edellisen summa: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... Esiintyy luonnossa (kukan terälehdet, simpukoiden kuoret) ja taiteessa.
Mikä on alkuluku?+
Alkuluku on luonnollinen luku, joka on suurempi kuin 1 ja jolla on tasan kaksi tekijää: 1 ja itse luku. Esim. 2, 3, 5, 7, 11, 13... Luku 1 ei ole alkuluku.
Mikä on suurin yhteinen tekijä?+
SYT (engl. GCD) on suurin luku, joka jakaa molemmat annetut luvut. Esim. SYT(12, 18) = 6, koska 6 jakaa molemmat eikä mikään isompi luku jaa.
Mikä on pienin yhteinen jaettava?+
PYJ (engl. LCM) on pienin luku, joka on molempien annettujen lukujen kerrannainen. Esim. PYJ(4, 6) = 12. Liittyy SYT:hen kaavalla: a × b = SYT(a,b) × PYJ(a,b).
Miksi alkuluvut ovat tärkeitä?+
Alkuluvut ovat kaiken kokonaislukuaritmetiikan perusta — jokainen luonnollinen luku ≥ 2 voidaan ilmaista yksikäsitteisesti alkulukujen tulona. Käytetään mm. modernissa kryptografiassa (RSA-algoritmi).