Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|improve this answer
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$... –  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.

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

share|improve this answer

Your Answer

 
discard

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.