Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM 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



quasi
Posts:
11,916
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 / subcase 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^(n1) = 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^(n1) = 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^(n1) = 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^(n1) = 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^(n1) = 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



