Prove that there exists a positive integer $k$ such that $k2^n + 1$ is composite for every positive integer $n$.

contest-mathelementary-number-theoryproblem solvingrecreational-mathematics

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.

Best Answer

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:

  1. 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.
  2. $\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.
  3. $\{(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.

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

  2. 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.
Related Question