Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Question about Carmichael numbers

Expand Messages
  • Jens Kruse Andersen
    ... (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
    • 0 Attachment
      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.