Expand Messages
• ... (mod n) for every a relatively prime to n. Yes, the definition says the composite n is a Carmichael number iff: a^(n-1)==1 (mod n) for every a relatively
Message 1 of 3 , Jul 1, 2004
Jose RamÃ³n Brox wrote:
> According to The Prime Glossary, a composite is a Carmichael number a^(n-1)==1
(mod n) for every a relatively prime to n.

Yes, the definition says the composite n is a Carmichael number iff:
a^(n-1)==1 (mod n) for every a relatively prime to n

> I ask: There's no bound to a in the definition? Something like a<=n-1. If it
actually is for every a, then I can't see how you prove a precise number (like
561) being a Carmichael.

There are definitions, and then there is a nice little thing mathematicians are
rather fond of: Theorems.
It is trivial to show that a<=n-1 is sufficient. It follows immediately from the
simple rule:
If a==b (mod n) then a^x == b^x (mod n).

Example of more complicated theorem: x is a Carmichael number (i.e. satisfies
the definition) if the prime factorization is on the form
(6n+1)*(12n+1)*(18n+1). The proof is omitted.
(There are many other Carmichael numbers).

> But if a is bounded, then I see no problem with Carmichaels in primality
testing... just take the a's over the bound.

A finite bound can still be infeasible, and it is for large prp's.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.