Re: [PrimeNumbers] Question about Carmichael numbers
- 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 itactually 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
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 primalitytesting... 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