Editing Fermat pseudoprime (section)

== Definition ==
[[Fermat's little theorem]] states that if <math>p</math> is prime and <math>a</math> is [[coprime]] to <math>p</math>, then <math>a^{p-1}-1</math> is [[Divisor|divisible]] by <math>p</math>. For a positive integer <math>a</math>, if a composite integer <math>x</math> divides <math>a^{x-1}-1</math> then <math>x</math> is called a '''Fermat pseudoprime''' to base <math>a</math>. <ref name="JoyOfFactoring">{{cite book | author = Samuel S. Wagstaff Jr. |author-link = Samuel S. Wagstaff, Jr. | title = The Joy of Factoring | publisher =American Mathematical Society | location = Providence, RI | year = 2013 | isbn = 978-1-4704-1048-3 |url =https://www.ams.org/bookpages/stml-68 }}</ref>{{rp|Def. 3.32}}

In other words, a composite integer is a Fermat pseudoprime to base <math>a</math> if it successfully passes the [[Fermat primality test]] for the base <math>a</math>.<ref name="desmedt-10-23">{{cite book |last=Desmedt |first=Yvo |editor1-last=Atallah |editor1-first=Mikhail J. |editor1-link=Mikhail Atallah |editor2-last=Blanton |editor2-first=Marina |year=2010 |title=Algorithms and theory of computation handbook: Special topics and techniques |chapter=Encryption Schemes |publisher=CRC Press |isbn=978-1-58488-820-8 |pages=10–23 |chapter-url=https://books.google.com/books?id=SbPpg_4ZRGsC&pg=SA10-PA23}}</ref> The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the [[Chinese hypothesis]].

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: <math>2^{340} \equiv 1 (\bmod{341})</math> and thus passes the
[[Fermat primality test]] for the base 2.

Pseudoprimes to base 2 are sometimes called '''Sarrus numbers''', after [[Pierre Frédéric Sarrus|P. F. Sarrus]] who discovered that 341 has this property, '''Poulet numbers''', after [[Paul Poulet|P. Poulet]] who made a table of such numbers,  or '''Fermatians''' {{OEIS|id=A001567}}.

A Fermat pseudoprime is often called a '''pseudoprime''', with the modifier '''Fermat''' being understood.

An integer <math>x</math> that is a Fermat pseudoprime for all values of <math>a</math> that are coprime to <math>x</math> is called a [[Carmichael number]].<ref name="desmedt-10-23" /><ref name="JoyOfFactoring" />{{rp|Def. 3.34}}