Flaw
There are infinitely many values of (known as Carmichael numbers) for which all values of for which are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers, there are enough of them that Fermat's primality test is often not used in favor of other primality tests such as Miller-Rabin and Solovay-Strassen.
In general, if is not a Carmichael number then at least half of all
are Fermat witnesses. For proof of this, let be a Fermat witness and, ..., be Fermat liars. Then
and so all for are Fermat witnesses.
Read more about this topic: Fermat Primality Test
Famous quotes containing the word flaw:
“She found his manners very pleasing indeed.—The little flaw of
having a Mistress now living with him at Ashdown Park, seems to
be the only unpleasing circumstance about him.”
—Jane Austen (1775–1817)