## Question related to Proth's theorem

Expand Messages
• Proth s Theorem (1878): Let n = h. 2^k + 1 with 2^k h. If there is an integer a such that a^[(n-1)/2] = -1 (mod n), then n is prime. Examining small
Message 1 of 1 , Jun 1, 2006
Proth's Theorem (1878): Let n = h. 2^k + 1 with 2^k > h.

If there is an integer a such that a^[(n-1)/2] = -1 (mod n), then n is
prime.

Examining small integers which satisfy the condition 2^k > h of proth's
theorem
n 2^k h
3 = 2 * 1 + 1
5 = 2^2 * 1 + 1
9 = 2^3 * 1 + 1
13 = 2^2 * 3 + 1
17 = 2^4 * 1 + 1
25 = 2^3 * 3 + 1
33 = 2^5 * 1 + 1
41 = 2^3 * 5 + 1

It seems clear that the chance of n satisfying this condition, 2^k > h, of
Proth drops very
quickly as n becomes larger.

How critical is this condition to primeness?

I understand that this condition is critical to the proof of primeness.

I am asking, what is the probability that a given n would be prime
if n = 2^k * h + 1, where h > 2^k and

for some a, a^[(n-1)/2] = -1 ?

I expect that the answer could be determined only empirically in terms of
the size of n.
Your message has been successfully submitted and would be delivered to recipients shortly.