Alkuluku ongelma
klo 14:34 | 20.1.2008
Vuonna 1992 löydettiin entistä suurempi alkuluku (jaoton luku), (2^756839)-1. Osoita, että tällöin luku (2^756839) + 1 ei voi olla alkuluku. Millä luvulla se on jaollinen?
Kiitos vastauksesta.
En itse keksi keinoa.
Kirjoita nimesi vetoomukseen eläinoikeusjulistuksen puolesta osoitteeseen http://animalsmatter.org
Jaollinen kolmosella.
Muotoa 2ⁿ + 1 olevia lukuja kutsutaan Fermat'n luvuiksi. Näistä luvuista tiedetään, että jos ne ovat alkulukuja, niin n = 2ª, missä a on luonnollinen luku. Nyt tarkasteltava eksponentti 756839 ei voi olla tätä muotoa, koska se on pariton, joten 2^756839 + 1 ei voi olla alkuluku.
EDIT: Oikeastaan vasta muotoa 2^2ⁿ + 1 olevia lukuja kutsutaan Fermat'n luvuiksi.
En oikein osaa lähteä yleisesti etsimään, millä se on jaollinen, mutta luonnollisesti Puuhikin esittämä 3 tulee kyllä väistämättä mieleen. Tarkistetaan, pitääkö se paikkansa.
Todetaan aluksi, että
2² = 4 ≡ 1 (mod 3)
Lähdetään muokkaamaan tästä muodostettua tosiyhtälöä.
2² ≡ 1 (mod 3) ║ ( )^378419
(2²)^378419 ≡ 1^378419 (mod 3)
2^756838 ≡ 1 (mod 3) ║∙2
2^756839 ≡ 2 (mod 3) ║+1
2^756839 + 1 ≡ 3 (mod 3)
2^756839 + 1 ≡ 0 (mod 3)
Viimeiseltä riviltä nähdään, että kun tutkittava luku jaetaan kolmella, niin jakojäännöstä ei tule. Siis luku 2^756839 + 1 on jaollinen kolmella.
□
EDIT: Kirjoitusvirheen korjaus.
Nyt puh ei ymmärrä, mikä alku luku on? 0?
Olen fiksu ja älykäs!
Alkuluku on positiivinen kokonaisluku, joka on jaollinen vain itsellään ja ykkösellä. Luvun yksi ei kuitenkaan yleensä katsota kuuluvaksi alkulukuihin. Alkulukuja ovat siis 2, 3, 5, 7, 11, jne. koska ne ovat jaottomia lukuja.
EDIT: täsmennys
Okei, nyt selkis.
Olen fiksu ja älykäs!
Alkulukuparit ovat muotoa 6n +/- 1. (2^756839) ei ole 6n koska sen alkulukutekijöinä on pelkkiä kakkosia.
EDIT: Tuo on huono tapa, koska se ei auta selvittämään millä luvulla tuo luku on jaollinen.
No en minä silti sitä huonoksi tavaksi sanoisi. Muutenkin isojen lukujen tekijöiden selvittäminen on melkein kuin oma tieteenalansa.
EDIT: Sitä paitsi auttaahan se jaollisuuden löytymisessä. Jos tiedetään, että 2^756839 - 1 on alkuluku (ei 3:lla jaollinen) ja luvun 2^756839 tekijät ovat pelkkiä kakkosia (ei siis 3:lla jaollinen), niin seuraava luku 2^756839 + 1 on väistämättä kolmella jaollinen. Oikein harmittaa, kun tämä ei tullut ihan ensimmäisenä tapana itselleni mieleen, vaan ajattelin asiat turhan monimutkaista reittiä.