Forta pseŭdoprimo
En nombroteorio, forta pseŭdoprimo estas nombro kiu pasas fortan pseŭdoprimecan provon al donita bazo. Ĉiuj primoj pasas ĉi tiun provon, sed malgranda frakcio de komponitaj nombroj pasas ĝin same bone.
Formala difino
[redakti | redakti fonton]Komponita nombro n = d · 2s + 1 estas forta pseŭdoprimo al bazo a se kaj nur se unu el la sekvaj kondiĉoj veras:
Devas esti rimarkita tamen, ke R. K. Guy uzas difinon kun nur la unua kondiĉo. Ĉar ne ĉiuj primoj pasas ĉi tiun kondiĉo, ĉi tiu difino de forta pseŭdoprimo similas la primo malpli proksime.
Propraĵoj de fortaj pseŭdoprimoj
[redakti | redakti fonton]Forta pseŭdoprimo al bazo a estas ĉiam eŭlera pseŭdoprimo al bazo a (Pomerance, Selfridge, Wagstaff 1980), sed ne ĉiu eŭlera pseŭdoprimo estas forta pseŭdoprimo. Iuj pseŭdoprimoj de Fermat kaj nombroj de Carmichael estas ankaŭ fortaj pseŭdoprimoj.
Kiel Monier kaj Rabin montris en 1980, komponita nombro n estas forta pseŭdoprimo al maksimume unu kvarono de ĉiuj bazoj <n; tial, ne ekzistas fortaj nombroj de Carmichael, nombroj kiuj estas fortaj pseŭdoprimoj al ĉiuj bazoj.
Estas pruvite ke estas malfinie multaj fortaj pseŭdoprimoj al ĉiu bazo.
Ekzemploj
[redakti | redakti fonton]La unuaj kelkaj fortaj pseŭdoprimoj al bazo 2 estas 2047, 3277, 4033, 4681, 8321, 15841, 29341, ... .
La unuaj kelkaj fortaj pseŭdoprimoj al bazo 3 estas 121, 703, 1891, 3281, 8401, 8911, 10585, ... .
Referencoj
[redakti | redakti fonton]- C. Pomerance, J. L. Selfridge kaj Wagstaff, Jr., S. S., The pseudoprimes to 25 · 109 - La pseŭdoprimoj al 25 · 109, Math. Comp., 35:151 (1980) 1003-1026
- R. K. Guy, "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." - "Pseŭdoprimoj. Eŭleraj pseŭdoprimoj. Fortaj pseŭdoprimoj." §A12 en Unsolved Problems in Number Theory - Nesolvitaj problemoj en nombra teorio, 2-a red. Novjorko: Springer-Verlag, pp. 27-30, 1994.