Fermat Pseudoprime - Definition

Definition

Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. If a composite integer x is coprime to an integer a > 1 and x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes Fermat primality test for the base a.

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes Fermat primality test for the base 2.

Pseudoprimes to base 2 are sometimes called Poulet numbers, Sarrus numbers, or Fermatians (sequence A001567 in OEIS).

An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.

Read more about this topic:  Fermat Pseudoprime

Famous quotes containing the word definition:

    One definition of man is “an intelligence served by organs.”
    Ralph Waldo Emerson (1803–1882)

    It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.”
    Jane Adams (20th century)

    Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.
    The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)