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

18378Re: Proth-like thinking

Expand Messages
  • leavemsg1
    Sep 24 2:13 PM
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "Paul Underwood"
      <paulunderwood@...> wrote:
      >
      >
      > Bill,
      >
      > is the 771st (?) Carmichael number a counterexample?:
      >
      > ? N=1657700353
      > 1657700353
      > ? factor(N-1)
      >
      > [2 15]
      >
      > [3 2]
      >
      > [7 1]
      >
      > [11 1]
      >
      > [73 1]

      No. The idea for testing any Proth-like number would be to subtract 1
      and divide out 2 until only other prime factors existed, and then to
      compute the classical 'p-1' test with 'any' of those numbers relative-
      ly prime to 50589. Hence, 2, 5, 13 up to 2^15 +1 would work but gcd
      (50589,3)!= 1 and 2 exposes that 1657700353 isn't prime.
      Bill
      The same is true for Proth primes except the test changes to a^((p-
      1)/2) == 1 mod p instead of the 'p-1'.

      >
      > ? n=(N-1)/(2^15)
      > 50589
      > ? 2^15+1<n&&n<2*(2^15+1)
      > 1
      >
      > Paul
      >
    • Show all 4 messages in this topic