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

  • 1
    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$...2011-12-09
  • 0
    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$?2011-12-09
  • 0
    please read text of the question carefully...2011-12-10
  • 0
    I did. What's your point?2011-12-10
  • 0
    "where $k$ is an odd number...."2011-12-10
  • 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