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

RE: [PrimeNumbers] RE Love prime numbers; have a question

Expand Messages
  • Richard FitzHugh
    ... A witness for n is a witness to its compositeness (there must be a better word than this for non-primality!) so the RH-related statement above doesn t
    Message 1 of 5 , Nov 19, 2005
    • 0 Attachment
      >From: Jose Ram�n Brox <ambroxius@...>
      >To: "Prime Numbers" <primenumbers@yahoogroups.com>
      >Subject: [PrimeNumbers] RE Love prime numbers; have a question
      >Date: Sat, 19 Nov 2005 14:54:44 +0100
      >
      >----- Original Message -----
      >From: "Jose Ram�n Brox" <ambroxius@...>
      >
      >Indeed, Carmichael fails Fermat test and therefore qualify as a-PRP, but
      >not all
      >Carmichaels are a-SPRPs. I also think the infinitude of SPRs is still
      >undecided.
      >
      >---------------------------------------------------
      >
      >Following Mathworld, if the RH is true, any composite n would have a
      >witness (an x so that
      >n is x-SPRP) less than 70�(log n)^2. That would imply the infinitude of
      >SPRPs since every
      >composite would be a SPRP for some base a, though It would leave open the
      >question "Is
      >there a infinity of a-SPRPs for every base a?"

      A "witness" for n is a "witness to its compositeness" (there must be a
      better word than this for non-primality!) so the RH-related statement above
      doesn't actually say anything about whether a composite n must be SPRP to
      any base a, merely that it will fail to be SPRP to a base a less than
      70(logn)^2. (Hasn't this bound been improved? I'm sure I saw a better result
      somewhere...)

      Richard
    Your message has been successfully submitted and would be delivered to recipients shortly.