2
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ This is USAMO 1982/4. The idea is to find a "covering set" of primes, and 24 just happens to be the first of several small numbers to test that works. Kalva adds the disclaimer that "Comment. This is one of the hardest problems ever set in the USAMO. You have almost no hope of solving it in a reasonable time if you have not seen it before." $\endgroup$ – Calvin Lin Jun 14 '20 at 13:54
  • 3
    $\begingroup$ See Sierpinksi Numbers $\endgroup$ – lulu Jun 14 '20 at 13:57
  • $\begingroup$ @CalvinLin Could you elaborate on cover set idea? And how that connects to the hint above? $\endgroup$ – crystal_math Jun 14 '20 at 13:58
  • $\begingroup$ I agree with the comment that this is a very hard problem, even with the hint. $\endgroup$ – Peter Jun 14 '20 at 14:13
4
$\begingroup$

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.
$\endgroup$
15
  • $\begingroup$ Okay, this seems like a good start! Thanks $\endgroup$ – crystal_math Jun 14 '20 at 14:17
  • $\begingroup$ Is a reduced covering set the same as proper covering set? $\endgroup$ – crystal_math Jun 14 '20 at 14:27
  • $\begingroup$ What is a proper covering set? Note that we could have $n$ covered by multiple sets (and you likely would). I'm using the term "reduced" very loosely, and it likely doesn't help to write a solution with "reduced" defined, but it helps in terms of setting up the cases. $\endgroup$ – Calvin Lin Jun 14 '20 at 14:30
  • $\begingroup$ the $n_i$ are distinct $\endgroup$ – crystal_math Jun 14 '20 at 14:31
  • 1
    $\begingroup$ You should have enough here to work through the question completely. I'd appreciate if you can post the $B= 24$ and even the $B= 8, 9, \ldots $ cases when you're done (as a separate answer). The ideas are "obvious once you see them", but like Peter/Kalva mentioned, can be hard to come up with. This question made the idea of looking at covering sets more known for competition problems, esp in the scenario where "distinct small cases are easy to set up, and we hope to stitch them together" $\endgroup$ – Calvin Lin Jun 14 '20 at 15:00
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.