if $n\ge4$ then there exists a prime $p$ s.t. $n=p\cdot2^{k}+a$ where $k \ge 1$, $a<2^{k}$

If $n$ is a positive integer $\ge4$ then there exists a prime $p$ such that $n=p\cdot2^{k}+a$ where $k \ge 1$, $a<2^{k}$.

For example:

$333 = 41\cdot2^3 + 5$

$461 = 3\cdot2^7 + 77$

Work-in-Progress Proof:

Select $k$ so that $2^k \le n$ and $2^{k+1} > n$, i.e. $2^k * 2 > n$.

Divide $n$ by $2^k$ so that $n = 2^k + a$, $a < 2^k$ by the division algorithm.

So $n = 2*2^{k-1} + a$, 2 is prime ($p=2$), $k \ge 1$, and $a < 2^k$.

• On what grounds do you think this is true? Nov 19, 2013 at 8:11
• @Gerry I have verified it for 4 <= n <= 1000000. Nov 19, 2013 at 8:14
• divide $n$ by $2$ until you get a quotient of $2$ or $3$. Nov 19, 2013 at 8:14
• Is it true for 30? Nov 19, 2013 at 8:14
• @hhsaffar: yes, 30 = 7*2^2 + 2, 30 = 3*2^3 + 6. Nov 19, 2013 at 8:18

I do not know if I misunderstood something: if $n\geq 4$ is odd then $\exists ! k,\ k\in \mathbb N$ such that $2^k< n < 2^{k+1}$. This means $n= 2^k + a$ with $a < 2^k$ (if not we will have $n\geq 2^{k=1}$). For the even case, we can use a really similar line of reasoning ($n=2^{k_n}\cdot m$ with $m$ odd). In particular, in each case, we have $p=1$.
• $n=2^{k_n}\cdot m$ with $m$ odd. So we know that $m=2^{k_m}+a_m$ with $a_m< 2^{k_n}$. Define $a_n= 2^{k_n}\cdot a_m$. We have that $a_n< 2^{k_n+k_m}$ and $n=2^{k_n+k_m}+ a_n$. Nov 19, 2013 at 8:48
• Sorry, I made a typo mistake: $a_m< 2^{k_m}$. Nov 19, 2013 at 8:50
• Ok thanks, there is still a problem, is $1$ a prime number... Nov 19, 2013 at 8:53
• No it is not a real problen. Can you see it? HINT: if $a<2^{k-1}$ no problem, if $2^{k-1}\leq a < 2^{k}$ reuse the same construction. Nov 19, 2013 at 9:01