Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Without using a computer prove that this Proth number cannot be a prime number :

$$43373\cdot 2^{49822}+1$$

share|cite|improve this question
up vote 3 down vote accepted

HINT $\rm\ c = (a\!+\!1,b\!+\!1)\ |\ a\: b^{2\:k}\! + 1\ $ by $\rm\:mod\ c\!\!:\ a,\!b\equiv {-}1\ \Rightarrow\ a\: b^{2\:k}\!+1 \equiv\: -\:(-1)^{2\:k}\!+1\equiv 0\:.$

Above $\rm\ \ c = (43374,3) = 3\:.\ $ Hence $\rm\ a\: b^{2\:k}\! + 1\:$ prime $\rm\:\Rightarrow\ a\!+\!1,\:b\!+\!1\:$ coprime (except in some trivial degenerate cases where the gcd $\rm\:c\:$ is not a proper factor).

share|cite|improve this answer

Reduce it modulo $3$. Recall $2\equiv -1$ and note $43373\equiv2$ modulo $3$, plus $49822$ is even.

share|cite|improve this answer
Are you kidding... it's divisible by 3.. – Eric Naslund Nov 22 '11 at 19:02
Is there some similar known criterion for all Proth numbers ? – pedja Nov 22 '11 at 19:09
@pedja: Proth's theorem, apparently. – anon Nov 22 '11 at 19:19
For large numbers Proth theorem is useless without computer's help... – pedja Nov 22 '11 at 19:36
@pedja but proth's theorem is a practical way to test primality. Do you know a better algoritm ? As for large numbers , well even factoring is hard usually. – mick Nov 1 '13 at 13:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.