Without using a computer prove that this Proth number cannot be a prime number :
$$43373\cdot 2^{49822}+1$$
Asked
Active
Viewed 236 times
2 Answers
6
Reduce it modulo $3$. Recall $2\equiv -1$ and note $43373\equiv2$ modulo $3$, plus $49822$ is even.
anon
- 151,657
-
2Are 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 01 '13 at 13:46
3
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).
Bill Dubuque
- 272,048