Luin lukuteorian kurssin läpi noin vuosi sitten, enkä millään jaksa kerrata, joten pyydänpä lukuteoriaa vaivattomammin muistavilta apua eräälle lukiolaiselle, jota olen hieman neuvonut esseen kirjoituksessa...
Eli yleisempi kysymys oli pienimmästä positiivisesta kokonaisluvusta k, että 2^k = 1 (mod n), missä n on pariton kokonaisluku.
Jos n = 2^m - 1, jollekin m>1, on triviaalia osoittaa, että minimaalinen k on m.
Entä jos n = 2^m 1, jollekin m>0 ? Mikäli n on alkuluku, on triviaalia osoittaa että minimaalinen k on 2m.
Mutta miten löydetään vastaesimerkki/todistus jos n ei tarvitse olla alkuluku?
(Uteliaille: Ota pakka, jossa on 2r korttia ja sekoita sitä toistuvasti niin, että jaat pakan keskeltä halki ja asetat kortit alternoivasti lomittain. Jos asetamme n=2r 1, voidaan osoittaa että minimimäärä tälläisiä sekoituksia palauttaaksesi pakan alkuasentoon on juuri tuo minimi-k.)
Eli yleisempi kysymys oli pienimmästä positiivisesta kokonaisluvusta k, että 2^k = 1 (mod n), missä n on pariton kokonaisluku.
Jos n = 2^m - 1, jollekin m>1, on triviaalia osoittaa, että minimaalinen k on m.
Entä jos n = 2^m 1, jollekin m>0 ? Mikäli n on alkuluku, on triviaalia osoittaa että minimaalinen k on 2m.
Mutta miten löydetään vastaesimerkki/todistus jos n ei tarvitse olla alkuluku?
(Uteliaille: Ota pakka, jossa on 2r korttia ja sekoita sitä toistuvasti niin, että jaat pakan keskeltä halki ja asetat kortit alternoivasti lomittain. Jos asetamme n=2r 1, voidaan osoittaa että minimimäärä tälläisiä sekoituksia palauttaaksesi pakan alkuasentoon on juuri tuo minimi-k.)
Vastaukset 4
Vanhimmat
http://fi.wikipedia.org/wiki/Fermat'n_pieni_lause
=> k = 340 ja n = 341 (ei alkuluku).
... mutta en kysynyt ihan mitä tahansa pseudo-alkulukua, vaan halusin jommankumman näistä:
a) Olkoon k(m) = 'pienin r>0 jolle 2^r = 1 mod (2^m 1)'. Haluan sellaisen m, jolle ei päde k(m)=2m.
b) Todistuksen, että k(m)=2m, kaikille m.
On selvää, että r>m ja toisaalta r=2m toteuttaa ehdon aina. Nyt pitää siis selvittää onko mahdollista 2m>r>m ja vastaus on ei sillä suorita jakokulmassa jakolasku 2^r-1 : 2^m 1
Ensimmäinen osamäärä on 2^(r-m) ja jakojäännös
-2^(r-m)-1 ja tämä on jälleen pienempi kuin jakaja 2^m 1, joten jako ei voi mennä tasan.
Siis mikään luku 2m>r>m ei toteuta ehtoa.
Jakoyhtälöiden avulla esitettynä:
Oletus m
... olevan kunnossa, mutta katsotaan tarkemmin muodollisen todistuksen kohtaa:
2^r-1 = 2^(r-m)*(2^m 1)-2^(r-m)-1
Tuossa meillä on -(2^(r-m) 1), joten loppuargumentissasi pitäisi käyttää 2^(r-m) 1, eikä 2^(r-m)-1. Mutta onneksemme kaikki toimii korjauksenkin jälkeen.
Kiitos tästä oivalluksesta!