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

Proth extended

Expand Messages
  • Bill Bouris
    Proth theorem extended(but not by much, but w/out any sacrifice): Let Q= k*2^n +1, where n= 3 is an odd natural number & k
    Message 1 of 1 , Jan 31, 2010
    • 0 Attachment
      Proth theorem extended(but not by much, but w/out any sacrifice):

      Let Q= k*2^n +1, where n=> 3 is an odd natural number & k<= 2^n+1.
      If for some 'a', a^((Q-1)/4) == +/-1 (mod Q), then 'Q' is prime.
      Proof:

      If 'm' is from the set of natural numbers, then every odd prime
      divisor 'q' of a^(2^(m+1))+/-1 implies that q == +/-1(mod a^(m+2))
      [concluded from generalized Fermat-number 'proofs' by Proth and
      adjusted by my replacing 'm' with 'm+1'].

      Now, if 'p' is any prime divisor of 'R', then a^((Q-1)/4) = (a^k)^
      (2^(n-2)) == +/-1(mod p) implies that p == +/-1 (mod 2^n).
      Thus, if 'R' is composite, 'R' will be the product of at least two
      primes each of which has either a minimum value of (2^n -1) or a
      maximum value of (2^n +1), and it follows that...

      k*2^n +1 >= (2^n +1)*(2^n +1) = (2^n)*(2^n) + 2*(2^n) +1; but the
      1's cancel, so k*(2^n) >= (2^n)*(2^n) + 2*(2^n) and upon dividing
      by 2^n... implies that k>= 2^n +2.

      (2^n -1)*2^n +1 = (2^n)*(2^n) - 2^n +1 >= (2^n -1)*(2^n -1)= (2^n)
      *(2^n) - 2*(2^n) +1; but the 1's cancel again, and multiplying by
      -1 and dividing by (2^n) implies that 1 < 2.

      Hence, both results confirm that for some 'a', if k<= 2^n +1 and
      a^((Q-1)/4) == +/-1 (mod Q), then 'Q' is prime.
      *QED
    Your message has been successfully submitted and would be delivered to recipients shortly.