Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-12T08:09:00.149Z Has data issue: false hasContentIssue false
  • English
  • Français

Finding pseudoprimes

Published online by Cambridge University Press:  23 January 2015

G. J. O. Jameson
G. J. O. Jameson*
Affiliation:
Dept. of Mathematics and Statistics, Lancaster University, Lancaster LA1 4YF e-mail:, [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

Recall that Fermat's ‘little theorem’ says that if p is prime and a is not a multiple of p, then ap − 1 ≡ 1 mod p.

This theorem gives a possible way to detect primes, or more exactly, non-primes: if for a certain a coprime to n, a− 1 is not congruent to 1 mod n, then, by the theorem, n is not prime. A lot of composite numbers can indeed be detected by this test, but there are some that evade it. Let us give ourselves some notation and terminology to discuss them.

Type
Articles
Information
The Mathematical Gazette , Volume 95 , Issue 534 , November 2011 , pp. 420 - 432
Copyright
Copyright © The Mathematical Association 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Jameson, G. J. O., Finding Carmichael numbers, Math. Gaz., 95 (July 2011) pp. 244–255.Google Scholar
2. Burton, David M., Elementary number theory (6th edn.), McGraw-Hill (2007).Google Scholar
3. Pinch, R. G. E., The pseudoprimes up to 1013 , Algorithmic number theory (Leiden, 2000), pp. 459–473, Lecture Notes in Compo Sci. 1838, Springer (2000).Google Scholar
4. Ribenboim, P., The new book of prime number records, Springer (1996).Google Scholar
5. Koblitz, Neal, A course in number theory and cryptography, Springer (1987).Google Scholar
6. Rosen, Kenneth H., Elementary number theory and its applications, Addison-Wesley (1988).Google Scholar
7. Jameson, G. J. O., Carmichael numbers and pseudoprimes, at http://www.maths.lancs.ac.uk/~jamesonGoogle Scholar