Näennäisalkuluku

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 

Fermat'n pienen lauseen mukaan kaikilla alkuluvuilla p ja positiivisilla kokonaisluvuilla a jotka eivät ole jaollisia p:llä on voimassa . 

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  sanotaan Fermat'n näennäisalkuluvuksi kannan a suhteen.

Esimerkiksi  ja , 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

Fermat'n näennäisalkuluku
Frobeniuksen näennäisalkuluku
Eulerin näennäisalkuluku 
Eulerin–Jacobin näennäisalkuluku 
Erittäin vahva Lucasin näennäisalkuluku
Fibonaccin näennäisalkuluku
Lucasin näennäisalkuluku
Perrinin näennäisalkuluku
Somerin–Lucasin näennäisalkuluku
Vahva Lucasin näennäisalkuluku
Vahva näennäisalkuluku

Lähteet

Viitteet 

Alkuluvut

nl:Kleine stelling van Fermat#Pseudo-priemgetallen