## Proth extended

Expand Messages
• 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
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.