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

Another form of probabilistic test for primeness

Expand Messages
  • Kermit Rose
    If P = x y where x and y are primes, and b is relatively prime to P, then b^(P+1) = b^(x+y). How might this theorem be used to prove that a number was not
    Message 1 of 3 , Jun 23, 2012
    • 0 Attachment
      If P = x y where x and y are primes, and b is relatively prime to P,
      then b^(P+1) = b^(x+y).

      How might this theorem be used to prove that a number was not prime?

      Suppose y is presumed to be prime, but is not really prime.

      Then since y is prime, and 3 is prime,

      it would be true that

      2^(3y+1) =2^(y+3) mod (3y).

      If this equation is not true, it would prove that y is not prime.
      However, if the equation is true, it would not prove that y is prime.

      It will be a matter of empirical research to determine lower bounds
      on composite y such that

      2^(3y+1) = 2^(y+3) mod (3y)

      2^(5y+1) = 2^(y+5) mod (5y)

      2^(7y+1) = 2^(y+7) mod (7y)

      etc

      Kermit
    • Peter Kosinar
      ... Four shalt be the number thou shalt count, and the number of the counting shalt be four. For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so
      Message 2 of 3 , Jun 23, 2012
      • 0 Attachment
        > It will be a matter of empirical research to determine lower bounds
        > on composite y such that
        >
        > 2^(3y+1) = 2^(y+3) mod (3y)
        > 2^(5y+1) = 2^(y+5) mod (5y)
        > 2^(7y+1) = 2^(y+7) mod (7y)

        Four shalt be the number thou shalt count, and the number of the counting
        shalt be four.

        For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so
        2^(4x+1) = 0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder
        Theorem, we get 2^(4x+1) = 2^5 (mod 4x)

        We also have 2^(x+4) = 2^(5 + (x-1)), which gets us
        2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT
        gives 2^(x+4) = 2^5 (mod 4x)

        Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest counterexample
        for any odd prime x.

        Peter
      • Kermit Rose
        ... counting shalt be four. ... 0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder Theorem, we get 2^(4x+1) = 2^5 (mod 4x) ... counterexample for
        Message 3 of 3 , Jun 24, 2012
        • 0 Attachment
          On 6/23/2012 5:44 PM, Peter Kosinar wrote:
          >> It will be a matter of empirical research to determine lower bounds
          >> on composite y such that
          >>
          >> 2^(3y+1) = 2^(y+3) mod (3y)
          >> 2^(5y+1) = 2^(y+5) mod (5y)
          >> 2^(7y+1) = 2^(y+7) mod (7y)
          >
          > Four shalt be the number thou shalt count, and the number of the
          counting shalt be four.
          >
          > For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so 2^(4x+1) =
          0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder Theorem,
          we get 2^(4x+1) = 2^5 (mod 4x)
          >
          > We also have 2^(x+4) = 2^(5 + (x-1)), which gets us
          > 2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT
          > gives 2^(x+4) = 2^5 (mod 4x)
          >
          > Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest
          counterexample for any odd prime x.
          >
          > Peter

          Hello Peter.

          Thanks.

          My test is even worse than you have discovered.

          For any composite y such that 2^y = 2 mod y, (Original Fermat test
          which fails too many times)
          and for any odd prime x,

          Calculate 2^(xy-x-y+1) mod x and 2^(xy-x-y+1) mod y

          2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^y * 2^(-x-y+1) = 2^(y-x-y+1) =
          2^(-x+1) = 2^(1-1) mod x


          2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^x * 2^(-x-y+1) = 2^(x-x-y+1) =
          2^(-y+1) = 2^(1-1) mod y


          Thus by chinese remainder theorem, 2(xy-x-y+1) = 1 mod (xy).

          This proves that my proposed "new" test is only a disguised Fermat test.

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