1
$\begingroup$

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

2 Answers 2

3

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

  • 0
    Yes, I saw that. What's your point? You noted something about odd numbers, but you didn't ask anything about odd numbers. You have one question mark in the title, and one in the body, and no reference to odd numbers in either place where there's a question mark, i.e., no reference to odd numbers where you actually ask a question. But in any event if you really do want only odd $k$ then there's an easy fix for the kind of answer I gave.2011-12-10
0

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