A Sierpinski number is an odd number $k$ such that $k2^n+1$ takes only composite values. In 1962, Selfridge proved that $78557$ is a Sierpinski number. It remains the smallest known such number.
How was $78557$ originally suspected to be a candidate for proving this property? The year 1962 lies at the dawn of the age where some computer-based search might have been possible, but I would be surprised if that were the case.
The remainders of $k2^n+1\pmod{p}$ repeat for any prime $p$.
If $k=2\pmod3$ then $k2^n+1$ is a multiple of 3 for even $n$; if $k=1\pmod3$ then $k2^n+1$ is a multiple of 3 for odd $n$.
If $k=1\pmod5$ then $k2^n+1$ is a multiple of 5 for $n=4m+2$.
And so on. What he did was to find a set of $p_r$ and residues $b_r$ so that they covered every value of $n$.
Choose $k=2\pmod3$ and $k=3\pmod5$, and you have covered all but $n=1\pmod4$.
After $p=17$ you have all but $n=1\pmod8$ because $17|2^8-1$.
After $p=7$ you have all but two residues $\mod 24$
After $p=13$ you have all but one residue $\mod 24$
After $p=241$ you have all $n$ covered.
There are some choices in the residue classes. For any set $k=\{b_r\pmod p_r\}$, use the Chinese remainder theorem to find $k$.
