Talk:Proth's theorem

From Wikipedia, the free encyclopedia

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)