Fermat's Little Theorem - Converse

Converse

The converse of Fermat's little theorem is not generally true, as it fails for Carmichael numbers. However, a slightly stronger form of the theorem is true, and is known as Lehmer's theorem. The theorem is as follows:
If there exists an a such that

and for all prime q dividing p − 1

then p is prime.

This theorem forms the basis for the Lucas–Lehmer test, an important primality test.

Read more about this topic:  Fermat's Little Theorem

Famous quotes containing the word converse:

    The American doctrinaire is the converse of the American demagogue, and, in this way, is scarcely less injurious to the public. The first deals in poetry, the last in cant. He is as much a visionary on one side, as the extreme theoretical democrat is a visionary on the other.
    James Fenimore Cooper (1789–1851)

    There is a plain distinction to be made betwixt pleasure and happiness. For tho’ there can be no happiness without pleasure—yet the converse of the proposition will not hold true.—We are so made, that from the common gratifications of our appetites, and the impressions of a thousand objects, we snatch the one, like a transient gleam, without being suffered to taste the other.
    Laurence Sterne (1713–1768)

    Whilst we converse with what is above us, we do not grow old, but grow young.
    Ralph Waldo Emerson (1803–1882)