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 $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

• 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

• Rosen, Kenneth H.: Elementary Number Theory and Its Applications. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)