Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question

2 Answers 2

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|improve this answer

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

share|improve this answer
2  
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

 
discard

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.