# Can we find prime in the form of $2^nx+1$ for arbitrary $x>0$?

For example, is it so that if we append enough number of $0$s followed by a $1$, any element $x\in \mathbb{Z}_p^*$ can be interpreted as a prime number, where $p$ is a $k$-bit prime for parameter $k$? (e.g. $x0000\ldots 1$)

[update]

What I mean is that the $0$s and $1$ are binary bits. So suppose $p=2^{127}-1$, $x=2^{126} \iff x=\underbrace{1000\ldots00_2}_{126}$. Can we append, say $n$ $0$s and a $1$ such that $x'=x\underbrace{00\ldots0}_{n}1_2=\underbrace{1000\ldots00_2}_{126+n}1$ is a prime?

And can we do so for arbitrary $x\in \mathbb{Z}_p^*$?

[Update]

Let's ignore the $p$ and $k$, they aren't relevant in general. What Chris Culter said is right: can we find prime in the form of $2^nx+1$ for arbitrary $x>0$?

• To clarify, can you give a concrete example of what you mean? – Chris Culter Apr 25 '18 at 21:24
• Post-update: It seems like you're asking: for every number $x$, does there exist a prime number of the form $2^mx+1$? I'm not sure how $p$ and $k$ are relevant. – Chris Culter Apr 25 '18 at 22:04

$$78557 \cdot 2^n+1$$ is always composite (as proved by Selfridge via covering congruences). Finding such numbers is an old problem of Sierpinski.
• I agree, but I'm more interested in finding either a non-trivial counter-example or proof so I added a restriction that $x>0$ and the base is 2. – xtt Apr 25 '18 at 22:15