I think $k=47$ works. Does anyone know how to prove that $47\cdot2^n + 1$ is always composite? Edit: Um... thanks, AIME15.

Mathematica says: $k=47$ does not work; taking $n = 583$ yields 1487939695262196876907983166454197495251350196192890428923003345454869706240895712896623468784438158657419591298913094265537812046389415279164757669092989298186306341246574002177, which is prime.

$k = 78557$. http://mathworld.wolfram.com/SierpinskisCompositeNumberTheorem.html Here's an outline of a (reasonable) solution:

Solution with awang11. The following prime factorizations are well-known: \begin{align*} 2^{2^0}+1&=3\\ 2^{2^1}+1&=5\\ 2^{2^2}+1&=17\\ 2^{2^3}+1&=257\\ 2^{2^4}+1&=65537\\ 2^{2^5}+1&=641\cdot 6700417. \end{align*}Then take $k$ to be $1$ modulo $3,5,17,257,65537,641$ and $-1$ modulo $6700417$, which we can do by the Chinese Remainder Theorem. Observe that if $\nu_2(k)=0$ the expression is divisible by $3$, if $\nu_2(k)=1$ the expression is divisible by $5$, and so on until if $\nu_2(k)=5$ the expression is divisible by $641$. Then if $\nu_2(k)\ge 6$, the expression is divisible by $6700417$, so done.

Mrdavid445 wrote: Prove that there exists a positive integer $k$ such that $k\cdot2^n+1$ is composite for every integer $n$. Let $c_n = k\cdot 2^{n} + 1$, so that $c_0 = k+1$ and $c_{n+1} = 2c_{n} - 1.$ Suppose that $c_i\equiv 0\pmod{p}.$ Then, \begin{align*} c_{i+1}&\equiv -1\pmod{p},\\ c_{i+2}&\equiv -3\pmod{p},\\ c_{i+3}&\equiv -7\pmod{p},\\ &\dots\\ c_{i+n}&\equiv 1-2^{n}\pmod{p},\\ \end{align*}and so the order of $c$ in $p$ is the same as $2^n$. By Fermat's Last Theorem this divides $p-1$. It suffices to find a set of primes s.t. the orders $q$ have $v_p(q_i) = x_{pi}$ and $$\sum \frac{1}{p^{x_{pi}}} \ge 1.$$for all the primes $p | \prod q.$ Then we will be able to do some Chinese Remainder Theorem magic on the orders to find what our $k$ has to be. This motivates us to look for primes that only have $2$ as a prime divisor of their order: factors of Fermat primes. And then you get the solution above mine.

Goodness me. We claim that there exists primes $p_1,p_2,...,p_{N+1}$ where $\text{ord}_{p_i}(2)=2^i$ for $i=1,...,N$ and $\text{ord}_{p_{N+1}}(2)=2^N$. Indeed, by Zsigmondy's theorem, we have that there exists $q$ where $2^{2^A} \equiv 1$ (mod $q$) and $2^{2^a} \not \equiv 1$ (mod $q$) for every $a<A$. Clearly, for reasons, we don't always multiply by just a prime to get from $2^{2^n}+1$ to $2^{2^{n+1}}+1$ so we will eventually get two such $q$'s which satisfy the conditions which gives us our $p_{N}$ and $p_{N+1}$. Now, by CRT, for any positive integers $r_1,r_2, \ldots, r_{N+1}$ we have that there exists $k$ where \[ k \cdot 2^{r_i} \equiv -1 \text{ }(\text{mod } p_i) \]But notice that \[ k \cdot 2^{r_i} \equiv k \cdot 2^{r_i+\text{ord}_{p_i}(2)} \text{ }(\text{mod } p_i) \]But by our choices of $\text{ord}_{p_i}(2)$ we can choose $r_i$ such that every positive integer is covered by an arithmetic progression in the form $r_i+m \cdot \text{ord}_{p_i}(2)$. Thus, $k \cdot 2^n \equiv -1$ (mod $p_i$) for every $n$. So, $k \cdot 2^n+1$ is never prime.

GeronimoStilton wrote: Solution with awang11. The following prime factorizations are well-known: \begin{align*} 2^{2^0}+1&=3\\ 2^{2^1}+1&=5\\ 2^{2^2}+1&=17\\ 2^{2^3}+1&=257\\ 2^{2^4}+1&=65537\\ 2^{2^5}+1&=641\cdot 6700417. \end{align*}Then take $k$ to be $1$ modulo $3,5,17,257,65537,641$ and $-1$ modulo $6700417$, which we can do by the Chinese Remainder Theorem. Observe that if $\nu_2(k)=0$ the expression is divisible by $3$, if $\nu_2(k)=1$ the expression is divisible by $5$, and so on until if $\nu_2(k)=5$ the expression is divisible by $641$. Then if $\nu_2(k)\ge 6$, the expression is divisible by $6700417$, so done. What is $\nu_2(k)$?

Arslan wrote: GeronimoStilton wrote: Solution with awang11. The following prime factorizations are well-known: \begin{align*} 2^{2^0}+1&=3\\ 2^{2^1}+1&=5\\ 2^{2^2}+1&=17\\ 2^{2^3}+1&=257\\ 2^{2^4}+1&=65537\\ 2^{2^5}+1&=641\cdot 6700417. \end{align*}Then take $k$ to be $1$ modulo $3,5,17,257,65537,641$ and $-1$ modulo $6700417$, which we can do by the Chinese Remainder Theorem. Observe that if $\nu_2(k)=0$ the expression is divisible by $3$, if $\nu_2(k)=1$ the expression is divisible by $5$, and so on until if $\nu_2(k)=5$ the expression is divisible by $641$. Then if $\nu_2(k)\ge 6$, the expression is divisible by $6700417$, so done. What is $\nu_2(k)$? $v_2(k)$ is the 2-adic valuation of $k$, which is the largest power of $2$ that divides $k$. More generally, $v_p(k)$ is the $p$-adic valuation of $k$. You can find more information about this online. (I believe there was also a great handout by Leo.Euler about this in Contests & Programs sometime ago.)

programmeruser wrote: Arslan wrote: GeronimoStilton wrote: Solution with awang11. The following prime factorizations are well-known: \begin{align*} 2^{2^0}+1&=3\\ 2^{2^1}+1&=5\\ 2^{2^2}+1&=17\\ 2^{2^3}+1&=257\\ 2^{2^4}+1&=65537\\ 2^{2^5}+1&=641\cdot 6700417. \end{align*}Then take $k$ to be $1$ modulo $3,5,17,257,65537,641$ and $-1$ modulo $6700417$, which we can do by the Chinese Remainder Theorem. Observe that if $\nu_2(k)=0$ the expression is divisible by $3$, if $\nu_2(k)=1$ the expression is divisible by $5$, and so on until if $\nu_2(k)=5$ the expression is divisible by $641$. Then if $\nu_2(k)\ge 6$, the expression is divisible by $6700417$, so done. What is $\nu_2(k)$? $v_2(k)$ is the 2-adic valuation of $k$. More generally, $v_p(k)$ is the $p$-adic valuation of $k$. You can find more information about this online. (I believe there was also a great handout by Leo.Euler about this in Contests & Programs sometime ago.) You could simply say the biggest power of $2$ dividing $k$.

Arslan wrote: You could simply say the biggest power of $2$ dividing $k$. yes, that's the definition of 2-adic valuation sorry, i forgot to add that, i'll add it right now if anyone else sees this thread in the future

GeronimoStilton wrote: Solution with awang11. The following prime factorizations are well-known: \begin{align*} 2^{2^0}+1&=3\\ 2^{2^1}+1&=5\\ 2^{2^2}+1&=17\\ 2^{2^3}+1&=257\\ 2^{2^4}+1&=65537\\ 2^{2^5}+1&=641\cdot 6700417. \end{align*}Then take $k$ to be $1$ modulo $3,5,17,257,65537,641$ and $-1$ modulo $6700417$, which we can do by the Chinese Remainder Theorem. Observe that if $\nu_2(k)=0$ the expression is divisible by $3$, if $\nu_2(k)=1$ the expression is divisible by $5$, and so on until if $\nu_2(k)=5$ the expression is divisible by $641$. Then if $\nu_2(k)\ge 6$, the expression is divisible by $6700417$, so done. Should not it be $v_2(n)$ not $v_2(k)$?!

i'm pretty sure variable letter names are an arbitrary choice i don't think it matters as long as you're consistent

wow was that ugly First, we make $k=1\pmod 3$, to cut out all odd $n$. Then, we make $k\equiv 1\pmod 5,$ to cut out all $n$ that are 2 mod 4, since the order of 2 mod 5 is 4 and $1\cdot4+1=5.$ Then, we make $k\equiv 1\pmod {17}$, to cut out all $n$ that are 4 mod 8, since the order of 2 mod 17 is 8 and $1\cdot 2^4+1=17$. Then, we make $k\equiv 1\pmod {257}$, to cut out all $n$ that are 8 mod 16, since the order of 2 mod 255 is 16 and $1\cdot 2^8+1=257$. Then, we make $k\equiv 1\pmod {65537}$, to cut out all $n$ that are 16 mod 32, since the order of 2 mod 65537 is 32 and $1\cdot 2^{16}+1=65536$. Then, we reach a crucial point. At this point, the only possible $n$ to produce a prime are multiples of 32. It is well known that $2^{32}+1$ is a semiprime. Let $p<q$ be primes such that $2^{32}+1=pq.$ Note that the order 2 mod both $p$ and $q$ is 64 (since neither of them are factors of $2^{32}-1=65537\cdot257\cdot17\cdot15$). We then make $$k\equiv -\frac{1}{2^{32}}\pmod p.$$Since the order of 2 mod $p$ is 64, this causes $k\cdot 2^n +1$ to be a multiple of $p$ when $n\equiv 32\pmod {64}.$ Finally, we make $$k\equiv -1\pmod q$$which causes $k\cdot 2^n +1$ to be a multiple of $q$ when $n\equiv 0\pmod {64}$. Now, we have successfully cut out all possible values of $n$ from making $k\cdot 2^n +1$ prime. Finally, since $3,5,17,257,65537,p,q$ are all primes, by Chinese Remainder Theorem, there exists $k$ such that $$k\equiv 1\pmod 5$$$$k\equiv 1\pmod {17}$$$$k\equiv 1\pmod {257}$$$$k\equiv 1\pmod {65537}$$$$k\equiv -\frac{1}{2^{32}}\pmod p$$$$k\equiv -1\pmod q,$$so we are done.

Let $k = x^4$ for $3\nmid x$ where we specify how we pick $x>1$ later. Then for all odd $n$ we have: \[k\cdot 2^{n}+1\equiv 1\cdot 2+1\equiv 0\pmod 3\]and $k\cdot 2^{n}+1>3$, so this number isn't prime. Also, if $n = 4m+2$, then by the Sophie-Germain identity: \[k\cdot 2^{n} + 1 = 4(x\cdot 2^{m})^4 + 1 = (x^2 2^{2m+1}+x\cdot 2^{m+1}+1)(x^2 2^{2m+1}-x\cdot 2^{m+1}+1)\]Hence $k\cdot 2^{n}+1$ is not prime as both brackets are positive integers $>1$. Now we fix the case $4\mid n$, so we want $f(s) = 16^{s}x^4+1$ not to be prime which requires some care: Let $x\equiv 1\pmod{17}$. Then if $s$ is odd, we have $16^{s}x^4+1\equiv (-1)^{s}+1\equiv 0\pmod{17}$ and as $16^{s}x^4+1>17$ we conclude that the expression isn't prime. Now we only need to consider $256^{s}x^4+1$. Let $x\equiv 1\pmod{257}$. Then if $s$ is odd, we have $256^{s}x^4+1\equiv (-1)^{s}+1\equiv 0\pmod{257}$ and as $256^{s}x^4+1>257$ we conclude that the expression isn't prime. Now we only need to consider $(2^{2^{4}})^{s}x^4+1$. Let $x\equiv 1\pmod{2^{2^{4}}+1}$. Similar to above, we only need to deal with the even $s$ case. Here actually $2^{2^{5}}+1$ isn't prime (this is the famous folklore counterexample to $2^{2^{n}}+1$ not being prime for all $n$) and we know that $641\mid 2^{2^{5}}+1$. So let $x\equiv 1\pmod p$ where $p=\frac{2^{2^{5}}+1}{641}$ is prime, so the odd case for $s$ is dealt with as before and pick $x$ such that $x^{4}\equiv -1\pmod{641}$. Such an $x$ exists as if $g$ is a primitive root $\pmod{641}$, then $g^{320}\equiv -1\pmod{641}$, so picking $x\equiv g^{80}\pmod{641}$ suffices to deal with the even cases. An $x$ satisfying all bullets exists due to the Chinese Remainder Theorem, the end.

We uploaded our solution https://calimath.org/pdf/USAMO1982-4.pdf on youtube https://youtu.be/fdVjrj2USAA.

Yall have less than $10$ residues? For each prime $p \ge 3$, note that by taking $k \equiv \frac{-1}{2^a} \pmod{p}$ we can make all $n \equiv a \pmod{p-1}$ composite. Then we may note that $3, 5, 7, 11, 13, 19, 31, 37, 41, 61, 73, 181$ are prime, and that the residues \begin{align*} &0 \pmod{2},\ 1 \pmod{4},\ 3 \pmod{6},\ 1 \pmod{10}, \\ &7 \pmod{12},\ 5 \pmod{18},\ 23 \pmod{30},\ 11 \pmod{36}, \\ &19 \pmod{40},\ 35 \pmod{60},\ 71 \pmod{72},\ 107 \pmod{180} \end{align*}form a complete residue set $\pmod{360}$ so all $n$ are thus composite.