Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 10,315
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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.