Editing Fermat primality test (section)

==Flaw==
There are infinitely many [[Fermat pseudoprime]]s to any given basis ''a'' > 1.{{r|PSW|p=Theorem 1}}
Even worse, there are infinitely many [[Carmichael number]]s.<ref name="Alford1994">{{cite journal |last1=Alford |first1=W. R. |author-link=W. R. (Red) Alford |last2=Granville |first2=Andrew |author-link2=Andrew Granville |last3=Pomerance |first3=Carl |author-link3=Carl Pomerance |year=1994 |title=There are Infinitely Many Carmichael Numbers |journal=[[Annals of Mathematics]] |doi=10.2307/2118576 |volume=140 |issue=3 |pages=703–722 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |jstor=2118576 }}</ref> These are numbers <math>n</math> for which <em>all</em> values of <math>a</math> with <math>\operatorname{gcd}(a, n) = 1</math> are Fermat liars. For these numbers, repeated application of the Fermat primality test performs the same as a simple random search for factors. While Carmichael numbers are substantially rarer than prime numbers (Erdös' upper bound for the number of Carmichael numbers<ref>
{{cite journal |author = Paul Erdős
 |date=1956 |title=On pseudoprimes and Carmichael numbers
 |journal=Publ. Math. Debrecen |volume=4 |pages=201–206|author-link=Paul Erdős|mr=0079031 }}</ref> is lower than the [[Prime number theorem|prime number function n/log(n)]]) there are enough of them that Fermat's primality test is not often used in the above form.  Instead, other more powerful extensions of the Fermat test, such as [[Baillie–PSW primality test|Baillie–PSW]], [[Miller–Rabin primality test|Miller–Rabin]], and [[Solovay–Strassen primality test|Solovay–Strassen]] are more commonly used.

In general, if <math>n</math> is a composite number that is not a Carmichael number, then at least half of all

:<math>a\in(\mathbb{Z}/n\mathbb{Z})^*</math> (i.e. <math>\operatorname{gcd}(a,n)=1</math>)

are Fermat witnesses.  For proof of this, let <math>a</math> be a Fermat witness and <math>a_1</math>, <math>a_2</math>, ..., <math>a_s</math> be Fermat liars.  Then

:<math>(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}</math>

and so all <math>a \cdot a_i</math> for <math>i = 1, 2, ..., s</math> are Fermat witnesses.