Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T23:30:43.785Z Has data issue: false hasContentIssue false
  • English
  • Français

On strong pseudoprimes in arithmetic progressions

Published online by Cambridge University Press:  09 April 2009

A. J. van der Poorten  and
A. Rotkiewicz
A. J. van der Poorten
Affiliation:
School of Mathematics and Physics Macquarie UniversityNorth Ryde, N.S.W. 2113, Australia
A. Rotkiewicz
Affiliation:
Instytut Matematyczmy PAN ul.Sniadeckich 8 00-950 Warszawa, Poland
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A composite integer N is said to be a strong pseudoprime for the base C if with N – 1 = 2sd, (2, d) = 1 either Cd = 1, or C2r ≡ 1 (mod N) some r, 0 ≤ r < s. It is shown that every arithmetic progression ax+b (x = 0,1, …) where a, b are relatively prime integers contains an infinite number of odd strong pseudoprimes for each base C ≤ 2.

1980 Mathematics subject classification (Amer. Math. Soc.): 10 A 15.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 29 , Issue 3 , May 1980 , pp. 316 - 321
Copyright
Copyright © Australian Mathematical Society 1980

References

Carmichael, R. D. (1912), ‘On composite numbers P which satisfy the Fermat congruence a p–1 ≡ 1 mod P’, Amer. Math. Monthly 19, 22–27.Google Scholar
Kanold, H. J. (1950), (Sätze über Kreisteilungspolynome und ihre Anwendungen auf einige zahlentheoretische Probleme’), J. für Math. 187, 169–172.Google Scholar
Lehmer, D. H. (1976), ‘Strong Carmichael numbers’, J. Austral. Math. Soc. Ser. A 21, 508–510.Google Scholar
Malm, D. E. (1977), ‘On Monte-Carlo primality tests’, Notices Amer. Math. Soc. 24, A-529, abstract 77T-A222.Google Scholar
Rabin, Michael O. (1976), ‘Probabilistic algorithms’, in Symposium on new directions and recent results in algorithms and complexity (editor Traub, J. F.) (Academic Press, New York), pp. 21–39.Google Scholar
Pomerance, Carl, Selfridge, John L. and Wagstaff, Samuel S. Jr (1979), ‘The pseudoprimes to 25000000000’ (preprint).Google Scholar
Rotkiewicz, A. (1963), ‘Surles nombres pseudopremiers de la forme ax + b’, C. R. Acad. Sci. Paris 257, 2601–2604.Google Scholar
Rotkiewicz, A. (1967), ‘On the pseudoprimes of the form ax + b’, Proc. Cambridge Phil. Soc. 63, 389–392.Google Scholar
Zsigmondy, K. (1892), ‘Zur Theorie der Potenzreste’, Monatsh. Math. 3, 265–284.Google Scholar