Prove that there exists a positive integer $k$ such that $k2^n + 1$ is composite for every positive integer $n$. Prove that there exists a positive integer $k$ such that $k2^n + 1$ is composite for every positive integer $n$. (Hint: Consider the congruence class of $n$ modulo 24 and apply the Chinese Remainder Theorem.)
I am struggling with this problem. I have not made any meaningful progress on it. Most of my time were spent on trying to understand the hint. I find it baffling that I should be concerned with the $n \mod 24$ which is the exponent. Anyone has any hints? Or can clarify the hint a bit more? I prefer hints and guiding questions to complete solutions. Thank you for your time.
 A: The idea here is to find a covering set $\{ (a_i, b_i) \}$ of the integers, such that every integer $n\equiv a_i \pmod{b_i}$ for at least 1 pair.
Then, for any prime $p_i$ that divides $2^{b_i} - 1$, if $k  \equiv - 2 ^ { b_i-a_i } \pmod{p_i}$, then $ p_i \mid  k 2^n + 1 $. If $k$ is large enough relative to $p_i$ (E.g. $k> p_i$), then this guarantees the term is composite.
Requirements:

*

*primes $p_i$ are distinct, in order to cleanly apply CRT to get $k$ -> We could allow $p_i$ to not be distinct, and then deal with it. Or we could make $p_i$ be distinct and have a much easier path. Your choice.

*$\sum \frac{ 1}{ b_i } \geq 1$ so that we can can have a hope of covering the integers. -> This is a necessary, and may not be sufficient, condition for a covering set. It is a simple enough first check, that it's worthwhile to be listed out separately.

*$\{(a_i, b_i)\}$ is a covering set of the integers.

Note: We do not require $b_i$ to be distinct, just that the corresponding $p_i$ must work.

*

*With large enough $b_i$, it could contribute multiple $p_i$ and so we could use distinct values of $a_i$.


*If the prime $p$ divides $ 2^b - 1$, we could have $(a, 2b), (a+b, 2b)$ that use the same prime $p$, but in which case we should reduce it to $(a, b)$.
Let $B= lcm (b_1, b_2, \ldots)$. We would want $B$ to have as many divisors as possible, so focusing on the terms $ 2^a 3^b 5^c \ldots$ make sense.
The requirements make it such that "too small" $B$ are unlikely to work, so we'd have to test up to larger values. But, for now, let's just work through small $B$ so that we can see these in play:

*

*With $B = 6$, we have $ 2^2 - 1 = 3, 2^3 - 1 = 7, 2 ^6 - 1 = 63 = 3^2 \times 7 $ doesn't give us distinct primes for requirement 1 so we have to drop one of these. Then, there is no covering set of the form $ (a_1, 2), (a_2, 3)$ since $ \frac{1}{2} + \frac{1}{3} < 1$ violating requirement 2. In particular, this tells us that if $ 6 \mid b$, then we've have to drop (at least) one of these values.

*With $ B = 10$, we have $ 2^2 - 1 = 3, 2^5 - 1 = 31, 2^{10} - 1 = 3 \times 11 \times 31$, so we can get our distinct primes, but again $ \frac{1}{2} + \frac{1}{5} + \frac{1}{10} < 1 $ violates requirement 2.

*With $B = 8, 9, 12, 15, 16, 20$, it is left as an exercise to the reader to show why they work or do not work. (My guess is that they do not, since otherwise the hint/solution would have used them, but you never know.)

*With $ B = 24$, $ \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{12} + \frac{1}{24}  = \frac{3}{2}$, so we could drop some residue classes (e.g. 6 as indicated above) to force the distinct primes condition. Work this out yourself, and determine your value of $k$.

*Now pick some other $B = 2^a 5 ^c $ and try to make this work.

A: Thanks to @CalvinLin, I was able to work out the problem and learn more about covering systems.
I am not going to go too in–depth (you can see Calvin's solution). I am just going to provide a covering system $\mod 24$ and what $k$ has to satisfy.
First notice that for any integer $n$, one of the following is true $$n\equiv 0\mod 2$$ $$n\equiv 0\mod 3$$ $$n\equiv 3 \mod 4$$ $$n\equiv 1 \mod 8$$ $$n\equiv 5\mod 12$$ $$n\equiv 13\mod 24$$
I will let you think about why this is true.
Now observe that $$2^2-1\equiv 0\mod 3$$ $$ 2^3-1 \equiv 0 \mod 7$$ $$2^4-1 \equiv 0 \mod 5$$ $$2^8-1\equiv 0\mod 73$$ $$2^{12}-1\equiv 0\mod 13$$ and $$2^{24}-1\equiv 0\mod 17$$
From these and the relation for $k$ listed on @Calvin's post, we get that $$k\equiv -1 \mod 3$$ $$k\equiv -1 \mod 7$$ $$k\equiv -2\mod 5$$$$k\equiv -2^7 \mod 73$$$$k\equiv -2^7 \mod 13$$ $$k\equiv -2^{11} \mod 17$$
Now CRT takes over and we get our solution
