Math 2.0

Number theory Definition

Carmichael number

Builds on Composite numberCoprime integersFermat pseudoprime

Definition

A Carmichael number is a composite number nn such that an−1≡1(modn)a^{n-1} \equiv 1 \pmod n for each integer aa coprime to nn.

Remarks

Thus a Carmichael number is a Fermat pseudoprime to each base coprime to it. Korselt's criterion: a composite nn is a Carmichael number if and only if nn is square-free and p−1∣n−1p - 1 \mid n - 1 for each prime p∣np \mid n. The smallest Carmichael number is 561=3⋅11⋅17561 = 3 \cdot 11 \cdot 17. Here 22, 1010 and 1616 divide 560560. Alford, Granville and Pomerance proved in 1994 that there are infinitely many Carmichael numbers.

Reading path

To understand this page from the ground up, read these 9 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionPrime number, definition, no evidence levelPrime numberdefinitionCoprime integers, definition, no evidence levelCoprime integersdefinitionFermat's little theorem, statement, no evidence levelFermat's little theor…statementComposite number, definition, no evidence levelComposite numberdefinitionFermat pseudoprime, definition, no evidence levelFermat pseudoprimedefinitionCarmichael number, definition, no evidence levelCarmichael numberdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Congruence modulo n definition
  3. Greatest common divisor definition
  4. Prime number definition
  5. Coprime integers definition
  6. Fermat's little theorem statement
  7. Composite number definition
  8. Fermat pseudoprime definition
  9. Carmichael number definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Carmichael_number, Overview
About this page
Tag0TA7WT68RK
URIm2://0TA7WT68RK
Aliasesabsolute-pseudoprime
Kinddefinition
WritingW1 stated
MSC11A51
DefinesCarmichael number
UsesComposite number, Coprime integers, Fermat pseudoprime

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.