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

18375Re: Proth-like thinking

Expand Messages
  • leavemsg1
    Sep 22, 2006
      --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...>
      wrote:
      >
      > Hello, Group.
      >
      > modifying Proth's Theorem...
      >
      > choose an odd 'n' such that 2^k +1 < n < 2*(2^k +1) for some k --
      > notice that this is different from Proth's notion that 'n' must be
      > < 2^k +1.
      >
      > if Z = n*(2^k) +1, then any number relatively prime to, less than,
      > and up to the lower limit for 'n' would rather quickly expose 'Z'
      as
      > composite using the q^(Z-1) != 1 (mod Z) test.
      >
      > choose n = 15, k = 3 and 9 < 15 < 18 and q = 7 since gcd(3 or 5,
      15) !
      > = 1; Z = 121. compute 7^120 == 109^24 == 45^6 == 23 (mod 121). I
      > could have also chosen q = 2, 4, or 8 to prove it not prime.

      Oddly enough, 121 is a psuedoprime base 3 according to Sloane's list.

      >
      > Conversely, however, a single test might also confirm primality
      when
      > the value for 'q' is chosen relatively prime to, less than, and up
      to
      > the lower limit for 'n' as opposed to performing several
      classical 'p-
      > 1' tests.
      >
      > The two notable counter examples for Z < 1000 (that are shown prime
      > via 2^(p-1) == 1 mod p test but are actually composite) are 341 &
      561 and
      > both of them can't be produced using the above criteria since 341 =
      > 2^2 * 85 +1 (85 is much larger than n < 2*(2^2 +1)) and 561 = 2^4 *
      > 35 +1 (35 is just larger than n < 2*(2^4 +1) = 34.
      >
      > Can someone any counter-example using this modification of Proth's
      theorem?
      >
      > i.e. After 'Z' is produced and 'q' is so carefully chosen... Can Z
      be
      > composite and still return a value of '1' from a classical 'p-1'
      test?
      >
      > I can't show it... or prove it, but it would seem so... I think the
      > classical counter-examples would not fall into this class of primes.
      >
      > Bill
      >
      I would name this class of primes... "2nd kind Proth primes"
    • Show all 4 messages in this topic