Fermat's little theorem

From Number
Jump to: navigation, search

Statement

For a relatively prime number

Suppose is a prime number and is a natural number that is not a multiple of . Then, the following equivalent statements hold:

  1. (Divisibility form): divides .
  2. (Congruence form): .
  3. (Order of element modulo another): The order of modulo divides .

For a not necessarily relatively prime number

Suppose is a prime number and is a natural number, not necessarily relatively prime to . Then, the following equivalent statements hold:

  1. (Divisibility form): divides .
  2. (Congruence form): .

Related facts

Stronger facts

Other related facts

  • Wilson's theorem: This states that for any prime , .
  • For a given modulo that is relatively prime to , is modulo if and only if is a quadratic residue modulo .
  • Period in decimal expansion of reciprocal of prime divides prime minus one: Suppose is chosen as a base for writing numbers, and is a prime that does not divide . Then, the expansion of in base has period dividing . In fact, the period equals the order of modulo , and it divides by Fermat's little theorem. It equals if and only if is a primitive root modulo . For , such primes are termed full reptend primes.

Converse

If, for a given relatively prime to , divides , it does not follow that is prime. This leads to some terminology:

  • Fermat pseudoprime to base is a composite number such that and are relatively prime and divides . (Caution: Fermat prime means something very different!)
  • Poulet number is a Fermat pseudoprime to base .
  • Carmichael number, also called absolute pseudoprime, is a composite natural number such that divides for all relatively prime to . Equivalently, divides for all .