- #1
ehrenfest
- 2,001
- 1
Homework Statement
Prove that there exists a positive integer k such that k 2^n+1 is composite for every positive integer n. (Hint: Consider the congruence class of n modulo 24 and apply the Chinese Remainder Theorem).
Homework Equations
The Attempt at a Solution
Notice that
2^{24}=(2^3-1)(2^3+1)(2^6+1)(2^12+1)=3^2*5*7*13*4097
Let n=24q+r.
We want to write down enough equation of the form x \equiv a_i \mod m_i, where the m_i are relatively prime so that the solution k to these equations will have the desired properties.
This means that for each value of r in [0,23], we need to have a congruence equation such that 2^{24q+r}+1 \equiv m_i \mod a_ifor some i.
Notice that if we set
k 2^{24q}+1\equiv k+1 \equiv 0 \mod 3,
this takes care of all the cases where r is even (by Fermat's Little Theorem).
If we set
k 2^{24q+1}+1 \equiv 2 k +1 \equiv 0 \mod 5,
that takes care of r=1,5,9,13,17,21 by Fermat's Little Theorem.
Setting
k 2^{24q+3}+1 \equiv 8 k +1 \equiv 0 \mod 7
k 2^{24q+7}+1 \equiv 128 k +1 \equiv 0 \mod 13
we take care of all the rest of the possible r except 11 and 23. What I am unsure of is how to handle the cases of r = 11 and 23 without using a calculator to find that 4097 has 2 prime factors? But maybe I should have just checked whether 4097 was divisible by the the first 10 primes and found that indeed it was divisible by 17? Also, how would you arrive at the hint if you were working this problem in a test without the hint? Or is the hint kind of necessary?
Last edited:
