Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$ ?

share|cite|improve this question
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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

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.

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

And this thing by Carl Pomerance

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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