# Compositeness of number $k\cdot 2^n+1$?

Every odd prime number can be expressed in the form $k \cdot 2^n+1$ ,where $k$ is an odd number .

For $n>2$ number $k \cdot 2^n+1$ is composite if :

$1.$ $k\equiv 1 \pmod {30} \land (n\equiv 2 \pmod 4 \lor n \equiv 1 \pmod 2 )$

$2.$ $k\equiv 3 \pmod {30} \land n\equiv 3 \pmod 4$

$3.$ $k\equiv 5 \pmod {30} \land n\equiv 0 \pmod 2$

$4.$ $k\equiv 7 \pmod {30} \land n\equiv 1 \pmod 2$

$5.$ $k\equiv 9 \pmod {30} \land n\equiv 0 \pmod 4$

$6.$ $k\equiv 11 \pmod {30} \land n\equiv 0 \pmod 2$

$7.$ $k\equiv 13 \pmod {30} \land n\equiv 1 \pmod 2$

$8.$ $k\equiv 17 \pmod {30} \land (n\equiv 1 \pmod 4 \lor n\equiv 0 \pmod 2)$

$9.$ $k\equiv 19 \pmod {30} \land (n\equiv 0 \pmod 4 \lor n\equiv 1 \pmod 2)$

$10.$ $k\equiv 21 \pmod {30} \land n\equiv 2 \pmod 4$

$11.$ $k\equiv 23 \pmod {30} \land (n\equiv 3 \pmod 4 \lor n\equiv 0 \pmod 2)$

$12.$ $k\equiv 25 \pmod {30} \land n\equiv 1 \pmod 2$

$13.$ $k\equiv 27 \pmod {30} \land n\equiv 1 \pmod 4$

$14.$ $k\equiv 29 \pmod {30} \land n\equiv 0 \pmod 2$

Are there some other similar relations between coefficient $k$ and exponent $n$ that ensure compositeness of number $k \cdot 2^n+1$ ?

-

There are zillions of such relations. For example: $2^6+1$ is a multiple of $13$, so $k2^n+1$ is composite if $n\equiv6\pmod{12}$ and $k\equiv1\pmod{13}$. You can make as many of these as you want.

EDIT: In general, take any numbers $q$ and $s$, and any prime $p$ dividing $q2^s+1$, and any $r$ such that $2^r\equiv1\pmod p$, then $k2^n+1$ is composite (since a multiple of $p$) when $k\equiv q\pmod p$ and $n\equiv s\pmod r$.

-
you are probably right,but in your example $k \equiv 1 \pmod {13}$ $k$ can be an even number so you need constraint $k \equiv 1 \pmod 2$... –  pedja Dec 9 '11 at 11:30
You asked for relations between $k$ and $n$ that ensure compositeness. You didn't ask for $k$ to be odd. Why would we need $k\equiv1\pmod2$? Isn't $(14)2^6+1$ a multiple of $13$? –  Gerry Myerson Dec 9 '11 at 22:17
please read text of the question carefully... –  pedja Dec 10 '11 at 8:32
I did. What's your point? –  Gerry Myerson Dec 10 '11 at 11:06
"where $k$ is an odd number...." –  pedja Dec 10 '11 at 11:14
show 1 more comment

Your findings have been generalized in this paper. Here, a covering system of integers is constructed and that allows for infinitely many numbers of the form $k\times2^n+1$ to be composite in the sequence of Lucas nubers.

So, for you, I guess the important part is that there are infinitely many Sierpinski numbers i.e. numbers of the form $k\times2^n+1$ are composite.

http://home.wlu.edu/~finchc/Research/RieselLucasArticle11.pdf

Just in case you are wondering what is a covering system, see this wiki entry

http://en.wikipedia.org/wiki/Covering_system

And this thing by Carl Pomerance

http://www.math.dartmouth.edu/~carlp/PDF/covertalkunder.pdf

-