Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: About Carmichael numbers (why they break the converse of Fermat's
Little Theorem, and Fermat Primality Test?)

Replies: 4   Last Post: Sep 20, 2013 1:50 PM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: About Carmichael numbers (why they break the converse of Fermat's Little Theorem, and Fermat Primality Test?)
Posted: Sep 20, 2013 1:50 PM

Kenneth Bull wrote:

>And also I suppose Car. numbers are counter example to
>Fermat's Little Theorem's converse (the gcd / sub-case of
>Euler's theorem form)>

It depends on how the statements are worded.

Here are two variations. In the first case, the converse
fails (due to Carmichael numbers). In the second case
the converse holds.

(1):

If n is prime, then a^(n-1) = 1 (mod n) for all integers a
which are coprime to n.

(1') Converse of (1):

If n is an integer with n > 1 such that a^(n-1) = 1 (mod n)
for all integers a which are coprime to n, then n is prime.

Statement (1) is true but statement (1') is false. The
counterexamples to (1') are precisely the Carmichael
numbers.

But here's a variant:

(2):

If n is prime, then a^(n-1) = 1 (mod n) for all integers a with
1 < a < n.

(2') Converse of (2):

If n is an integer with n > 1 such that a^(n-1) = 1 (mod n)
for all integers a with 1 < a < n, then n is prime.

Statements (2) and (2') are both true. Thus, for this version,
the converse holds. Any composite positive integer n will fail
the congruence a^(n-1) = 1 (mod n) whenever 1 < a < n and
gcd(a,n) > 1. In particular, since Carmichael numbers are
composite, they are not counterexamples statement (2').
Thus, for this version, the converse holds.

quasi

Date Subject Author
9/19/13 Kenneth Bull
9/20/13 quasi
9/20/13 quasi
9/20/13 Kenneth Bull
9/20/13 quasi