Näennäisalkuluku

Wikipedia
Loikkaa: valikkoon, hakuun

Näennäisalkuluku eli pseudoalkuluku on yhdistetty luku, joka toteuttaa jonkin sellaisen ominaisuuden, jonka kaikki alkuluvut toteuttavat. On olemassa useita eri näennäisalkulukutyyppejä riippuen siitä, mitä ominaisuutta tarkastellaan. Kun puhutaan yleisesti näennäisalkuluvuista, tarkoitetaan yleensä Fermat'n näennäisalkulukuja. Näennäisalkulukuluvuilla on merkitystä muun muassa alkulukutestien kehittämisessä, todennäköisyyspohjaiset alkulukutestit perustuvat näennäisalkulukuihin. Niiden avulla voidaan sanoa jonkin suuren kokonaisluvun olevan todennäköisesti alkuluku. Tämä on hyödyllistä, kun kyseessä on niin suuri luku, että sen alkuluvuksi todistaminen vaatisi äärimmäisen suurta laskentatehoa.

Fermat'n näennäisalkuluvut[muokkaa | muokkaa wikitekstiä]

Fermat'n pienen lauseen mukaan kaikilla alkuluvuilla p ja positiivisilla kokonaisluvuilla a jotka eivät ole jaollisia p:llä on voimassa a^{p-1}\equiv 1\pmod p.

Kuitenkin on myös yhdistettyjä lukuja, jotka täyttävät saman ehdon kuin alkuluvut Fermat'n pienen lauseen mukaan. Yhdistettyä lukua n, jolla ei ole a:n kanssa muita yhteisiä tekijöitä kuin 1, ja jolle a^{n-1}\equiv 1\pmod {n} sanotaan Fermat'n näennäisalkuluvuksi kannan a suhteen.

Esimerkiksi 341=11\cdot 31 ja 2^{340}\equiv 1\pmod {341}, joten 341 on Fermat'n näennäisalkuluku kannan 2 suhteen. On myös lukuja, jotka ovat Fermat'n näennäisalkulukuja jokaisen kannan suhteen, näitä kutsutaan Carmichaelin luvuiksi tai absoluuttisiksi näennäisalkuluvuiksi.

Erilaisia näennäisalkulukuja[muokkaa | muokkaa wikitekstiä]


Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.