Alkuluku ongelma

Seuraa 
Viestejä119
Liittynyt10.12.2006

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

Kommentit (8)

Vierailija

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.

Vierailija

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.

Vierailija
NallePuh
Nyt puh ei ymmärrä, mikä alku luku on? 0?

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

NallePuh
Seuraa 
Viestejä1151
Liittynyt19.7.2007
Kale
NallePuh
Nyt puh ei ymmärrä, mikä alku luku on? 0?

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!

Vierailija

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.

Vierailija
Vanhaomena
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ä.

Uusimmat

Suosituimmat