Talk:Proth's theorem

drgnrave: One question: What is the difference between proth's and fermat's little theorem. Fermat's states that if p is prime then a^(p-1) is congruent to 1 mod p. If you take proth's, and square both sides you get fermat's. Is the difference that if a proth number fulfills proth's theorem it is prime, unlike fermat's where you can have a psuedo prime?

Yes. If a number satisfies the congruence in Fermat's little theorem then it may turn out to be a pseudoprime. If the number does not have a special form, for example a Proth number, then much slower methods than Proth's theorem must currently be used to prove if it is prime. PrimeHunter (talk) 02:48, 13 February 2008 (UTC)

Proth's Theorem Extended

Here's proof that the Proth entry needs to be edited. Proth's theorem extended (not by much, but w/out sacrifice!):

Let $Q = k*2^n+1, n > 1$ is a natural number and $k \leq 2^n+1$. If for some 'a', $a^{(Q-1)/4} \equiv \pm 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}} \pm 1$ implies that $q \equiv \pm 1 \mod a^{m+2}$ [concluded from generalized Fermat-number 'proofs' by Proth and adjusted by me replacing 'm' with 'm+1'].

Now, if 'p' is any prime divisor of 'R', then $a^{(Q-1)/4} = (a^k)^{2^{n-2}} \equiv \pm 1 \mod p implies that $p \equiv \pm 1 \mod 2^n$.

Thus, if 'R' is composite, 'R' will be the product of at least two primes each of which may have a maximum value of $2^n +1$, and it follows that...

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

Hence, for some 'a', if $k \leq 2^n +1$ and $a^{(Q-1)/4} \equiv \pm 1 \mod Q$, then 'Q' is prime.

• QED

I didn't violate any copyrights; it's MY modification that a high school student could verify.

Thanks,Bill; my e-mail is leavemsg1@yahoo.com

— Preceding unsigned comment added by 99.135.161.116 (talk • contribs) 16:05, 20 July 2014 (UTC)

Remove Template?

I propose removing the template which complains that this article relies mainly on one source, and that it needs more citations. Any objections? MathPerson (talk) 18:55, 10 April 2019 (UTC)

Seeing no objection, I removed the template. MathPerson (talk) 22:58, 3 May 2019 (UTC)

reference is not vol 37 but vol 87

The reference I changed in the text so it was vol 87 instead of vol 37. I include the url for the cover of the 1877 french math periodical for interest.

https://gallica.bnf.fr/ark:/12148/bpt6k3044x.r=proth?rk=21459;2

Endo999 (talk) 07:43, 21 March 2020 (UTC)

Generalization

This paper https://arxiv.org/pdf/2207.12407.pdf says it provides "a generalization of Proth’s theorem for integers of the form Kpn + 1". Billymac00 (talk) 14:15, 27 July 2022 (UTC)