Fermat pseudoprime

From Citizendium, the Citizens' Compendium

Jump to: navigation, search


This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Code [?]
 
http://en.citizendium.org/wiki?title=Fermat_pseudoprime&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

A composite number \scriptstyle q\ is called a Fermat pseudoprime to a natural base \scriptstyle a\ , which is coprime to \scriptstyle q\ , if \scriptstyle a^{q-1} \equiv 1 \pmod q.

Contents

Restriction

It is sufficient that the base \scriptstyle a\ satisfies \scriptstyle 2 \le a \le q-2 because every odd number \scriptstyle q\ satisfies \scriptstyle a^{q-1} \equiv 1 \pmod q for \scriptstyle a = q-1\ [1].

If \scriptstyle q\ is a Fermat pseudoprime to base \scriptstyle a\ then \scriptstyle q\ is a Fermat pseudoprime to base \scriptstyle b\cdot q+a for every integer \scriptstyle b \ge 0.

Odd Fermat pseudoprimes

To every odd Fermat pseudoprime \scriptstyle q\ exist an even number of bases \scriptstyle a\ . Every base \scriptstyle a\ has a cobase \scriptstyle a' = q - a\ .

Examples:

15 is a Fermat pseudoprime to the bases 4 and 11
49 is a Fermat pseudoprime to the bases 18, 19, 30 and 31

Properties

Most of the pseudoprimes, like Euler pseudoprimes, Carmichael numbers, Fibonacci pseudoprimes and Lucas pseudoprimes, are Fermat pseudoprimes.

References and notes

  1. ↑ Richard E. Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, page 132, Theorem 3.4.2.

Further reading

Links

Retrieved from "http://en.citizendium.org/wiki/Fermat_pseudoprime"
Views
Personal tools